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.

本文提出了基于阈值的迭代算法，用于处理含有离群点的数据集中的偏差鲁棒主成分分析问题，该方法的迭代复杂度最多线性，可以处理至多α分数的离群点，并且对于一般噪声设置具有近乎最佳的计算复杂度。对于特殊情况，即噪声是加性高斯噪声，本文改进了该方法，并成功地减小了恢复误差。

基于阈值的高效异常值鲁棒主成分分析