Low-rank matrix approximation with weights or missing data is NP-hard

DOI10.1137/110820361zbMATH Open1242.65077arXiv1012.0197OpenAlexW2162171343MaRDI QIDQ3225532FDOQ3225532

Authors: Nicolas Gillis, François Glineur 

Publication date: 21 March 2012

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1012.0197

Recommendations

• On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
• Weighted low rank approximations with provable guarantees
• On a Problem of Weighted Low-Rank Approximation of Matrices
• Computational Science and Its Applications – ICCSA 2004
• scientific article; zbMATH DE number 18873

zbMATH Keywords

computational complexitymissing dataprincipal component analysisnonnegative matrix factorizationbipartite graphbiadjacency matrixmatrix completion with noiseweighted low-rank matrix approximation

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Complexity and performance of numerical algorithms (65Y20) Factorization of matrices (15A23) Matrix completion problems (15A83) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (26)

• Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking
• Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs
• Algorithms and Literate Programs for Weighted Low-Rank Approximation with Missing Data
• Color image inpainting via robust pure quaternion matrix completion: error bound and weighted loss
• The bipartite Boolean quadric polytope
• Low-rank matrix completion via preconditioned optimization on the Grassmann manifold
• Low-rank tensor completion based on log-det rank approximation and matrix factorization
• Low-rank matrix approximation in the infinity norm
• The bipartite QUBO
• On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
• Weighted low rank approximations with provable guarantees
• Markov chain methods for the bipartite Boolean quadratic programming problem
• An Apocalypse-Free First-Order Low-Rank Optimization Algorithm with at Most One Rank Reduction Attempt per Iteration
• A gradient system for low rank matrix completion
• Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
• An efficient method for non-negative low-rank completion
• Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
• Exact solutions in low-rank approximation with zeros
• Normal Cones Intersection Rule and Optimality Analysis for Low-Rank Matrix Optimization with Affine Manifolds
• Spurious Valleys, NP-Hardness, and Tractability of Sparse Matrix Factorization with Fixed Support
• Weighted norms in subspace-based methods for time series analysis.
• Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy
• A global exact penalty for rank-constrained optimization problem and applications
• Convex low rank approximation
• Block tensor train decomposition for missing data estimation
• The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases

This page was built for publication: Low-rank matrix approximation with weights or missing data is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3225532)