Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA
This addresses the problem of robust PCA for data analysts and machine learning practitioners, offering efficient solutions that improve upon previous computationally-inefficient or sub-optimal methods.
The paper tackles robust principal component analysis (PCA) in the presence of outliers by developing a nearly-linear time algorithm with near-optimal error guarantees, and also provides a single-pass streaming algorithm with memory usage nearly-linear in the dimension.
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.