  We consider the problem of outlier robust PCA (OR-PCA) where the goal is to
recover principal directions despite the presence of outlier data points. That
is, given a data matrix $M^*$, where $(1-\alpha)$ fraction of the points are
noisy samples from a low-dimensional subspace while $\alpha$ fraction of the
points can be arbitrary outliers, the goal is to recover the subspace
accurately. Existing results for \OR-PCA have serious drawbacks: while some
results are quite weak in the presence of noise, other results have runtime
quadratic in dimension, rendering them impractical for large scale
applications.
  In this work, we provide a novel thresholding based iterative algorithm with
per-iteration complexity at most linear in the data size. Moreover, the
fraction of outliers, $\alpha$, that our method can handle is tight up to
constants while providing nearly optimal computational complexity for a general
noise setting. For the special case where the inliers are obtained from a
low-dimensional subspace with additive Gaussian noise, we show that a
modification of our thresholding based method leads to significant improvement
in recovery error (of the subspace) even in the presence of a large fraction of
outliers.
