Bridging convex and nonconvex optimization in robust PCA: Noise, outliers and missing data

Yuxin Chen, Jianqing Fan, Cong Ma, Yuling Yan

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


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 in the presence of 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.

Original languageEnglish (US)
Pages (from-to)2948-2971
Number of pages24
JournalAnnals of Statistics
Issue number5
StatePublished - Oct 2021

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


  • Convex relaxation
  • Leave-one-out analysis
  • Robust principal component analysis
  • ℓ guarantees


Dive into the research topics of 'Bridging convex and nonconvex optimization in robust PCA: Noise, outliers and missing data'. Together they form a unique fingerprint.

Cite this