NCTS(South)/ NCKU Math Colloquium
DATE	2012-03-08　15:10-16:00
PLACE	R204, 2F, NCTS, NCKU
SPEAKER	Prof. Moody T. Chu (朱天照 教授)（North Carolina State University, USA）
TITLE	Nonnegative Rank Factorization — A Heuristic Approach via Rank Reduction
ABSTRACT	Any given nonnegative matrix A 2 Rmn can be expressed as the product A = UV for some nonnegative matrices U 2 Rmk and V 2 Rkn with k  minfm; ng. The smallest k that makes this factorization possible is called the nonnegative rank of A. Computing the exact nonnegative rank and the corresponding factorization are known to be NP-hard. Even if the nonnegative rank is known a priori, no simple procedure exists that is able to perform the nonnegative factorization. Based on the Wedderburn rank reduction formula, this paper proposes a heuristic approach to tackle this difficult problem numerically. Starting with A, the idea is to recurrently extract, whenever possible, a rank-one nonnegative portion from the previous matrix while keeping the residual nonnegative and lowering its rank by one. With a slight modification for symmetry, the method can equally be applied to another important class of completely positive matrices. No error analysis is provided at present, as even no perturbation theory for nonnegative rank is known in the literature. More theoretical research is needed. However, numerical testing seems to suggest that the proposed algorithm might serve as a first-step numerical means for exploring the intriguing problem of nonnegative rank factorization.