Bridging Convex and Nonconvex Optimization in Robust PCA: Noise,
  Outliers, and Missing Data
  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 $\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.
