Robust Regression Using Sparse Learning for High Dimensional Parameter Estimation Problems
(ICASSP 2010)
Algorithms such as Least Median of Squares (LMedS) and Random Sample Consensus (RANSAC) have been very successful for low-dimensional robust regression problems. However, the combinatorial nature of these algorithms makes them practically unusable for high-dimensional applications. In this paper, we introduce algorithms that have cubic time complexity in the dimension of the problem, which make them computationally efficient for high-dimensional problems. We formulate the robust regression problem by projecting the dependent variable onto the null space of the independent variables which receives significant contributions only from the outliers. We then identify the outliers using sparse representation/learning based algorithms. Under certain conditions, that follow from the theory of sparse representation, these polynomial algorithms can accurately solve the robust regression problem which is, in general, a combinatorial problem. We present experimental results that demonstrate the efficacy of the proposed algorithms. We also analyze the intrinsic parameter space of robust regression and identify an efficient and accurate class of algorithms for different operating conditions. An application to facial age estimation is presented.
The Problem
Background
Regression aims to estimate model parameters from training data, but real-world datasets frequently contain outliers ➯ observations that deviate significantly from the underlying model. The presence of outliers makes standard regression estimates unreliable.
Challenges with Existing Approaches:
- LMedS (Least Median of Squares): Uses random sampling with combinatorial complexity ≥ (1/f)D
- RANSAC: Practical only for dimensions D ≤ 4–5 due to exponential scaling with dimension
- M-Estimators: Non-convex optimization with multiple local minima, difficult initialization
- Scalability: Traditional methods become impractical for D > 16
Mathematical Formulation
Given a linear regression model:
y = Xw + n + s
where y is the dependent variable, X contains independent variables, w are parameters to estimate, n is inlier noise, and s represents outlier errors. The goal is to estimate w while identifying and removing outliers.
Our Approach
Key Innovation: Null Space Projection
Instead of solving for both parameters and outliers simultaneously, we project the dependent variable onto the left null space of the independent variables. This transforms the problem into a sparse representation problem where outliers manifest as non-zero sparse coefficients.
Reformulated Problem
After null space projection, the robust regression becomes:
mins ||s||0 subject to ||z − Cs||2 ≤ ε
This is a sparse recovery problem ➯ identifying which observations are outliers by finding the sparsest solution. The matrix C is constructed from orthonormal basis vectors of the null space.
Two Polynomial-Time Solutions
BSRR
Bayesian Sparse Robust Regression
Uses sparsity-enforcing Bayesian priors with an evidence maximization framework
O(N³+D³) complexity
BPRR
Basis Pursuit Robust Regression
Convex L1 norm relaxation of the L0 minimization problem
O(N³+D³) complexity
Why This Works
- Under Restricted Isometry Property (RIP) conditions, L1 minimization recovers sparse solutions
- Projection isolates outlier information in a low-dimensional subspace
- Polynomial algorithms can solve what is inherently combinatorial in parameter space
- Robust to multiple outliers, unlike heuristic approaches
Description
Many high-dimensional parameter estimation problems in computer vision and signal processing must contend with training data that is corrupted by gross outliers, in addition to ordinary bounded noise. Classical robust regression techniques, developed for low-dimensional settings, do not always scale gracefully as the number of unknown parameters grows.
We recast robust regression as a sparse learning problem by explicitly modeling the outliers as an additional sparse error vector, added to the standard regression residual. Because only a small fraction of the observations are typically corrupted, this outlier vector is sparse, and can be recovered using tools from sparse signal recovery.
This formulation lets us bring efficient sparse learning algorithms to bear on robust regression problems with a large number of unknown parameters, giving estimators that remain accurate in the presence of outliers while scaling to high-dimensional settings that are common in computer vision applications such as structure from motion and face recognition.
Figure 1: Mean angle error vs. outlier fraction for dimensions 2, 8, and 32 ➯ BSRR consistently achieves the lowest estimation error among BSRR, BPRR, M-estimator, and L1.
Figure 2. Mean angle error vs. dimension at outlier fraction 0.4 ➯ BSRR performs well up to dimension 128.
Figure 4. Some outliers and inliers found by BSRR ➯ most of the outliers detected are correctly identified.
Number of Data Points
1,000 – 5,000
Dimensions Tested
2 to 128
Outlier Fraction
10% – 80%
Key Findings
Superior Robustness
BSRR maintains excellent performance up to dimension 128, while competing methods degrade significantly.
Scalability
Handles high-dimensional problems (D=128) in ~6 minutes ➯ traditional methods become impractical beyond D=16.
Noise Robustness
BSRR performs robustly across a wide range of inlier noise variances (0–14 σ²).
Algorithm Complexity Comparison
| Algorithm |
Time Complexity |
Feasibility |
Max Dimension |
| BSRR | O(N³+D³) | ● Practical | 128+ |
| BPRR | O(N³+D³) | ● Practical | 128+ |
| M-Estimators (IRLS) | O(D³/3+D²N) | ● Practical | 32 |
| L1 Regression | O(N³) | ● Practical | 32 |
| LMedS | min(log(1−p)/log(1−(1−f)D), N!/(D!(N−D)!)) | ✗ Impractical | 4–5 |
| RANSAC | Combinatorial in D | ✗ Impractical | 4–5 |
| MSAC | Combinatorial in D | ✗ Impractical | 4–5 |
Real-World Application: Facial Age Estimation
Dataset: FG-Net Aging Database
- Total Images: 1,002 facial images
- Subjects: 82 individuals
- Feature Type: Geometric features (68 fiducial points)
- Preprocessing: Optical flow computation relative to a reference face
Results
| Category |
Mean Absolute Error (MAE) |
Interpretation |
| Inlier Samples | 3.73 years | High accuracy for regular/typical faces |
| Outlier Samples | 19.14 years | Poor predictions for unusual cases |
| Overall | 6.45 years | Balanced performance across all |
Key Observations
- Outlier Detection Success: Found 177 outliers (17.7% of dataset)
- Pattern Recognition: Most outliers were older subjects with less variation in geometric features
- Data Quality: Fewer samples in older age categories contributed to outlier detection
- Model Reliability: Separation between inlier and outlier MAE validates robustness
Visualizations
An animated view of the outlier-detection process, followed by the performance, scalability, complexity, and application figures from the paper, plus a one-page project summary.
Animation: Sparse representation and outlier detection process ➯ points are processed one at a time as inliers and outliers are progressively identified.
Fig 1. Mean angle error vs. outlier fraction at dimensions 2, 8, and 32, comparing BSRR, BPRR, RANSAC, MSAC, LMedS, and M-estimators.
Fig 2. Scalability across dimensions (linear and log scale) ➯ BSRR maintains the lowest error as dimension grows to 128.
Fig 3. Computational complexity comparison ➯ BSRR and BPRR remain polynomial-time and feasible where combinatorial methods are not.
Fig 4. Facial age estimation application on FG-Net ➯ inlier vs. outlier MAE and the dataset split found by BSRR.
Project Summary. One-page overview of the problem, solution, and key results.
Research Contributions
Novel Contributions
- Null Space Reformulation: First work to reformulate robust regression via null space projection, connecting it to sparse representation theory
- Polynomial-Time Algorithms: Two algorithms (BSRR and BPRR) with cubic time complexity in problem dimension, enabling high-dimensional applications
- Theoretical Analysis: Conditions under which L1 minimization recovers the true outliers, based on RIP and incoherence properties
- Parameter Space Analysis: Comprehensive empirical study of how outlier fraction (f), dimension (D), sample size (N), and noise variance (σ²) affect algorithm performance
- Practical Application: Demonstration on facial age estimation, showing real-world utility for computer vision tasks
Technical Impact & Future Directions
Impact
- Enables robust regression in truly high-dimensional spaces (D > 100)
- Provides a principled approach based on sparse recovery theory
- Bridges computer vision methods (RANSAC) with compressed sensing and sparse learning
- Applicable to multiple domains: computer vision, signal processing, machine learning
Advantages Over Prior Work
- ● No Random Sampling: Deterministic polynomial-time algorithms
- ● High-Dimensional: Scales to dimension 128+
- ● Multiple Outliers: Systematic approach handles many outliers
- ● Theoretical Guarantees: Sparse recovery theory provides recovery conditions
- ● Robust: Performs across a wide range of noise and outlier levels