Low-rank matrix approximation with weights or missing data is NP-hard
From MaRDI portal
Publication:3225532
computational complexitymissing dataprincipal component analysisnonnegative matrix factorizationbipartite graphbiadjacency matrixmatrix completion with noiseweighted low-rank matrix approximation
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)
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).
Recommendations
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
- The bipartite Boolean quadric polytope
- Low-rank matrix completion via preconditioned optimization on the Grassmann manifold
- Color image inpainting via robust pure quaternion matrix completion: error bound and weighted loss
- 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
- Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
- An efficient method for non-negative low-rank completion
- 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)
