@inproceedings{cherapanamjeri2017thresholding,
author = {Cherapanamjeri, Yeshwanth and Jain, Prateek and Netrapalli, Praneeth},
title = {Thresholding Based Efficient Outlier Robust PCA},
booktitle = {COLT-2017},
year = {2017},
month = {February},
abstract = {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 - cx) fraction of the points are noisy samples from a low-dimensional subspace while  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, , 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.},
url = {http://approjects.co.za/?big=en-us/research/publication/thresholding-based-efficient-outlier-robust-pca/},
edition = {COLT-2017},
}