Provable Non-convex Robust PCA

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 low-rank 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 x n input matrix (m <= n), our method has a running time of O (r(2)mn) per iteration, and needs O (log(1/is an element of)) iterations to reach an accuracy of is an element of. This is close to the running times of simple PCA via the power method, which requires O (rmn) per iteration, and O (log(1/is an element of)) iterations. In contrast, the existing methods for robust PCA, which are based on convex optimization, have O (m(2)n) complexity per iteration, and take O (1/is an element of)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.