Matrix Rigidity and the Ill-Posedness of Robust PCA and Matrix Completion

DOI10.1137/18M1227846zbMath1502.62074arXiv1811.05919OpenAlexW2973685100WikidataQ127250705 ScholiaQ127250705MaRDI QIDQ5025789

Andrew Thompson, Simon Vary, Jared Tanner

Publication date: 3 February 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

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

zbMATH Keywords

matrix decompositionlow-rank matrix completionrobust PCAmatrix rigiditynonconvex methods

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Computational methods for sparse matrices (65F50) Robustness and adaptive procedures (parametric inference) (62F35) Ill-posedness and regularization problems in numerical linear algebra (65F22)

Related Items

Compressed sensing of low-rank plus sparse matrices, Sensitivity of low-rank matrix recovery

Uses Software

• SDPLR
• ADMiRA

Cites Work

• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Using elimination theory to construct rigid matrices
• Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
• Low rank matrix completion by alternating steepest descent methods
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Principal component analysis.
• Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
• Matrix recipes for hard thresholding methods
• Exact matrix completion via convex optimization
• Normalized Iterative Hard Thresholding for Matrix Completion
• Computational Advertising: Techniques for Targeting Relevant Ads
• Robust principal component analysis?
• A Singular Value Thresholding Algorithm for Matrix Completion
• Rank-Sparsity Incoherence for Matrix Decomposition
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• On the Best Rank-1 and Rank-(R₁ ,R₂ ,. . .,R_N) Approximation of Higher-Order Tensors
• CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix