Skip to main content

Computing a nonnegative matrix factorization-provably

Author(s): Arora, Sanjeev; Ge, R; Kannan, R; Moitra, A

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1jf1k
Full metadata record
DC FieldValueLanguage
dc.contributor.authorArora, Sanjeev-
dc.contributor.authorGe, R-
dc.contributor.authorKannan, R-
dc.contributor.authorMoitra, A-
dc.date.accessioned2019-08-29T17:05:01Z-
dc.date.available2019-08-29T17:05:01Z-
dc.date.issued2016en_US
dc.identifier.citationArora, S, Ge, R, Kannan, R, Moitra, A. (2016). Computing a nonnegative matrix factorization-provably. SIAM Journal on Computing, 45 (1582 - 1611. doi:10.1137/130913869en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1jf1k-
dc.description.abstractIn the nonnegative matrix factorization (NMF) problem we are given an n × m nonnegative matrix M and an integer r > 0. Our goal is to express M as AW, where A and W are nonnegative matrices of size n×r and r×m, respectively. In some applications, it makes sense to ask instead for the product AW to approximate M, i.e. (approximately) minimize ||M - AWF||, where || ||F,denotes the Frobenius norm; we refer to this as approximate NMF. This 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 A and W are computed using a variety of local search heuristics. Vavasis recently proved that this problem is NP-complete. (Without the restriction that A and W be nonnegative, both the exact and approximate problems can be solved optimally via the singular value decomposition.) We initiate a study of when this problem is solvable in polynomial time. 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 subexponential-time algorithm. This rules out substantial improvements to the above algorithm. 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 example of a polynomial-time algorithm that provably works under a non-trivial condition on the input and we believe that this will be an interesting and important direction for future work.en_US
dc.format.extent1582 - 1611en_US
dc.language.isoen_USen_US
dc.relation.ispartofSIAM Journal on Computingen_US
dc.rightsAuthor's manuscripten_US
dc.titleComputing a nonnegative matrix factorization-provablyen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1137/130913869-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
Computing a Nonnegative Matrix Factorization -- Provably.pdf544.81 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.