Theoretical Guarantees for the Subspace-Constrained Tyler's Estimator

Gilad Lerman, Feng YuarXiv 2024 · DOI · arXiv

Abstract

Robust Subspace Recovery (RSR) is a fundamental problem in computer vision and data science, often complicated by high outlier ratios. This paper provides the first rigorous theoretical analysis of the Subspace-Constrained Tyler’s Estimator (STE). We demonstrate that STE can achieve perfect subspace recovery even in the "computationally hard" regime where the inlier fraction falls below standard thresholds. By establishing guarantees for initialization, convergence rates, and noise stability, we show that STE, particularly when initialized with Tyler’s M-estimator (TME), offers a robust solution for high-dimensional data corrupted by significant noise.

Introduction

The goal of Robust Subspace Recovery (RSR) is to identify a low-dimensional linear structure within a dataset heavily contaminated by outliers. This task is critical for applications such as motion segmentation, face recognition, and fundamental matrix estimation. However, RSR faces a well-known "hardness" threshold: when the dimension-scaled Signal-to-Noise Ratio ($\delta_S$) is less than 1, the problem is conjectured to be NP-hard.

While Tyler’s M-estimator (TME) is a popular choice for robust estimation, its theoretical success is largely confined to the "easy" regime ($\delta_S > 1$). This paper analyzes the Subspace-Constrained Tyler’s Estimator (STE), a variant designed to bypass these limitations by iteratively constraining the search space to a specific $d$-dimensional manifold.

The Subspace-Constrained Tyler’s Estimator (STE)

STE differs from traditional M-estimators by restricting the shape matrix estimation to a $d$-dimensional subspace. The algorithm follows an iterative process:

  1. Initialization: An initial subspace estimate is provided (often via TME or PCA).
  2. Weighting: Data points are weighted based on their distance from the current subspace estimate.
  3. Constrained Update: The estimator updates the subspace by focusing exclusively on the top $d$ eigenvectors of the weighted covariance matrix.

This constraint acts as an aggressive filter against outliers. By restricting the optimization to a $d$-dimensional manifold, STE effectively reshapes the optimization landscape, allowing it to ignore outlier directions that would typically bias standard estimators.

Theoretical Framework

To evaluate STE, the authors employ three rigorous statistical models:

  • Noiseless Inlier-Outlier Model: Inliers reside perfectly on a subspace, while outliers are in general position.
  • Noisy Cone Model: Inliers are perturbed but remain within a narrow cone around the true subspace.
  • Generalized Haystack Model: A probabilistic model where outliers follow an anisotropic Gaussian distribution, providing a realistic simulation of structured noise.

The analysis utilizes Matrix Perturbation Theory and fixed-point analysis to track the evolution of the "initialization-dependent SNR" ($\kappa_1$) across iterations.

Key Results

Recovery in the Hard Regime

The primary contribution of this work is Theorem 3.1, which proves that STE can achieve exact recovery in the "hard" regime ($\delta_S < 1$). The condition for success is that the initialization must be sufficiently aligned with the true subspace. This suggests that while the global problem is hard, local convergence to the global optimum is guaranteed given a reasonable starting point.

Convergence and Stability

In noiseless scenarios, the angle between the estimated and true subspace is shown to vanish at an R-linear rate. Furthermore, Theorem 3.3 addresses the presence of noise. If inliers are corrupted by noise of level $\epsilon$, STE maintains stability, approximating the subspace with an error bound of $O(\sqrt{\epsilon})$.

Synergy with TME

A significant practical finding is the effectiveness of the TME+STE pipeline. Under the asymptotic generalized haystack model, there exists an "Intermediate Regime" where TME alone fails to recover the subspace but provides an initialization "good enough" for STE to succeed. This combination allows for robust recovery in high-outlier settings where neither method would suffice in isolation.

Discussion and Limitations

While STE provides a powerful tool for RSR, its performance is inherently tied to its initialization. If the initial guess is too far from the ground truth, the algorithm may converge to a local minimum. Additionally, the constants used in the theoretical guarantees are not yet "sharp," suggesting that STE's practical performance may exceed the current theoretical bounds.

Future research may focus on automated selection of the shrinkage parameter $\gamma$ and extending these guarantees to multi-subspace recovery or robust tensor decomposition.

Summary updated

Abstract

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. 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.
BibTeX
@misc{lerman2024theoretical,
  author = {Gilad Lerman and Feng Yu},
  title = {{Theoretical Guarantees for the Subspace-Constrained Tyler's Estimator}},
  year = {2024},
  eprint = {2403.18658},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.18658},
}
Figure