Fast Algorithms for Robust PCA via Gradient Descent
We consider the problem of Robust PCA in the fully and partially observed settings. Without corruptions, this is the well known matrix completion problem. From a statistical standpoint this problem has been recently well studied, and conditions on when recovery is possible (how many observations do we need, how many corruptions can we tolerate) via polynomial time algorithms is by now understood. This paper presents and analyzes a non convex optimization approach that greatly reduces the computational complexity of the above problems, compared to the best available algorithms. In particular, in the fully observed case, with $r$ denoting rank and $d$ dimension, we reduce the complexity from \mathcal{O}(r^2d^2\log(1/\varepsilon) to \mathcal{O}(rd^2\log(1/\varepsilon) a big savings when the rank is big. For the partially observed case, we show the complexity of our algorithm is no more than \mathcal{O}(r^4d \log d \log(1/\varepsilon) Not only is this the best known run time for a provable algorithm under partial observation, but in the setting where $r$ is small compared to $d$ it also allows for near linear in $d$ run time that can be exploited in the fully observed case as well, by simply running our algorithm on a subset of the observations.
NIPS