Non-Convex Robust PCA
1,006 views · Published 22 June 2016 · 50:40 · Indexed 22 October 2026
Channel: Microsoft Research · 2016 · Science & Technology
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.
