Abstract
Principal Component Analysis (PCA) is a fundamental technique for dimensionality reduction, yet its reliance on the $\ell_2$ norm makes it highly susceptible to outliers. This paper introduces REAPER, a convex optimization framework that robustly recovers linear subspaces from data contaminated by adversarial noise. By relaxing the non-convex problem of orthogonal $\ell_1$ regression into a convex program, REAPER provides a computationally efficient approach with rigorous theoretical guarantees. We demonstrate its effectiveness on both synthetic datasets and real-world facial recognition tasks, where it outperforms traditional methods even when outliers constitute over 90% of the observations.
Introduction
In fields ranging from computer vision to bioinformatics, high-dimensional data often resides on low-dimensional linear subspaces. While PCA is the standard tool for identifying these structures, its sensitivity to outliers—where a single extreme value can significantly bias the model—limits its utility in noisy environments. Orthogonal $\ell_1$ regression offers a robust alternative by minimizing the sum of unsquared residuals, but it typically results in a non-convex optimization problem that is difficult to solve globally. REAPER addresses this challenge through a clever convex relaxation, enabling reliable subspace recovery in high-dimensional spaces.
Methodology
The core of REAPER lies in parameterizing subspaces through orthogonal projector matrices. In a standard setting, such a matrix must have eigenvalues of exactly 0 or 1, a constraint that induces non-convexity. REAPER relaxes this requirement, allowing eigenvalues to reside in the continuous interval $[0, 1]$. This transformation maps the problem onto the convex hull of rank-$d$ orthoprojectors, making it amenable to global optimization.
To solve the resulting convex program, the authors propose an Iteratively Reweighted Least Squares (IRLS) algorithm. This method solves a sequence of weighted PCA problems, effectively down-weighting data points that deviate significantly from the current subspace estimate. For scenarios with extreme outliers, a pre-processing step called "spherization" (S-REAPER) is employed, projecting data onto a unit sphere to further mitigate the impact of distant points.
Theoretical Foundations
REAPER's success is underpinned by the geometry of high-dimensional spaces. The authors demonstrate that the convex relaxation remains remarkably tight, allowing for the recovery of the true subspace even when the search space is expanded. A key contribution is the "stability statistic," a deterministic metric that balances the structural evidence of inliers against the potential linear structure of outliers. When this statistic is positive, REAPER is guaranteed to recover the exact subspace (in the noiseless case) or a stable approximation.
Furthermore, the framework exhibits favorable scaling properties. Successful recovery requires the number of inliers to scale with the subspace dimension ($d$), while the capacity to handle outliers scales with the ambient dimension ($D$). This "David vs. Goliath" scaling allows REAPER to identify a small number of relevant signals buried within a massive volume of high-dimensional noise.
Experimental Results
The authors validated REAPER using both synthetic and real-world data. In "Haystack" models—where a 10-dimensional subspace is hidden in a 100-dimensional space—REAPER achieved perfect recovery even when outliers outnumbered inliers by a factor of ten.
In real-world tests, the algorithm was applied to the Extended Yale Face Database B. A set of 32 face images (inliers) was mixed with 467 random background images from Caltech101 (outliers), representing a dataset with over 90% contamination. S-REAPER successfully extracted a clean 9-dimensional model of the face. When evaluated on unseen test images, the subspace learned by S-REAPER provided significantly better reconstruction accuracy than standard PCA, Spherical PCA, or Low-Leverage Decomposition (LLD).
Conclusion
REAPER provides a mathematically sound and computationally efficient solution for robust linear modeling. By leveraging convex relaxation and high-dimensional geometry, it overcomes the limitations of traditional PCA in the presence of heavy outliers. While the method currently requires a pre-specified subspace dimension and is optimized for column-wise outliers rather than entry-wise corruption, it represents a significant advancement in robust data analysis.
Summary updated