Computing a nonnegative matrix factorization - Provably

Sanjeev Arora, Rong Ge, Ravindran Kannan, Ankur Moitra

Research output: Chapter in Book/Report/Conference proceedingConference contribution

220 Scopus citations


The Nonnegative Matrix Factorization (NMF) problem has a rich history spanning quantum mechanics, probability theory, data analysis, polyhedral combinatorics, communication complexity, demography, chemometrics, etc. In the past decade NMF has become enormously popular in machine learning, where the factorization is computed using a variety of local search heuristics. Vavasis recently proved that this problem is NP-complete. We initiate a study of when this problem is solvable in polynomial time. Consider a nonnegative m x n matrix M and a target inner-dimension r. Our results are the following: 1. We give a polynomial-time algorithm for exact and approximate NMF for every constant r. Indeed NMF is most interesting in applications precisely when r is small. 2. We complement this with a hardness result, that if exact NMF can be solved in time (nm) o(r), 3-SAT has a sub-exponential time algorithm. Hence, substantial improvements to the above algorithm are unlikely. 3. We give an algorithm that runs in time polynomial in n, m and r under the separablity condition identified by Donoho and Stodden in 2003. The algorithm may be practical since it is simple and noise tolerant (under benign assumptions). Separability is believed to hold in many practical settings. To the best of our knowledge, this last result is the first polynomial-time algorithm that provably works under a non-trivial condition on the input matrix and we believe that this will be an interesting and important direction for future work.

Original languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Number of pages17
StatePublished - 2012
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Other44th Annual ACM Symposium on Theory of Computing, STOC '12
Country/TerritoryUnited States
CityNew York, NY

All Science Journal Classification (ASJC) codes

  • Software


  • data analysis
  • nonnegative matrix factorization
  • semi-algebric sets


Dive into the research topics of 'Computing a nonnegative matrix factorization - Provably'. Together they form a unique fingerprint.

Cite this