  We study principal component analysis (PCA), where given a dataset in
$\mathbb{R}^d$ from a distribution, the task is to find a unit vector $v$ that
approximately maximizes the variance of the distribution after being projected
along $v$. Despite being a classical task, standard estimators fail drastically
if the data contains even a small fraction of outliers, motivating the problem
of robust PCA. Recent work has developed computationally-efficient algorithms
for robust PCA that either take super-linear time or have sub-optimal error
guarantees. Our main contribution is to develop a nearly-linear time algorithm
for robust PCA with near-optimal error guarantees. We also develop a
single-pass streaming algorithm for robust PCA with memory usage nearly-linear
in the dimension.
