New proof pinpoints exact threshold for Tyler's M-Estimator in subspace recovery
A decade-old boundary between solvable and hard subspace recovery problems is finally resolved.
Robust Subspace Recovery (RSR) is a fundamental problem in high-dimensional statistics and machine learning: find a low-dimensional subspace that captures the true signal when the dataset is heavily contaminated by outliers. Prior work established a computational hardness threshold based on the dimension-scaled signal-to-noise ratio (DS-SNR). When DS-SNR < 1, the problem is SSE-hard (likely intractable for efficient algorithms). When DS-SNR > 1, practical algorithms succeed under 'general position' assumptions. But the exact behavior at the critical boundary DS-SNR = 1 remained unknown for over a decade.
In this paper, Gilad Lerman and Teng Zhang resolve the boundary case for Tyler's M-Estimator (TME), a popular robust algorithm. They prove that TME converges exactly to the true subspace for DS-SNR ≥ 1 under a newly introduced stability condition that is strictly less restrictive than the general position assumptions used in prior work. The proof uses a majorization-minimization framework to decompose the TME iterates. This sharp phase transition provides both theoretical closure and practical guidance: practitioners can now know precisely when TME will work and when it will fail, enabling more reliable subspace recovery in applications like computer vision, sensor networks, and financial data analysis.
- Sharp threshold at DS-SNR = 1: below it the problem is SSE-hard, above it TME converges.
- New stability condition for TME is less restrictive than previous general position assumptions.
- Proof uses a majorization-minimization decomposition of TME iterates; first rigorous analysis at the critical boundary.
Why It Matters
Provides a mathematically exact guarantee for robust subspace recovery, enabling reliable high-dimensional data analysis with outliers.