Nonnegative rank factorization—a heuristic approach via rank reduction

Bo Dong, Matthew M. Lin, Moody T. Chu

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

Given any nonnegative matrix $A \in \mathbb{R}^{m \times n}$, it is always possible to express A as the sum of a series of nonnegative rank-one matrices. Among the many possible representations of A, the number of terms that contributes the shortest nonnegative rank-one series representation 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 presently 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 extrat, 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 convergence can be guaranteed, but repeated restart might help alleviate the difficulty. Extensive 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.

Original languageEnglish
Pages (from-to)251-274
Number of pages24
JournalNumerical Algorithms
Volume65
Issue number2
DOIs
Publication statusPublished - 2014 Feb 1

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Fingerprint Dive into the research topics of 'Nonnegative rank factorization—a heuristic approach via rank reduction'. Together they form a unique fingerprint.

  • Cite this