Abstract

We propose a new method for robust PCA – the task of recovering a low-rank matrix from sparse corruptions that are of unknown value and support. Our method involves alternating between projecting appropriate residuals onto the set of lowrank matrices, and the set of sparse matrices; each projection is non-convex but easy to compute. In spite of this non-convexity, we establish exact recovery of the low-rank matrix, under the same conditions that are required by existing methods (which are based on convex optimization).
For an m×n input matrix (m n), our method has a running time of per iteration, and needs iterations to reach an accuracy of . This is close to the running times of simple PCA via the power method, which requires O (rmn) per iteration, and iterations. In contrast, the existing methods
for robust PCA, which are based on convex optimization, have complexity per iteration, and take iterations, i.e., exponentially more iterations for the same accuracy. Experiments on both synthetic and real data establishes the improved speed and accuracy of our method over existing convex implementations.Keywords: Robust PCA, matrix decomposition, non-convex methods, alternating projec-tions.