# Fast, Robust and Non-convex Subspace Recovery

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2014.

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

- [A Subspace-Constrained Tyler's Estimator and its Applications to Structure from Motion](https://mlsanity.com/paper/2404.11590/) (2024)
- [Probabilistic Robust Autoencoders for Outlier Detection](https://mlsanity.com/paper/2110.00494/) (2021)
- [Unlabeled Principal Component Analysis and Matrix Completion](https://mlsanity.com/paper/2101.09446/) (2021)
- [Fun with Flags: Robust Principal Directions via Flag Manifolds](https://mlsanity.com/paper/2401.04071/) (2024)
- [Unveiling Multiple Descents in Unsupervised Autoencoders](https://mlsanity.com/paper/2406.11703/) (2024)
- [Stochastic and Private Nonconvex Outlier-Robust PCA](https://mlsanity.com/paper/2203.09276/) (2022)
- [LRANet++: Low-Rank Approximation Network for Accurate and Efficient Text Spotting](https://mlsanity.com/paper/2511.05818/) (2025)
- [A Riemannian ADMM](https://mlsanity.com/paper/2211.02163/) (2022)
- [Theoretical Guarantees for the Subspace-Constrained Tyler's Estimator](https://mlsanity.com/paper/2403.18658/) (2024)
- [Entropic Wasserstein Component Analysis](https://mlsanity.com/paper/2303.05119/) (2023)
- [Nested subspace learning with flags](https://mlsanity.com/paper/2502.06022/) (2025)
- [A Flag Decomposition for Hierarchical Datasets](https://mlsanity.com/paper/2502.07782/) (2025)
- [Robust Moment-Based Estimation via Spectral Gradient Reweighting](https://mlsanity.com/paper/2605.27718/) (2026)
- [Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search](https://mlsanity.com/paper/2106.12190/) (2021)
- [Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity](https://mlsanity.com/paper/2202.04020/) (2022)
- [Robust Projection based Anomaly Extraction (RPE) in Univariate Time-Series](https://mlsanity.com/paper/2205.15548/) (2022)
- [AdaContour: Adaptive Contour Descriptor with Hierarchical Representation](https://mlsanity.com/paper/2404.08292/) (2024)
- [RANSAC Revisited: An Improved Algorithm for Robust Subspace Recovery under Adversarial and Noisy Corruptions](https://mlsanity.com/paper/2504.09648/) (2025)
- [Unsupervised Feature Selection via Robust Autoencoder and Adaptive Graph Learning](https://mlsanity.com/paper/2512.18720/) (2025)
- [TriDE: Triangle-Consistent Translation Directions for Global Camera Pose Estimation](https://mlsanity.com/paper/2605.06889/) (2026)

## Abstract (arXiv)

This work presents a fast and non-convex algorithm for robust subspace recovery. The data sets considered include inliers drawn around a low-dimensional subspace of a higher dimensional ambient space, and a possibly large portion of outliers that do not lie nearby this subspace. The proposed algorithm, which we refer to as Fast Median Subspace (FMS), is designed to robustly determine the underlying subspace of such data sets, while having lower computational complexity than existing methods. We prove convergence of the FMS iterates to a stationary point. Further, under a special model of data, FMS converges to a point which is near to the global minimum with overwhelming probability. Under this model, we show that the iteration complexity is globally bounded and locally r-linear. The latter theorem holds for any fixed fraction of outliers (less than 1) and any fixed positive distance between the limit point and the global minimum. Numerical experiments on synthetic and real data demonstrate its competitive speed and accuracy.