Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
From MaRDI portal
Publication:2054540
DOI10.1214/21-AOS2066zbMATH Open1486.62181arXiv2001.05484MaRDI QIDQ2054540FDOQ2054540
Authors: Yuxin Chen, Cong Ma, Yuling Yan, Jianqing Fan 
Publication date: 3 December 2021
Published in: The Annals of Statistics (Search for Journal in Brave)
Abstract: This paper delivers improved theoretical guarantees for the convex programming approach in low-rank matrix estimation, in the presence of (1) random noise, (2) gross sparse outliers, and (3) missing data. This problem, often dubbed as robust principal component analysis (robust PCA), finds applications in various domains. Despite the wide applicability of convex relaxation, the available statistical support (particularly the stability analysis vis-`a-vis random noise) remains highly suboptimal, which we strengthen in this paper. When the unknown matrix is well-conditioned, incoherent, and of constant rank, we demonstrate that a principled convex program achieves near-optimal statistical accuracy, in terms of both the Euclidean loss and the loss. All of this happens even when nearly a constant fraction of observations are corrupted by outliers with arbitrary magnitudes. The key analysis idea lies in bridging the convex program in use and an auxiliary nonconvex optimization algorithm, and hence the title of this paper.
Full work available at URL: https://arxiv.org/abs/2001.05484
Recommendations
- Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
- Robust principal component analysis?
- Strongly convex programming for exact matrix completion and robust principal component analysis
- Robust PCA by manifold optimization
- Exact guarantees on the absence of spurious local minima for non-negative rank-1 robust principal component analysis
convex relaxationrobust principal component analysisleave-one-out analysis\( \ell_\infty\) guarantees
Factor analysis and principal components; correspondence analysis (62H25) Convex programming (90C25) Estimation in multivariate analysis (62H12) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Nonconvex programming, global optimization (90C26)
Cites Work
- Spectral regularization algorithms for learning large incomplete matrices
- Phase retrieval via Wirtinger flow: theory and algorithms
- High dimensional covariance matrix estimation using a factor model
- Large Covariance Estimation by Thresholding Principal Orthogonal Complements
- Robust principal component analysis?
- Fast alternating linearization methods for minimizing the sum of two convex functions
- Latent variable graphical model selection via convex optimization
- Noisy low-rank matrix completion with general sampling distribution
- Exact matrix completion via convex optimization
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
- Inference and uncertainty quantification for noisy matrix completion
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- Restricted strong convexity and weighted matrix completion: optimal bounds with noise
- Sparse PCA: optimal rates and adaptive estimation
- Clustering partially observed graphs via convex optimization
- Rank-Sparsity Incoherence for Matrix Decomposition
- Robust Matrix Decomposition With Sparse Corruptions
- Robust matrix completion
- Matrix Completion From a Few Entries
- Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization
- Noisy matrix decomposition via convex relaxation: optimal rates in high dimensions
- Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
- An Online Algorithm for Separating Sparse and Low-Dimensional Signal Sequences From Their Sum
- Compressed sensing and matrix completion with constant proportion of corruptions
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- Low-rank matrix completion using alternating minimization
- Minimax risk of matrix denoising by singular value thresholding
- Learning Theory
- Robust Spectral Compressed Sensing via Structured Matrix Completion
- Angular synchronization by eigenvectors and semidefinite programming
- Incoherence-Optimal Matrix Completion
- Blind Deconvolution Using Convex Programming
- Accelerated Alternating Projections for Robust Principal Component Analysis
- Recursive Robust PCA or Recursive Sparse Recovery in Large but Structured Noise
- Guaranteed Matrix Completion via Non-Convex Factorization
- Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
- The projected power method: an efficient algorithm for joint alignment from pairwise differences
- Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Guarantees of Riemannian optimization for low rank matrix recovery
- Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
- Phase Retrieval Using Alternating Minimization
- Robust covariance estimation for approximate factor models
- Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- An \(\ell_{\infty}\) eigenvector perturbation bound and its application
- Matrix completion with noisy entries and outliers
- Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
- On the convex geometry of blind deconvolution and matrix completion
- Nonconvex Rectangular Matrix Completion via Gradient Descent Without ℓ₂,∞ Regularization
- Composite optimization for robust rank one bilinear sensing
Cited In (15)
- Analysis of a nonsmooth optimization approach to robust estimation
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
- Stable local-smooth principal component pursuit
- Generalized Low-Rank Plus Sparse Tensor Estimation by Fast Riemannian Optimization
- A new complexity metric for nonconvex rank-one generalized matrix completion
- Spectral analysis of Gram matrices with missing at random observations: convergence, central limit theorems, and applications in statistical inference
- Non-convex matrix completion and related problems via strong duality
- GNMR: a provable one-line algorithm for low rank matrix recovery
- Robust PCA by manifold optimization
- Matrix rigidity and the ill-posedness of robust PCA and matrix completion
- Comment: Feature Screening and Variable Selection via Iterative Ridge Regression
- Strongly convex programming for exact matrix completion and robust principal component analysis
- A short note on strongly convex programming for exact matrix completion and robust principal component analysis
- Inference for heteroskedastic PCA with missing data
Uses Software
This page was built for publication: Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2054540)
