The Vulnerability of Squared Errors
Imagine trying to fit a straight line through a cloud of data points. Standard techniques like Principal Component Analysis (PCA) do this by maximizing the variance of the projected data or, equivalently, minimizing the sum of squared residual distances ($\ell_2$-norm).
This reliance on squared errors is a major vulnerability. If a single data point is corrupted—due to a sensor glitch, a pixel occlusion, or background clutter—its distance from the true line might be large, say 100 units. When we square this error, its weight in the optimization objective becomes 10,000. This single outlier exerts massive leverage, dragging the estimated subspace away from the true underlying structure. As noted by Diego Klabjan et al. in Iteratively Reweighted Least Squares Algorithms for L1-Norm Principal Component Analysis, this quadratic penalty makes classical $\ell_2$ methods highly fragile when dealing with real-world, contaminated datasets.
The $\ell_1$-Norm Alternative: Subspace Medians
To tame the influence of outliers, we can replace the $\ell_2$-norm with an $\ell_1$-norm, minimizing absolute deviations instead of squared deviations. Geometrically, this shifts the problem from finding a mean subspace to finding a median subspace.
If an outlier is 100 units away from an $\ell_1$ candidate subspace, its penalty is simply 100. It cannot dominate the optimization. Gilad Lerman et al. demonstrate in An Overview of Robust Subspace Recovery that minimizing the sum of absolute distances acts as a geometric median, preventing distant corruptions from biasing the result. This "sum-of-distances" framework provides exceptional stability against heavy-tailed noise, ensuring that the low-dimensional representation remains aligned with the primary data distribution (Zhili Feng et al., Dimensionality Reduction for the Sum-of-Distances Metric).
Standard L2 PCA (Mean-based):
Outlier (Distance: 100) ---> Penalty: 10,000 (Massive leverage, pulls subspace)
Robust L1 PCA (Median-based):
Outlier (Distance: 100) ---> Penalty: 100 (Bounded leverage, ignored)
This resilience is highly valuable across computer vision and pattern recognition tasks. For example, Mohammed Bennamoun et al. utilize absolute differences to achieve robust subpixel alignment in the presence of noise (Generalized Closed-Form Formulae for Feature-Based Subpixel Alignment in Patch-Based Matching). Similarly, Weiwei Zhou et al. show that re-centering graph embedding frameworks within an $\ell_1$-norm space protects downstream recognition boundaries from being skewed by extreme artifacts (Improved Graph Embedding for Robust Recognition with outliers).
Two Formulations: Distance Minimization vs. Variance Maximization
In classical $\ell_2$ PCA, minimizing reconstruction error and maximizing projected variance yield the exact same subspace. However, when we switch to the $\ell_1$-norm, this mathematical equivalence breaks down. This creates two distinct ways to formulate robust PCA:
- Distance Minimization: Finding a subspace that minimizes the sum of absolute distances to the data points.
- Variance (Spread) Maximization: Finding a subspace that maximizes the sum of absolute values of the projected data.
Feiping Nie 0001 et al. focus on the variance maximization path in Robust Principal Component Analysis with Non-Greedy l1-Norm Maximization. They introduce a non-greedy optimization strategy that solves for all projection directions simultaneously, preserving rotation invariance and avoiding the local optima that plague greedy, step-by-step extraction methods.
Maximizing the $\ell_1$ spread is particularly effective when modeling deformable objects under severe occlusion. For instance, Justus Piater et al. use this formulation to track hands for sign language recognition, showing that it prevents unaligned background clutter from corrupting the learned basis vectors (Hand Modeling and Tracking for Video-Based Sign Language Recognition by Robust Principal Component Analysis). To handle even more complex data structures, such as multi-channel video tensors, Yang Liu et al. extend $\ell_1$ optimization to multilinear embeddings, avoiding the need to flatten structured data into vectors (Multilinear Maximum Distance Embedding Via L1-Norm Optimization).
The Dual Approach: Hunting the Orthogonal Complement
When the target subspace is high-dimensional (such as a hyperplane), finding its basis vectors directly can be computationally difficult. An alternative strategy is to search for its orthogonal complement—the normal vectors that are perpendicular to the subspace.
This is the core intuition behind Dual Principal Component Pursuit (DPCP). If a data point lies perfectly within a hyperplane, its dot product with the hyperplane's normal vector is exactly zero. If we project a dataset onto a candidate normal vector, the true inliers will map to zero, while outliers will map to non-zero values.
Inliers lie ON the hyperplane ---> Dot product with normal vector = 0
Outliers lie OFF the hyperplane ---> Dot product with normal vector ≠ 0
DPCP Objective: Minimize ∑ |x_i · v| subject to ||v|| = 1
By minimizing the $\ell_1$-norm of these projections subject to a unit-sphere constraint, DPCP forces the candidate vector to align with the true normal direction. Manolis C. Tsakiris et al. demonstrate in Hyperplane Clustering via Dual Principal Component Pursuit that this dual formulation remains highly effective even when outliers comprise up to half of the dataset.
Further theoretical analysis by Zhihui Zhu et al. reveals that DPCP can tolerate an extreme number of outliers—scaling quadratically relative to the number of inliers ($O(N^2)$)—while maintaining linear convergence speeds (Dual Principal Component Pursuit: Improved Analysis and Efficient Algorithms). Rather than searching for normal vectors sequentially, Tianyu Ding et al. extended this framework to a holistic version that recovers the entire orthogonal basis simultaneously, providing strong recovery guarantees for both noiseless and noisy data regimes (Dual Principal Component Pursuit for Robust Subspace Learning: Theory and Algorithms for a Holistic Approach).
Streaming and Online Subspace Estimation
In many real-world applications, data arrives as a continuous stream, making batch optimization over the entire dataset impossible due to memory and latency constraints. To address this, researchers have developed online and streaming variants that update the robust subspace on the fly.
Early work by Jongwoo Lim et al. demonstrated that incorporating robust error norms into sequential subspace updates allows visual trackers to adapt to changing illumination and poses while ignoring transient occlusions (Incremental Learning for Visual Tracking). For complex data distributions lying on multiple linear structures, Arthur Szlam et al. introduced the Median K-flats (MKF) algorithm (Median K-flats for hybrid linear modeling with many outliers). By minimizing $\ell_1$ distances rather than $\ell_2$ errors during the online clustering process, MKF accurately isolates multiple underlying flats while maintaining a tiny memory footprint (see also Teng Zhang et al., Hybrid Linear Modeling via Local Best-Fit Flats.).
To provide rigorous theoretical guarantees in streaming environments, John Goes et al. developed Robust Stochastic PCA using Matrix Exponentiated Gradient (MEG) updates (Robust Stochastic Principal Component Analysis). Their method achieves sub-linear convergence and successfully recovers low-dimensional patterns even when up to 80% of the incoming stream is corrupted. Similarly, Teodor Vanislavov Marinov et al. proved that replacing standard variance maximization with absolute subspace deviation models bounds the influence of extreme values, ensuring stable streaming estimation under non-Gaussian noise (Streaming Principal Component Analysis in Noisy Settings).
Alternative Geometries and Modern Dualities
Robust subspace estimation can also be viewed through the lens of manifold geometry and advanced optimization dualities.
Instead of treating subspace estimation as an optimization problem in Euclidean space, Aasa Feragen et al. reformulate it as an averaging problem on the Grassmann manifold—the parameter space of all linear subspaces (Grassmann Averages for Scalable Robust PCA). By computing "trimmed" averages based on the absolute values of projections, their Grassmann Average (GA) framework achieves high scalability on massive datasets without requiring complex convex optimization solvers.
Euclidean Optimization:
Find matrix U that minimizes ∑ ||x_i - U U^T x_i||_1
Grassmann Manifold Optimization:
Find a point (subspace) on the manifold that represents the robust "median" of the data
More recently, Jan Quan et al. revisited the core PCA objective using Difference-of-Convex (DC) duality (Rethinking PCA Through Duality). Their dual formulation provides an important practical benefit: out-of-sample applicability. Historically, many robust PCA methods required re-optimizing the entire objective when new data arrived. The DC duality framework allows new points to be projected directly onto the learned robust subspace.
This out-of-sample capability mirrors supervised settings like video background estimation. As shown by Aritra Dutta et al. in Online and Batch Supervised Background Estimation via L1 Regression, when incoming test frames are projected onto a pre-defined subspace basis via $\ell_1$ regression, the static background is accurately reconstructed, while moving foreground objects are cleanly isolated as sparse outliers.
As synthesized by Thierry Bouwmans et al., the shift from quadratic $\ell_2$ metrics to linear-like $\ell_1$ objectives represents a foundational transition in signal processing, enabling models to preserve underlying low-dimensional structures across highly corrupted, high-dimensional, and streaming environments (Introduction to the Issue on Robust Subspace Learning and Tracking: Theory, Algorithms, and Applications).
Key Foundational Work
A New Algorithm for Estimating the Effective Dimension-Reduction Subspace (2008) — contributed 1 concept elements to this direction.
Incremental Learning for Visual Tracking (2004) — contributed 1 concept elements to this direction.