Low-Rank Matrix Approximation with Weights or Missing Data is NP-hard

Abstract

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 study the computational complexity of WLRA and prove that it is NP-hard to find an approximate solution, even when a rank-one approximation is sought. Our proofs are based on a reduction from the maximum-edge biclique problem, and apply to strictly positive weights as well as binary weights (the latter corresponding to low-rank matrix approximation with missing data).

Proof of Lemma 4 (Lemma 3 in v1) has been corrected. Some remarks and comments have been added. Accepted in SIAM Journal on Matrix Analysis and Applications

References in corpus (2)

• Low-Rank Matrix Approximation with Weights or Missing Data is NP-hard
• Matrix Completion With Noise

Cited by in corpus (34)

• Convolutional neural networks with low-rank regularization
• Smooth PARAFAC Decomposition for Tensor Completion
• Low-Rank Matrix Approximation with Weights or Missing Data is NP-hard
• Global Optimality in Low-rank Matrix Optimization
• The Non-convex Geometry of Low-rank Matrix Optimization
• Quaternion-based bilinear factor matrix norm minimization for color image inpainting
• Experimentally bounding deviations from quantum theory in the landscape of generalized probabilistic theories
• Introduction to Nonnegative Matrix Factorization
• On the Complexity of Robust PCA and ${\ell }_1$-norm Low-Rank Matrix Approximation
• Structured low-rank matrix completion for forecasting in time series analysis
• Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss
• Convex Optimization without Projection Steps
• Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy
• Low-Rank Matrix Approximation in the Infinity Norm
• Average value of solutions for the bipartite boolean quadratic programs and rounding algorithms
• Recovery guarantee of weighted low-rank approximation via alternating minimization
• Heuristic algorithms for the bipartite unconstrained 0-1 quadratic programming problem
• An apocalypse-free first-order low-rank optimization algorithm with at most one rank reduction attempt per iteration
• Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and Applications
• Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach
• Low-rank optimization methods based on projected projected-gradient descent that accumulate at Bouligand stationary points
• Recovering Multiple Nonnegative Time Series From a Few Temporal Aggregates
• Spurious Valleys, NP-hardness, and Tractability of Sparse Matrix Factorization With Fixed Support
• On Weighted Low-Rank Approximation
• Theoretical Guarantees for Low-Rank Compression of Deep Neural Networks
• Low-Rank Matrix Optimization Over Affine Set
• Theory-independent monitoring of the decoherence of a superconducting qubit with generalized contextuality
• Generalized low rank approximation to the symmetric positive semidefinite matrix
• Pursuits in Structured Non-Convex Matrix Factorizations
• Exact solutions in low-rank approximation with zeros
• Fast Rank-1 NMF for Missing Data with KL Divergence
• Does a sparse ReLU network training problem always admit an optimum?
• Low-rank quaternion tensor completion for recovering color videos and images
• Markov Chain methods for the bipartite Boolean quadratic programming problem