zbMATH — the first resource for mathematics

On the complexity of nonnegative matrix factorization. (English) Zbl 1206.65130
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.

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
Full Text: DOI