mlsanityData to 7 Oct 2026

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

arXiv 2001.05484 ↗First posted 15 Jan 2020stat.ML cs.IT cs.LGcited by 23

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 3; 2023: 4; 2024: 5; 2025: 1; 2026: 4.

23 papers.

Sort:

By area:

  1. 2021Inference for Heteroskedastic PCA with Missing Datacited by 21
  2. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 21
  3. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  4. 2022Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descentcited by 11
  5. 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
  6. 2024Low-Rank Contextual Reinforcement Learning from Heterogeneous Human Feedbackcited by 10
  7. 2023Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCAcited by 7
  8. 2022Non-Asymptotic Guarantees for Robust Statistical Learning under Infinite Variance Assumptioncited by 6
  9. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  10. 2021Learning Treatment Effects in Panels with General Intervention Patternscited by 5
  11. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  12. 2022Robust Matrix Completion with Heavy-tailed Noisecited by 4
11 more
  1. 2023Exact Recovery for System Identification with More Corrupt Data than Clean Datacited by 2
  2. 2021Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recoverycited by 1
  3. 2024Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functionscited by 1
  4. 2024Exact Recovery Guarantees for Parameterized Nonlinear System Identification Problem under Sparse Disturbances or Semi-Oblivious Attackscited by 1
  5. 2024Heterogeneous Treatment Effects in Panel Datacited by 0
  6. 2024Alternating minimization for square root principal component pursuitcited by 0
  7. 2025RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guaranteescited by 0
  8. 2026Low-Rank Plus Sparse Matrix Transfer Learning under Growing Representations and Ambient Dimensionscited by 0
  9. 2026Efficient Personalized Federated PCA with Manifold Optimization for IoT Anomaly Detectioncited by 0
  10. 2026Synthetic Nearest Neighbors: Extending Synthetic Controls for Matrix Completion with Missing Not at Random Datacited by 0
  11. 2026Nuclear Norm-Regularized Bayesian Matrix Completioncited by 0