# List Decodable Subspace Recovery

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2020.

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

- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Privately Learning Mixtures of Axis-Aligned Gaussians](https://mlsanity.com/paper/2106.02162/) (2021)
- [List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering](https://mlsanity.com/paper/2206.05245/) (2022)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [List-Decodable Covariance Estimation](https://mlsanity.com/paper/2206.10942/) (2022)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)
- [A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm](https://mlsanity.com/paper/2305.00966/) (2023)
- [Robust Mixture Learning when Outliers Overwhelm Small Groups](https://mlsanity.com/paper/2407.15792/) (2024)
- [Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity](https://mlsanity.com/paper/2202.04020/) (2022)
- [A Combinatorial Approach to Robust PCA](https://mlsanity.com/paper/2311.16416/) (2023)

## Abstract (arXiv)

Learning from data in the presence of outliers is a fundamental problem in statistics. In this work, we study robust statistics in the presence of overwhelming outliers for the fundamental problem of subspace recovery. Given a dataset where an α fraction (less than half) of the data is distributed uniformly in an unknown k dimensional subspace in d dimensions, and with no additional assumptions on the remaining data, the goal is to recover a succinct list of O(frac1α) subspaces one of which is nontrivially correlated with the planted subspace. We provide the first polynomial time algorithm for the 'list decodable subspace recovery' problem, and subsume it under a more general framework of list decoding over distributions that are "certifiably resilient" capturing state of the art results for list decodable mean estimation and regression.