Certifying optimality in nonconvex robust PCA

Abstract

Robust principal component analysis seeks to recover a low-rank matrix from fully observed data with sparse corruptions. A scalable approach fits a low-rank factorization by minimizing the sum of entrywise absolute residuals, leading to a nonsmooth and nonconvex objective. Under standard incoherence conditions and a random model for the corruption support, we study factorizations of the ground-truth rank-$r$ matrix with both factors of rank $r$. With high probability, every such factorization is a Clarke critical point. We also characterize the local geometry: when the factorization rank equals $r$, these solutions are sharp local minima; when it exceeds $r$, they are strict saddle points.