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

arXiv: https://arxiv.org/abs/2001.05484 · HTML: https://mlsanity.com/paper/2001.05484/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2020.

## Built on by (most cited first, 23 of 23)

- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (2021)
- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)
- [Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descent](https://mlsanity.com/paper/2206.09109/) (2022)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Low-Rank Contextual Reinforcement Learning from Heterogeneous Human Feedback](https://mlsanity.com/paper/2412.19436/) (2024)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Non-Asymptotic Guarantees for Robust Statistical Learning under Infinite Variance Assumption](https://mlsanity.com/paper/2201.03182/) (2022)
- [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023)
- [Learning Treatment Effects in Panels with General Intervention Patterns](https://mlsanity.com/paper/2106.02780/) (2021)
- [Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent](https://mlsanity.com/paper/2305.17224/) (2023)
- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [Exact Recovery for System Identification with More Corrupt Data than Clean Data](https://mlsanity.com/paper/2305.10506/) (2023)
- [Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery](https://mlsanity.com/paper/2106.09211/) (2021)
- [Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions](https://mlsanity.com/paper/2407.19446/) (2024)
- [Exact Recovery Guarantees for Parameterized Nonlinear System Identification Problem under Sparse Disturbances or Semi-Oblivious Attacks](https://mlsanity.com/paper/2409.00276/) (2024)
- [Heterogeneous Treatment Effects in Panel Data](https://mlsanity.com/paper/2406.05633/) (2024)
- [Alternating minimization for square root principal component pursuit](https://mlsanity.com/paper/2501.00471/) (2024)
- [RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees](https://mlsanity.com/paper/2505.12919/) (2025)
- [Transfer Denoising of Low-Rank Plus Sparse Matrices under Ambient and Rank Growth](https://mlsanity.com/paper/2601.21873/) (2026)
- [Efficient Personalized Federated PCA with Manifold Optimization for IoT Anomaly Detection](https://mlsanity.com/paper/2602.12622/) (2026)
- [Synthetic Nearest Neighbors: Extending Synthetic Controls for Matrix Completion with Missing Not at Random Data](https://mlsanity.com/paper/2609.13586/) (2026)
- [Nuclear Norm-Regularized Bayesian Matrix Completion](https://mlsanity.com/paper/2609.30078/) (2026)

## Abstract (arXiv)

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.