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.


We provide the matlab source code for our algorithm. [Download]


Fast Algorithms for Robust PCA via Gradient Descent,
Xinyang Yi, Dohyung Park, Yudong Chen, Constantine Caramanis
To appear in Neural Information Processing Systems Conference (NIPS), 2016.


Our algorithm can be applied to the problem of separating the static background from the moving foreground in a video.

1. Original video
2. Sub-sampled video
3. Separation results using our algorithm: background, foreground