# Robust Subspace Recovery with Adversarial Outliers

arXiv: https://arxiv.org/abs/1904.03275 · HTML: https://mlsanity.com/paper/1904.03275/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2019.

## Built on by (most cited first, 8 of 8)

- [A Subspace-Constrained Tyler's Estimator and its Applications to Structure from Motion](https://mlsanity.com/paper/2404.11590/) (2024)
- [Stochastic and Private Nonconvex Outlier-Robust PCA](https://mlsanity.com/paper/2203.09276/) (2022)
- [Unsupervised Anomaly Detection for Auditing Data and Impact of Categorical Encodings](https://mlsanity.com/paper/2210.14056/) (2022)
- [Theoretical Guarantees for the Subspace-Constrained Tyler's Estimator](https://mlsanity.com/paper/2403.18658/) (2024)
- [A Combinatorial Approach to Robust PCA](https://mlsanity.com/paper/2311.16416/) (2023)
- [RANSAC Revisited: An Improved Algorithm for Robust Subspace Recovery under Adversarial and Noisy Corruptions](https://mlsanity.com/paper/2504.09648/) (2025)
- [SNAP: A Self-Consistent Agreement Principle with Application to Robust Computation](https://mlsanity.com/paper/2602.02013/) (2026)
- [The Sharp Phase Transition of Tyler's M-Estimator for Robust Subspace Recovery](https://mlsanity.com/paper/2606.06782/) (2026)

## Abstract (arXiv)

We study the problem of robust subspace recovery (RSR) in the presence of adversarial outliers. That is, we seek a subspace that contains a large portion of a dataset when some fraction of the data points are arbitrarily corrupted. We first examine a theoretical estimator that is intractable to calculate and use it to derive information-theoretic bounds of exact recovery. We then propose two tractable estimators: a variant of RANSAC and a simple relaxation of the theoretical estimator. The two estimators are fast to compute and achieve state-of-the-art theoretical performance in a noiseless RSR setting with adversarial outliers. The former estimator achieves better theoretical guarantees in the noiseless case, while the latter estimator is robust to small noise, and its guarantees significantly improve with non-adversarial models of outliers. We give a complete comparison of guarantees for the adversarial RSR problem, as well as a short discussion on the estimation of affine subspaces.