# Theoretical Guarantees for the Subspace-Constrained Tyler's Estimator

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 30 references that are in the map.
- First posted on arXiv 27 Mar 2024.

## Builds on (most cited first, 4 of 4)

- [An Overview of Robust Subspace Recovery](https://mlsanity.com/paper/1803.01013/) (2018)
- [Fast, Robust and Non-convex Subspace Recovery](https://mlsanity.com/paper/1406.6145/) (2014)
- [A Well-Tempered Landscape for Non-convex Robust Subspace Recovery](https://mlsanity.com/paper/1706.03896/) (2017)
- [Robust Subspace Recovery with Adversarial Outliers](https://mlsanity.com/paper/1904.03275/) (2019)

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

- [A Subspace-Constrained Tyler's Estimator and its Applications to Structure from Motion](https://mlsanity.com/paper/2404.11590/) (2024)
- [Cycle-Sync: Robust Global Camera Pose Estimation through Enhanced Cycle-Consistent Synchronization](https://mlsanity.com/paper/2511.02329/) (2025)
- [Unsupervised Feature Selection via Robust Autoencoder and Adaptive Graph Learning](https://mlsanity.com/paper/2512.18720/) (2025)

## Abstract (arXiv)

This work analyzes the subspace-constrained Tyler's estimator (STE), a method designed to recover a low-dimensional subspace from a dataset that may be heavily corrupted by outliers. The STE has previously been shown to be competitive for fundamental computer vision problems. We assume a weak inlier-outlier model and allow the inlier fraction to fall below the threshold at which robust subspace recovery becomes computationally hard. We show that, in this setting, if the initialization of STE satisfies a certain condition, then STE, which is computationally efficient, can effectively recover the underlying subspace. To demonstrate the usefulness of this result, we use a common setting in the theoretical computer science community, whose special case is when the inliers are sampled from a Gaussian distribution and there are no restrictions on the outliers. We show that in this setting, with high probability, STE initialized by a polynomial algorithm exactly recovers the underlying subspace with linear convergence. Furthermore, we establish approximate recovery guarantees for STE in the presence of noisy inliers. Finally, under the asymptotic generalized haystack model, we demonstrate that STE initialized with Tyler's M-estimator (TME) recovers the subspace even when the inlier fraction is too small for TME to succeed on its own.