Fast Algorithms for Robust PCA via Non-convex Gradient Descent

We consider the problem of Robust PCA in the partially observed setting. Without corruptions, this is the well-known matrix completion problem. We present and analyze a non-convex optimization approach that greatly reduces the computational complexity of the above problems, compared to the best available algorithms. In particular, with $r$ denoting rank and $d$ dimension, we show the complexity of our algorithm is no more than $O(r^4d \log d \log(1/\varepsilon))$. In the setting where $r$ is small compared to $d$, our algorithm allows for near-linear-in-$d$ run-time.

Code

Paper

Videos