Abstract
Robust PCA is the well known task of recovering a low rank matrix from measurements corrupted with sparse noise. A popular recovery method is convex relaxation, where the rank and sparsity constraints are replaced by their convex surrogates. This can provably recover the low rank and sparse components under natural constraints such as incoherence and sparsity. In this talk, I will describe how non-convex methods can provably solve the robust PCA problem and also match the guarantees for the convex method. At the same time, our non-convex method has significantly lower computational complexity, since it involves finding only low rank approximations of the observed matrix. Thus, non-convex methods can achieve best of both the worlds: guaranteed recovery and low computational complexity.
This is joint work with Praneeth Netrapalli, U N Niranjan, Prateek Jain, and Sujay Sanghavi.