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-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. |
Year | Venue | Field |
---|---|---|
2017 | arXiv: Learning | Data point,Subspace topology,Pattern recognition,Iterative method,Outlier,Quadratic equation,Artificial intelligence,Thresholding,Gaussian noise,Machine learning,Mathematics,Computational complexity theory |
DocType | Volume | Citations |
Journal | abs/1702.05571 | 1 |
PageRank | References | Authors |
0.35 | 6 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yeshwanth Cherapanamjeri | 1 | 17 | 4.51 |
Prateek Jain | 2 | 256 | 16.85 |
Praneeth Netrapalli | 3 | 674 | 34.41 |