Smoothed Outliers and the Dimension Barrier in Robust Subspace Recovery

Robust subspace recovery means finding the low-dimensional plane that most of the data lies on when some points are arbitrary outliers. Ordinary principal component analysis (PCA) fails at this task because a few distant points can drag its answer anywhere. Current efficient methods succeed only when the inliers outnumber the outliers by a factor that grows with the plane's dimension $d$. Meanwhile, an exhaustive and computationally intractable search needs only a constant factor. The known constructions that force this linear-in-$d$ requirement all use outliers placed with exact precision, for example packed onto a competing plane. We propose to test whether this "dimension barrier" is a real feature of the problem or an artifact of such finely tuned configurations. The test is smoothed analysis: the adversary still chooses where the outliers go, but each chosen point is then jittered by a small amount of Gaussian noise before the algorithm sees it.

Our hypothesis is that the jitter does two things. First, it lowers the inlier-to-outlier ratio needed for recovery from order $d$ toward a constant, at a rate governed by the noise scale. Second, and this is the mechanism, it removes the flat and spurious stationary points that the aligned outliers create on the space of candidate planes. Once those are gone, simple noise-injected gradient descent started at random can find the true plane without the careful spectral or sorting-based initializations that every current efficient method depends on. If the hypothesis is right, it explains why these methods work far better in practice than their worst-case bounds predict. If it is wrong, we will have shown that the barrier survives noise, which is itself a useful negative result.

Core Claim

We make one claim with two halves. The first is a threshold claim. Maunu and Lerman, in Robust Subspace Recovery with Adversarial Outliers, project data onto the unit sphere so that no single outlier has unbounded pull (they call this "spherizing"). They then run geodesic gradient descent on the Grassmannian, the manifold of $d$-dimensional planes, and prove exact recovery when $\mathrm{SNR} > \sqrt{3}\,d\,\kappa_d$. Here SNR is the inlier-to-outlier ratio and $\kappa_d$ is a spherical condition number that measures how concentrated the outliers are along any $d$-dimensional direction. We conjecture that this bound becomes much weaker once the outliers are smoothed. Write $\kappa_d(\sigma)$ for the same condition number when each adversarial outlier $x_j$ is observed as $x_j + \sigma g_j$, with $g_j$ standard Gaussian in the ambient dimension $D$. We expect $\kappa_d(\sigma)$ to shrink roughly like $d/D$ times a term that decays in $\sigma$, because Gaussian jitter spreads each outlier's spherized mass over all $D$ directions instead of the adversary's chosen $d$. If so, the effective requirement falls from $\Theta(d)$ toward $O(1)$ once $\sigma$ exceeds a scale we will characterize.

The second half is a landscape claim. Take a smoothed least-absolute-deviation objective on spherized data, where $\mathrm{dist}_\delta$ is a convolution-smoothed distance with bandwidth $\delta$:

$$F_\delta(V) = \sum_{i=1}^{n} \mathrm{dist}_\delta\!\left(\frac{x_i}{\|x_i\|},\ \mathrm{span}(V)\right)$$

Under $\sigma$-smoothed outliers, we claim that with high probability every stationary point of $F_\delta$ other than the true plane has a Riemannian Hessian with a clearly negative eigenvalue, bounded away from zero by an amount polynomial in $\sigma$. The three-region picture of Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization would then carry over from clean squared-loss factorization to the robust, outlier-contaminated setting.

Where This Sits

The closest existing work is Polynomial time guarantees for the Burer-Monteiro method. That paper applies smoothed analysis to a low-rank factorized form of semidefinite programs. It perturbs the cost and constraint matrices, shows that the spurious regions become negligibly small, and reports that perturbation with $\sigma = 0.2$ raised empirical success from roughly 50% to nearly 90% on hard instances. It motivates us but differs in three ways. It perturbs a convex program's data rather than an outlier configuration. It uses a smooth objective with no robust loss. And its guarantees require a second-order method, adaptive regularization with cubics. We smooth the adversary's outlier placements, work with a non-smooth robust loss, and target a first-order method.

Two papers supply our methods. The escape analysis for first-order methods comes from How to Escape Saddle Points Efficiently. It proves that gradient descent with occasional isotropic noise escapes strict saddles, meaning saddles with a strictly negative curvature direction, with only polylogarithmic dependence on dimension. The smoothing of the non-smooth loss comes from Smoothed Robust Phase Retrieval. That paper convolves an $L_1$ loss with a kernel to obtain a twice-differentiable surrogate with a benign landscape, but only for scalar phase retrieval. We move that construction onto the Grassmannian.

Low-Degree Method Fails to Predict Robust Subspace Recovery both motivates and constrains the proposal. It shows that anti-concentration, the property that random points rarely fall near low-dimensional sets, makes robust recovery easy even where formal hardness predictions say otherwise. But its algorithm enumerates subsets and costs $O(\binom{m}{d+1})$. Gaussian smoothing is a direct source of anti-concentration. Our question is whether a continuous first-order method can exploit the same property in polynomial time for large $d$.

We also take an important constraint seriously. Smoothing does not always help: 2-player Nash equilibria stay PPAD-hard under smoothed payoffs (Smoothed Complexity of 2-player Nash Equilibria), and training depth-3 networks stays hard under perturbation (Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy). The barrier could therefore survive noise, and our experiments are designed to detect that outcome.

Research Program

The theoretical program has three steps.

The first step is a bound on the smoothed spherical condition number $\kappa_d(\sigma)$ for an arbitrary adversarial outlier set. We would prove it using Gaussian anti-concentration of the projections of spherized points. The main technical difficulty is that spherizing is a nonlinear map applied after the noise.

The second step is to plug this bound into the recovery argument of Maunu and Lerman, which yields a smoothed recovery threshold.

The third step is a landscape analysis of $F_\delta$. We would classify its stationary points into three groups: points near the true plane, where the objective is locally strongly convex; points near "decoy" planes formed by aligned outliers, which we expect to become strict saddles; and everything else, where we expect the gradient to be large. We would then combine this classification with the escape bound of Jin et al. to get an end-to-end iteration count for perturbed Riemannian gradient descent from random initialization. The competing requirements between the loss bandwidth $\delta$, the outlier noise $\sigma$, and the sample size must be made explicit. Zheng and Xue already found that small bandwidth demands more samples.

The empirical program builds a suite of adversarial outlier configurations. It includes outliers packed onto a competing $d'$-dimensional plane, collinear clusters, and outliers concentrated near but off the true plane. Each configuration is swept over noise scales $\sigma$. At every stationary point that an algorithm reaches, we measure the smallest Hessian eigenvalue directly with Hessian-vector products, as in Finding Approximate Local Minima for Nonconvex Optimization in Linear Time. This makes the "flat saddle becomes strict saddle" mechanism observable, in the same way the lifting paper reports the curvature at a spurious point moving from 2.67 to −0.17 (Over-parametrization via Lifting for Low-rank Matrix Sensing).

Baselines

The naive reference is ordinary PCA through a truncated SVD, together with PCA on spherized data. Both show how much of any gain comes from robustness at all. Every method in the comparison sees the same data matrices, the same random seeds, the same wall-clock budget per instance, and the same grid search over its own hyperparameters, with selection done on a held-out set of instances.

The strongest competitor on the threshold question is spherical geodesic gradient descent from spherical-PCA initialization (Robust Subspace Recovery with Adversarial Outliers). It is the method whose proven $\sqrt{3}\,d\,\kappa_d$ condition we aim to beat, and the same paper cites Outlier Pursuit as needing constants up to $121d$ and a modified RANSAC as needing $\mathrm{SNR} \ge cd$. These are proven thresholds, not measured ones. We found no reported empirical phase-transition curve on Lacuna for any of these methods on the Haystack model. We will therefore measure all of them ourselves.

The second strong competitor is the Subspace-Constrained Tyler's Estimator initialized by Tyler's M-estimator (Theoretical Guarantees for the Subspace-Constrained Tyler's Estimator). It already succeeds in a regime conjectured to be hard, with $\delta_S < 1$, so it is the method most likely to make our smoothing unnecessary.

We also include three further baselines. The first is trimmed reconstruction error over the Stiefel manifold, known as TRPCA (Robust PCA: Optimization of the Robust Reconstruction Error over the Stiefel Manifold). The second is factorized projected gradient descent with sorting-based initialization (Fast Algorithms for Robust PCA via Gradient Descent). The third is convex principal component pursuit, which separates the data into a low-rank part and a sparse part (Stable Principal Component Pursuit). We include pursuit only at sizes where it runs.

To beat the strongest baseline, our method must satisfy three conditions at matched compute. Its SNR at 50% recovery success must grow sublinearly in $d$ under smoothed outliers, while SGGD's grows linearly. Its success rate from random initialization must be at least as high as SGGD's rate from spectral initialization. And it must not lose to STE in any cell of the sweep.

The key ablations remove one ingredient at a time: the injected escape noise, which gives plain Riemannian gradient descent; the loss smoothing, which gives the raw $L_1$ loss with subgradients; the random initialization, which is replaced by spectral initialization; and the adversary-side smoothing, which is set to $\sigma = 0$.

Why not just…?

Why not just use a careful initialization, as every current method does? Yi et al. acknowledge a gap between the corruption level their initialization tolerates and the information-theoretic limit. Lerman and Yu show that STE fails when its initialization lands outside the basin of attraction. Initialization therefore patches the landscape without explaining it. The initialization ablation measures directly whether random initialization matches spectral initialization under smoothing. If spectral initialization still dominates, the landscape half of our claim is false, and we will report that.

Why not just add noise to the data yourself before running the algorithm? This is a real threat, and it is not the same as a smoothed adversary. Noise added by the learner also blurs the inliers, so exact recovery becomes impossible. It also cannot undo alignment that is already present in the outliers the learner receives. We will run learner-injected noise as a separate arm. If it recovers most of the threshold improvement at acceptable accuracy loss, the practical recommendation becomes "inject noise," and the theory reframes accordingly.

Why not just treat smoothed outliers as generic outliers, which the Haystack model already covers? When $\sigma$ is large, smoothed outliers do become Haystack-like and easy, so any result at large $\sigma$ is trivial. The contribution lies in how the threshold scales at small $\sigma$, where the outliers are still mostly aligned. Our sweep reports the threshold as a function of both $\sigma$ and $d$. A result that appears only when $\sigma$ is comparable to the norm of the data would count as a failure of the claim.

Why not just use the anti-concentration subset search? It already exploits the right property, but its $O(\binom{m}{d+1})$ cost limits it to small $d$ (Low-Degree Method Fails to Predict Robust Subspace Recovery). We run it for $d \le 4$ as an accuracy ceiling and ask whether our method approaches that ceiling at a small fraction of the runtime.

Proposed Experiments

The primary experiment is a phase-transition study on the Haystack and Generalized Haystack models used by Maunu and Lerman and by Lerman and Yu. We sweep $d$ from 2 to 64, ambient dimension up to $D = 1000$, several adversarial configurations, and $\sigma$ from 0 up to a moderate fraction of the data norm. The metric is the principal-angle distance to the true plane. For each method we report the SNR at which recovery succeeds half the time, plotted against $d$. The decisive check is whether the slope of that curve on log-log axes stays near 1 at $\sigma = 0$ and drops substantially for moderate $\sigma$. At each stationary point that is reached, we also record the smallest Hessian eigenvalue. Consistently negative values at decoy planes would confirm the mechanism, and near-zero values would refute it.

The secondary experiments use data sets where the outliers are structured rather than drawn from a model. On USPS and MNIST, we plant digits of one class as inliers and choose outliers adversarially from another class, projected onto a decoy plane, then smoothed. TRPCA was reported there to keep lower trimmed reconstruction error than its competitors, but no numerical value is reported on Lacuna for TRPCA on USPS or MNIST. On the Water surface, Restaurant, and ShoppingMall background-subtraction videos, we compare separation quality and runtime. The reported reference points are TRPCA at about 64 seconds versus over 232,000 seconds for LLD on Water surface, and factorized gradient descent reportedly giving cleaner separation when only 20% of pixels are observed. No quantitative accuracy figure for these videos was found on Lacuna.

On real data, the decisive question is whether random-start perturbed descent on the smoothed loss matches the carefully initialized methods. A negative answer on real data, together with a positive answer on smoothed synthetic data, would tell us that real outliers are more aligned than Gaussian smoothing captures. That finding would matter for how beyond-worst-case models should be built.