On the complexity of nonnegative matrix factorization
For researchers in machine learning and optimization, this work provides foundational complexity results for NMF, a widely used technique.
The paper establishes that exact nonnegative matrix factorization (NMF) is NP-hard, while also showing its equivalence to a polyhedral combinatorics problem and providing a polynomial-time local search heuristic.
Nonnegative matrix factorization (NMF) has become a prominent technique for the analysis of image databases, text databases and other information retrieval and clustering applications. In this report, we define an exact version of NMF. Then we establish several results about exact NMF: (1) that it is equivalent to a problem in polyhedral combinatorics; (2) that it is NP-hard; and (3) that a polynomial-time local search heuristic exists.