Vavasis, Stephen A. On the complexity of nonnegative matrix factorization. (English) Zbl 1206.65130 SIAM J. Optim. 20, No. 3, 1364-1377 (2009). Nonnegative matrix factorization (NMF) is important for database analysis, information retrieval and finding features in datasets. Such factorizations start from a nonnegative matrix \(A_{m,n}\) and a given integer \(k\) and try to find nonnegative matrices \(W_{m,k}\) and \(H_{k,n}\) so that \(A\) and \(W \cdot H\) are nearly identical. Here it is shown that the exact NMF (EXACT NMF) problem where \(k = \) rank\((A_{m,n})\) is equivalent to an NP hard problem in polyhedral combinatorics. It follows that a certain local search heuristic for the NMF can be solved via linear programming. The question whether any of these problems is actually NP is related to a still open question by J. E. Cohen and U. G. Rothblum [Linear Algebra Appl. 190, 149–168 (1993; Zbl 0784.15001)] of 1993. Reviewer: Frank Uhlig (Auburn) Cited in 2 ReviewsCited in 61 Documents MSC: 65F05 Direct numerical methods for linear systems and matrix inversion 68Q25 Analysis of algorithms and problem complexity 15A23 Factorization of matrices 90C60 Abstract computational complexity for mathematical programming problems 90C26 Nonconvex programming, global optimization 65Y20 Complexity and performance of numerical algorithms 15B48 Positive matrices and their generalizations; cones of matrices 68P10 Searching and sorting 68P15 Database theory 68P20 Information storage and retrieval of data Keywords:complexity; nonnegative matrix factorization; NP hard; nonnegative rank; data mining; database analysis, information retrieval; local search heuristic; linear programming PDF BibTeX XML Cite \textit{S. A. Vavasis}, SIAM J. Optim. 20, No. 3, 1364--1377 (2009; Zbl 1206.65130) Full Text: DOI