Low-rank matrix approximation with weights or missing data is NP-hard
From MaRDI portal
biadjacency matrixbipartite graphcomputational complexitymatrix completion with noisemissing datanonnegative matrix factorizationprincipal component analysisweighted low-rank matrix approximation
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Factorization of matrices (15A23) Matrix completion problems (15A83) Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20) 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
(32)- Markov chain methods for the bipartite Boolean quadratic programming problem
- Block tensor train decomposition for missing data estimation
- An efficient method for non-negative low-rank completion
- Convex low rank approximation
- Low-rank matrix approximation in the infinity norm
- A gradient system for low rank matrix completion
- Low-rank tensor completion based on log-det rank approximation and matrix factorization
- Low-rank matrix completion via preconditioned optimization on the Grassmann manifold
- The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
- Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs
- Exact solutions in low-rank approximation with zeros
- The bipartite Boolean quadric polytope
- A global exact penalty for rank-constrained optimization problem and applications
- Algorithms and Literate Programs for Weighted Low-Rank Approximation with Missing Data
- Weighted norms in subspace-based methods for time series analysis.
- Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
- Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
- Color image inpainting via robust pure quaternion matrix completion: error bound and weighted loss
- The bipartite QUBO
- Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking
- On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
- Weighted low rank approximations with provable guarantees
- Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy
- An Apocalypse-Free First-Order Low-Rank Optimization Algorithm with at Most One Rank Reduction Attempt per Iteration
- Spurious Valleys, NP-Hardness, and Tractability of Sparse Matrix Factorization with Fixed Support
- Normal Cones Intersection Rule and Optimality Analysis for Low-Rank Matrix Optimization with Affine Manifolds
- Theoretical guarantees for low-rank compression of deep neural networks
- Fast estimation of the Renshaw-Haberman model and its variants
- Efficient quaternion CUR method for low-rank approximation to quaternion matrix
- Geometry and optimization of shallow polynomial networks
- Color video recovery through low-rank quaternion tensor completion with nonconvex weighted Laplace regularization
- Factorized binary polynomial optimization
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)
