Introduction
In high-dimensional data analysis, Principal Component Analysis (PCA) serves as the foundational tool for dimensionality reduction. However, PCA is notoriously sensitive to outliers; even a small number of corrupted data points can significantly skew the resulting subspace. Robust Subspace Recovery (RSR) addresses this by seeking the underlying low-dimensional structure while ignoring outliers. One of the most effective algorithms for this task is Iteratively Reweighted Least Squares (IRLS). While empirically successful and computationally efficient, IRLS has historically lacked a rigorous theoretical foundation for global convergence. This research bridges that gap, providing the first proof that a specific IRLS variant can converge globally and linearly to the correct solution on a Riemannian manifold.
The Challenge of Robustness
The RSR problem is often formulated as finding a $d$-dimensional subspace that minimizes the sum of distances to the data points. Unlike PCA, which minimizes squared distances, robust methods typically minimize absolute distances ($L_1$-like objectives). This change makes the objective function non-smooth and the optimization problem non-convex, particularly when defined over the Grassmannian manifold—the space of all possible $d$-dimensional subspaces.
Traditional IRLS approaches approximate this non-smooth objective by solving a sequence of weighted quadratic problems. However, these methods often require a "warm start" (a near-perfect initial guess) to guarantee convergence to the global optimum. Without such an initialization, the algorithm might stall at sub-optimal stationary points.
Dynamic Smoothing: The Key Innovation
The authors focus on the Fast Median Subspace (FMS) algorithm and introduce a crucial modification: Dynamic Smoothing (DS). To handle the non-smoothness of the objective, a smoothing parameter $\epsilon$ is typically added to the denominator of the weights to prevent them from reaching infinity when a point lies exactly on the subspace.
While a fixed $\epsilon$ leads to an approximate solution, the FMS-DS algorithm employs an adaptive schedule. The parameter $\epsilon$ starts large and decreases based on the $\gamma$-quantile of the distances between the data and the current subspace estimate. This dynamic adjustment ensures that the algorithm avoids getting trapped in local minima early in the process while eventually converging to the exact solution of the non-smooth problem.
Theoretical Breakthrough: Global and Linear Convergence
The primary contribution of this work is the mathematical proof of global convergence. Under specific deterministic conditions—essentially requiring that inliers are sufficiently spread out and outliers are not perfectly aligned—the authors demonstrate that FMS-DS converges to the true subspace from any random initialization on the Grassmannian manifold.
Furthermore, they establish that this convergence is linear, meaning the error decreases exponentially ($c^k$) with each iteration. This is a significant advancement over previous theories that only guaranteed local convergence or convergence to arbitrary stationary points.
Empirical Validation
The theoretical findings are supported by experiments across synthetic and real-world datasets:
- Synthetic Models: Using the "Generalized Haystack Model" and adversarial setups, the authors show that FMS-DS consistently recovers the true subspace where other methods fail. Notably, it outperforms RANSAC in high-dimensional settings, as RANSAC's computational cost scales poorly with dimensionality.
- Deep Learning Applications: The method was applied to neural network training (CIFAR-10, CIFAR-100, and Tiny ImageNet) using a technique called Deep Learning Dimensionality Reduction (DLDR). Because stochastic gradient noise in deep learning is often heavy-tailed, the robust nature of FMS-DS provides better generalization than standard PCA-based methods, especially in the presence of label corruption.
Conclusion and Future Directions
By introducing dynamic smoothing, this research provides a theoretical anchor for a widely used class of algorithms. It proves that global optimality in robust subspace recovery is achievable without specialized initialization.
Future work remains to extend the global convergence proof to the "noisy" case, where inliers do not lie exactly on the subspace but are perturbed by small amounts of noise. Additionally, while the algorithm has been extended to affine subspaces, the global convergence proof for that specific geometry remains an open challenge. Nevertheless, this work marks a major step forward in understanding the geometry of robust optimization.
Summary updated