[ACM Press the 44th symposium - New York, New York, USA (2012.05.19-2012.05.22)] Proceedings of the 44th symposium on Theory of Computing - STOC '12 - Computing a nonnegative matrix factorization -- provably

✍ Scribed by Arora, Sanjeev; Ge, Rong; Kannan, Ravindran; Moitra, Ankur

• Book ID: 126452357
• Publisher: ACM Press
• Year: 2012
• Tongue: English
• Weight: 858 KB
• Category: Article
• ISBN: 1450312454
• DOI: 10.1145/2213977.2213994

✦ Synopsis

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 × 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 N M F 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