On the complexity of nonnegative matrix factorization

Abstract

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.

Version 2 corrects small typos; adds ref to Cohen & Rothblum; adds ref to Gillis; clarifies reduction of NMF to int. simplex

Cited by in corpus (4)

• Identification of conserved moieties in metabolic networks by graph theoretical analysis of atom transition networks
• Learning Hidden Markov Models using Non-Negative Matrix Factorization
• NMF-based GPU accelerated coronagraphy pipeline
• First Order Methods for Robust Non-negative Matrix Factorization for Large Scale Noisy Data