Computing a nonnegative matrix factorization -- provably

By Sanjeev Arora, Rong Ge, R. Kannan, Ankur Moitra. Symposium on the Theory of Computing, 2011

419 citations recorded by the source corpus.

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

Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/6456d62f3a918d0b1171e09b648df879da481c8c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Electrical and Electronic Engineering

Citations in the corpus

New Algorithms for Learning Incoherent and Overcomplete Dictionaries (2013, methodology): “Our goal is to design an algorithm for this problem with provable guarantees in the same spirit as recent work on nonnegative matrix factorization [5], topic models [6], [4] and mixtures models [39], [10].”
Robust Subspace Clustering (2013, methodology): “In particular, [5] and recent variations [5, 12] use a convex formulation very similar to SSC for the purpose of nonnegative matrix factorizations.”
Low rank approximation with entrywise l1-norm error (2017, methodology): “For any p ∈ [1, 2], the `p -norm of a vector x ∈ Rd is de ned as”
A Practical Algorithm for Topic Modeling with Provable Guarantees (2012, methodology): “See Arora et al. [2012a] and Arora et al. [2012b] for more details about this problem.”
Learning Topic Models -- Going beyond SVD (2012, methodology): “Recently, we gave a polynomial time algorithm to solve NMF under the condition that the topic matrix A is separable [3].”
Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations (2017, positive): “For theoretical analysis, (Arora et al., 2012b) provided a ﬁxed-parameter tractable algo-rithm for NMF using algebraic equations.”
Recovery Guarantee of Non-negative Matrix Factorization via Alternating Updates (2016, background): “[AGKM12] Sanjeev Arora, Rong Ge, Ravindran Kannan, and Ankur Moitra.”
Spectral Methods for Supervised Topic Models (2014, background): “Much recent progress has been made on developing spectral decomposition [1] [2] [3] and nonnegative matrix factorization (NMF) [4] [5] [6] [7] methods to infer latent topic-word distributions.”
On the Geometric Interpretation of the Nonnegative Rank (2010, background): “[2] have shown very recently that checking whether the nonnegative rank of an m-by-n nonnegative matrix is equal to k can be done in polynomial time inm and n (not in k).”
Weighted low rank approximations with provable guarantees (2016, methodology): “Then this can be solved in time (md)O(v) using generic solvers [49, 48, 47, 8], and such techniques have been used in the context of database theory [21], non-negative matrix factorization [4, 43], learning mixtures of Gaussians [36], computing approximate PSD factorizations [6], and solving small-s”
The Why and How of Nonnegative Matrix Factorization (2014, methodology): “This new direction of research was launched by a paper by Arora et al. [4] which shows that NMF of separable matrices can be computed eﬃciently (that is, in polynomial time), even in the presence of noise (the error can be bounded in terms of the noise level; see below).”
Scalable Temporal Latent Space Inference for Link Prediction in Dynamic Social Networks (2014, background): “Only if the input matrix G is separable or near-separable [27], [28], we are able to achieve the global optimum or a global error bound.”
Most Tensor Problems Are NP-Hard (2009, background): “For example, matrix (p, q)-norms when 1 ≤ q ≤ p ≤ ∞ [Steinberg 2005], nonnegative rank of nonnegative matrices [Vavasis 2009; Arora et al. 2012], sparsest null vector [Coleman and Pothen 1986], and rank minimization with linear constraints [Natarajan 1995] are all known to be NP-hard; the matrix p-n”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “Without making any assumptions, those non-convex problems are intractable (Arora et al., 2012a; Gillis & Vavasis, 2015; Song et al., 2017a; Gillis & Glineur, 2011; Razen-shteyn et al., 2016; Sontag & Roy, 2011; Hardt & Moitra, 2013; Arora et al., 2012b; Yi et al., 2014).”