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

DOI10.1137/110820361zbMath1242.65077arXiv1012.0197OpenAlexW2162171343MaRDI QIDQ3225532

Nicolas Gillis, François Glineur

Publication date: 21 March 2012

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

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

zbMATH Keywords

computational complexitybipartite graphprincipal component analysismissing datanonnegative matrix factorizationbiadjacency matrixmatrix completion with noiseweighted low-rank matrix approximation

Mathematics Subject Classification ID

Related Items (24)

Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss ⋮ The Bipartite QUBO ⋮ Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs ⋮ Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem ⋮ Exact solutions in low-rank approximation with zeros ⋮ The bipartite Boolean quadric polytope ⋮ 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 ⋮ Weighted norms in subspace-based methods for time series analysis ⋮ 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 ⋮ A global exact penalty for rank-constrained optimization problem and applications ⋮ Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking ⋮ Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms ⋮ An efficient method for non-negative low-rank completion ⋮ Convex low rank approximation ⋮ Markov chain methods for the bipartite Boolean quadratic programming problem ⋮ Block tensor train decomposition for missing data estimation ⋮ Low-rank matrix approximation in the infinity norm ⋮ On the Complexity of Robust PCA and ℓ₁-Norm Low-Rank Matrix Approximation ⋮ 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

This page was built for publication: Low-Rank Matrix Approximation with Weights or Missing Data Is NP-Hard