Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data

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-à-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 ${\ell }_{\infty }$ 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.

arXiv commentaccepted to the Annals of Statistics

References in corpus (18)

• An overview of low-rank matrix recovery from incomplete observations
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Latent variable graphical model selection via convex optimization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• Sparse PCA: Optimal rates and adaptive estimation
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Incoherence-Optimal Matrix Completion
• An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
• Minimax risk of matrix denoising by singular value thresholding
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Non-convex Robust PCA
• Matrix Completion with Noisy Entries and Outliers
• Accelerated Alternating Projections for Robust Principal Component Analysis
• Composite optimization for robust blind deconvolution
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity