# A Well-Tempered Landscape for Non-convex Robust Subspace Recovery

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2017.

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

- [Breaking the Curse of Dimensionality: Diffusion Models Efficiently Learn Low-Dimensional Distributions](https://mlsanity.com/paper/2409.02426/) (2024)
- [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)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Stochastic and Private Nonconvex Outlier-Robust PCA](https://mlsanity.com/paper/2203.09276/) (2022)
- [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022)
- [Riemannian Perspective on Matrix Factorization](https://mlsanity.com/paper/2102.00937/) (2021)
- [On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization](https://mlsanity.com/paper/2110.12121/) (2021)
- [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)
- [Nested subspace learning with flags](https://mlsanity.com/paper/2502.06022/) (2025)
- [A Robust Autoencoder Ensemble-Based Approach for Anomaly Detection in Text](https://mlsanity.com/paper/2405.13031/) (2024)
- [Boosting RANSAC via Dual Principal Component Pursuit](https://mlsanity.com/paper/2110.02918/) (2021)
- [Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension](https://mlsanity.com/paper/2201.09079/) (2022)
- [Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity](https://mlsanity.com/paper/2202.04020/) (2022)
- [RANSAC Revisited: An Improved Algorithm for Robust Subspace Recovery under Adversarial and Noisy Corruptions](https://mlsanity.com/paper/2504.09648/) (2025)
- [Simplifying Optimal Transport through Schatten-p Regularization](https://mlsanity.com/paper/2510.11910/) (2025)
- [The Sharp Phase Transition of Tyler's M-Estimator for Robust Subspace Recovery](https://mlsanity.com/paper/2606.06782/) (2026)

## Abstract (arXiv)

We present a mathematical analysis of a non-convex energy landscape for robust subspace recovery. We prove that an underlying subspace is the only stationary point and local minimizer in a specified neighborhood under a deterministic condition on a dataset. If the deterministic condition is satisfied, we further show that a geodesic gradient descent method over the Grassmannian manifold can exactly recover the underlying subspace when the method is properly initialized. Proper initialization by principal component analysis is guaranteed with a simple deterministic condition. Under slightly stronger assumptions, the gradient descent method with a piecewise constant step-size scheme achieves linear convergence. The practicality of the deterministic condition is demonstrated on some statistical models of data, and the method achieves almost state-of-the-art recovery guarantees on the Haystack Model for different regimes of sample size and ambient dimension. In particular, when the ambient dimension is fixed and the sample size is large enough, we show that our gradient method can exactly recover the underlying subspace for any fixed fraction of outliers (less than 1).