Non-Convex Robust PCA

In this lecture, we will illustrate a novel technique due to Erdos et al. (2011) which can be used to obtain bounds on eigenvector perturbation in the ℓ∞ norm. Standard techniques give us optimal bounds only for perturbation in the ℓ2 norm. We will further use this technique to propose and analyze a new non-convex algorithm for robust PCA, where the task is to recover a low-rank matrix from sparse corruptions that are of unknown value and support. In the deterministic error setting, our method achieves exact recovery under the same conditions that are required by existing methods (which are based on convex optimization) but is much faster.

Speaker Details

Praneeth Netrapalli is a POST DOC RESEARCHER at Microsoft Research. Earlier he was a PhD student in the ECE department at UT Austin, where he was advised by Prof. Sujay Sanghavi. His research focuses on designing and understanding practical algorithms for solving machine learning problems. He obtained MS from UT Austin, and B. Tech from IIT Bombay, both in Electrical Engineering. His prior experience includes two years as a quantitative analyst at Goldman Sachs where he worked on pricing and evaluating risk on complex financial products.

Date:
Speakers:
Praneeth Netrapalli
Affiliation:
Microsoft