Low-Rank Matrix Approximation with Weights or Missing Data Is NP-Hard

By Nicolas Gillis, François Glineur. 2010

201 citations recorded by the source corpus.

Weighted low-rank approximation (WLRA), a dimensionality reduction technique for data analysis, has been successfully used in several applications, such as in collaborative filtering to design recommender systems or in computer vision to recover structure from motion. In this paper, we prove that computing an optimal WLRA is NP-hard, already when a rank-one approximation is sought. In fact, we show that it is hard to compute approximate solutions to the WLRA problem with some prescribed accuracy. Our proofs are based on reductions from the maximum-edge biclique problem and apply to strictly positive weights as well as to binary weights (the latter corresponding to low-rank matrix approximation with missing data).

Subfields: Artificial Intelligence, Computational Mechanics, Algorithms & Complexity, Signal Processing

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Algorithms & Complexity

In Signal Processing

Citations in the corpus

Recovery guarantee of weighted low-rank approximation via alternating minimization (2016, background): “Given the observation M = M ∗ + N where N is a noise matrix, we want to recover the ground truth M ∗ by solving the weighted low-rank approximation problem for M and a non-negative weight matrix W : where R k is the set of rank-k n by n matrices, and A 2 W = i,j W i,j A 2 i,j is the weighted…”
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).”
Weighted low rank approximations with provable guarantees (2016, methodology): “To construct a weighted low-rank appoximation problem from a given bipartite graph, for a given bipartite graph G(U, V,E), we generate the matrix A andW as in [24]: Aij = 1 if edge (Ui, Vj) ∈ E, Aij = 0 if edge (Ui, Vj) / ∈ E.”
Unifying Nuclear Norm and Bilinear Factorization Approaches for Low-Rank Matrix Decomposition (2013, background): “We note that this is not surprising since the problem of factorization with missing data is NP-Hard.”
On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation (2015, unknown): “However, the problem is NP-hard for any fixed factorization rank [17], even in the rank-one case (that is, for r = 1).”
The non-convex geometry of low-rank matrix optimization (2016, methodology): “n problem where W is the all-ones matrix, in general there is no analytic solutions for the weighted PCA problem (1.4) [47] and directly solving this traditional ‘ 2 loss (1.4) is known to be NP-hard [26]. We now apply Theorem2to the weighted PCA problem and show the objective function in (1.4) has ”
Generalized Low Rank Models (2014, methodology): “) = w ij(a u)2, where w ij is a weight, and take r= ~r= 0. Unlike PCA, the weighted PCA problem has no known analytical solution [SJ03]. In fact, it is NP-hard to nd an exact solution to weighted PCA [GG11], although it is not known whether it is always possible to nd approximate solutions of modera”