Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2014 | public
Book Section - Chapter

Provable Non-convex Robust PCA

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 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(r²mn) per iteration, and needs O (log(1/ϵ)) 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 O(log(1/ϵ)) iterations. In contrast, the existing methods for robust PCA, which are based on convex optimization, have O(m²n) complexity per iteration, and take O(1/ϵ) iterations, i.e., exponentially more iterations for the same accuracy.

Additional Information

AA and UN would like to acknowledge NSF grant CCF-1219234, ONR N00014-14-1-0665, and Microsoft faculty fellowship. SS would like to acknowledge NSF grants 1302435, 0954059, 1017525 and DTRA grant HDTRA1-13-1-0024. PJ would like to acknowledge Nikhil Srivastava and Deeparnab Chakrabarty for several insightful discussions during the course of the project.

Additional details

Created:
August 20, 2023
Modified:
October 24, 2023