@inproceedings{netrapalli2014non-convex,
author = {Netrapalli, Praneeth and Niranjan, U N and Sanghavi, Sujay and Anandkumar, Anima and Jain, Prateek},
title = {Non-convex Robust PCA},
booktitle = {Advances in Neural Information Processing Systems},
year = {2014},
month = {December},
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 low-rank matrices, and the set of sparse matrices; each projection is [\em 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 O(r2mn) per iteration, and needs O(log(1/ϵ)) iterations to reach an accuracy of ϵ. This is close to the running time of simple PCA via the power method, which requires O(rmn) per iteration, and O(log(1/ϵ)) iterations. In contrast, existing methods for robust PCA, which are based on convex optimization, have O(m2n) complexity per iteration, and take O(1/ϵ) 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.},
publisher = {Neural Information Processing Systems},
url = {http://approjects.co.za/?big=en-us/research/publication/non-convex-robust-pca/},
pages = {1107-1115},
}