TY - GEN

T1 - Computing a nonnegative matrix factorization - Provably

AU - Arora, Sanjeev

AU - Ge, Rong

AU - Kannan, Ravindran

AU - Moitra, Ankur

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - data analysis

KW - nonnegative matrix factorization

KW - semi-algebric sets

UR - http://www.scopus.com/inward/record.url?scp=84862609231&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862609231&partnerID=8YFLogxK

U2 - 10.1145/2213977.2213994

DO - 10.1145/2213977.2213994

M3 - Conference contribution

AN - SCOPUS:84862609231

SN - 9781450312455

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 145

EP - 161

BT - STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing

T2 - 44th Annual ACM Symposium on Theory of Computing, STOC '12

Y2 - 19 May 2012 through 22 May 2012

ER -