FMS-DS Solves a Decades-Old Math Problem in Outlier-Resistant Data Recovery
A new theoretical result shows a popular iterative algorithm reliably recovers subspaces from corrupted data, no matter how badly it is initialized.
- New paper proves IRLS with dynamic smoothing converges linearly to the true subspace from any initialization.
- Covers both linear and affine subspace recovery, the latter being the first such theoretical guarantee.
- First global convergence result for nonconvex IRLS on a Riemannian manifold (the Grassmannian).
- FMS-DS variant uses a shrinking epsilon to escape saddle points before sharpening to exact recovery.
- Experiments match or beat TME, STE, RANSAC on synthetic data, and improve low-dim neural network training on CIFAR and Tiny ImageNet.
- Paper on arXiv; authors from University of Minnesota, UCF, and Brandeis.
Robust subspace recovery (RSR) estimates a low-dimensional structure from data contaminated by arbitrary outliers. In a new paper, Gilad Lerman, Kang Li, Tyler Maunu, and Teng Zhang prove that a dynamically smoothed variant of Iteratively Reweighted Least Squares (IRLS) converges to the underlying subspace from any initialization, provided the data satisfy deterministic geometric conditions. The convergence rate is linear, meaning the estimation error decreases geometrically across iterations.
The result supplies a guarantee that had been missing from a widely used optimization method. IRLS performs well empirically, yet its nonsmooth objective, singular weights, and saddle points had prevented a proof covering arbitrary starting points. The authors describe their result as the first global convergence guarantee for IRLS in RSR and for nonconvex IRLS optimization on a Riemannian manifold. They also extend the analysis to affine subspaces.
Why outliers overpower PCA
Given observations in an ambient space ℝD, RSR seeks a d-dimensional subspace that explains the inliers while resisting outliers. Principal component analysis minimizes squared residuals, so a few distant observations can dominate its objective and rotate the estimated subspace away from the inliers.
A robust alternative minimizes the sum of residual norms, an ℓ1-style objective that gives extreme observations less leverage. That objective is nonsmooth when a residual reaches zero and nonconvex over the Grassmann manifold, the set of all d-dimensional subspaces in ℝD. Multiple orthonormal matrices can represent the same subspace, which makes ordinary Euclidean optimization theory insufficient.
The fast median subspace algorithm, or FMS, applies IRLS through a repeated sequence:
- Measure residuals. Compute each point’s distance from the current subspace.
This story is for Pro members
You've reached the end of the free preview. Upgrade to AlphaSignal Pro to read the full article - and everything else behind the paywall.
Comments
