On the Complexity of Nonnegative Matrix Factorization

By Stephen A. Vavasis. SIAM Journal on Optimization, 2007

638 citations recorded by the source corpus.

Nonnegative matrix factorization (NMF) has become a prominent technique for the analysis of image databases, text databases, and other information retrieval and clustering applications. The problem is most naturally posed as continuous optimization. In this report, we define an exact version of NMF. Then we establish several results about exact NMF: (i) that it is equivalent to a problem in polyhedral combinatorics; (ii) that it is NP-hard; and (iii) that a polynomial-time local search heuristic exists.

Subfields: Computer Vision and Pattern Recognition, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/3e73308656edb029257fa87b232f8d116e1b6058

How researchers see this paper

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

In Computer Vision and Pattern Recognition

In Electrical and Electronic Engineering

Citations in the corpus

Scalable Temporal Latent Space Inference for Link Prediction in Dynamic Social Networks (2014, background): “1, which includes a symmetric Non-negative Matrix Factorization (the ﬁrst term), is also NP-hard.”
Song recommendation with non-negative matrix factorization and graph total variation (2016, background): “NMF comes to the cost of being NP-hard [15], so sophisticated regularization is important for finding a good local minimum.”
Fast Nonnegative Matrix Factorization: An Active-Set-Like Method and Comparisons (2011, background): “Factors W and H are then found by solving the optimization problem: min W≥0,H≥0 f(W,H) = 1 2 ‖A−WH‖2F , (1.2) ∗An earlier version of this paper appeared in a conference proceeding: Jingu Kim and Haesun Park.”
Nonnegative Matrix Factorization: A Comprehensive Review (2013, background): “The theoretical results on complete NMF will be helpful to design more efficient NMF algorithms [31], [34].”
Detecting Memorization in ReLU Networks (2018, methodology): “Although computing the non-negative rank is NP-hard (Vavasis, 2009), we can restrict it with approximate non-negative matrix factorization (NMF) (Lee & Seung, 1999).”
Computing a nonnegative matrix factorization -- provably (2011, methodology): “Vavasis [36] proved that Intermediate Simplex is equivalent to the Simplicial Factorization problem.”
Most Tensor Problems Are NP-Hard (2009, background): “For example, matrix (p, q)-norms when 1 = q = p =8[Steinberg 2005], nonnegative rank of nonnegative matrices [Arora et al. 2012; Vavasis 2009], sparsest null vector [Coleman and Pothen 1986], and rank minimization with linear constraints [Natarajan 1995] are all known to be NP-hard; the matrix…”
Low-Rank Matrix Approximation with Weights or Missing Data Is NP-Hard (2010, neutral): “Note that (unweighted) NMF has been shown to be NP-hard when r is not fixed [29] (i.”
FIXED POINTS OF THE EM ALGORITHM AND NONNEGATIVE RANK BOUNDARIES (2013, methodology): “The proof of Theorem 4.1 is based on the familiar characterization of nonnegative rank in terms of nested polytopes [ 1, 10, 33], and, in particular, on work of Mond et al. [29] on the structure of critical conﬁgurations in the plane (shown in Figure 5).”
Generalized Low Rank Models (2014, methodology): “a solution gives the matrix best approximating Athat has a nonnegative factorization (i.e., a factorization into elementwise nonnegative matrices) [LS99]. It is NP-hard to solve NNMF problems exactly [Vav09]. However, these problems have a rich analytical structure which can sometimes be exploited [”
A Signal Processing Perspective on Hyperspectral Unmixing: Insights from Remote Sensing (2014, neutral): “First, (41) is NP-hard in general [66].”
Learning Topic Models -- Going beyond SVD (2012, background): “The general problem of ﬁnding nonnegative factors A, W of speciﬁed dimensions when given the matrix AW (or a close approximation) is called the Nonnegative Matrix Factorization (NMF) problem (see [22], and [2] for a longer history) and it is NP-hard [31].”
On the Geometric Interpretation of the Nonnegative Rank (2010, methodology): “We now prove equivalence between RNR and NPP, which generalizes the result of Vavasis [42] showing equivalence between exact NMF and intermediate simplex.”
Non‐parametric identification and estimation of the number of components in multivariate mixtures (2014, background): “(Vavasis (2009) has shown that determining the non-negative rank of a matrix is non-deterministic polynomial time hard.)”
Interventional Fairness: Causal Database Repair for Algorithmic Fairness (2019, background): “The following implied from NP-hardness of NMF [50].”
The Why and How of Nonnegative Matrix Factorization (2014, background): “Unfortunately, as opposed to the unconstrained problem which can be solved eﬃciently using the SVD, NMF is NP-hard in general [105].”