Timezone: »

 
Spotlight
Non-convex Robust PCA
Praneeth Netrapalli · Niranjan Uma Naresh · Sujay Sanghavi · Animashree Anandkumar · Prateek Jain

Wed Dec 10 07:10 AM -- 07:30 AM (PST) @ Level 2, room 210
in Spotlight Session 5: Regression and time series spotlights »
We propose a new provable method for robust PCA, where the task is to recover a low-rank matrix, which is corrupted with sparse perturbations. Our method consists of simple alternating projections onto the set of low rank and sparse matrices with intermediate de-noising steps. We prove correct recovery of the low rank and sparse components under tight recovery conditions, which match those for the state-of-art convex relaxation techniques. Our method is extremely simple to implement and has low computational complexity. For a $m \times n$ input matrix (say m \geq n), our method has O(r^2 mn\log(1/\epsilon)) running time, where $r$ is the rank of the low-rank component and $\epsilon$ is the accuracy. In contrast, the convex relaxation methods have a running time O(mn^2/\epsilon), which is not scalable to large problem instances. Our running time nearly matches that of the usual PCA (i.e. non robust), which is O(rmn\log (1/\epsilon)). Thus, we achieve ``best of both the worlds'', viz low computational complexity and provable recovery for robust PCA. Our analysis represents one of the few instances of global convergence guarantees for non-convex methods.

Author Information

Praneeth Netrapalli (Google Research)
Niranjan Uma Naresh (UC Irvine)
Sujay Sanghavi (UT-Austin)
Animashree Anandkumar (NVIDIA / Caltech)
Prateek Jain (Microsoft Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors