Robust Regression Using Sparse Learning for High Dimensional Parameter Estimation Problems

Abstract

robust-regression-sparse-learning-computational-imaging-lab-iit-madras

The Problem

Background

Challenges with Existing Approaches:

Mathematical Formulation

y = Xw + n + s

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

mins ||s||0 subject to ||z − Cs||2 ≤ ε

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

Description

Results

robust-regression-sparse-learning-main-comparison-graph-computational-imaging-lab-iit-madras

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.

robust-regression-sparse-learning-scalability-high-dimensional-performance-computational-imaging-lab-iit-madras

Figure 2. Mean angle error vs. dimension at outlier fraction 0.4 ➯ BSRR performs well up to dimension 128.

robust-regression-sparse-learning-fg-net-age-estimation-outlier-detection-computational-imaging-lab-iit-madras

Figure 4. Some outliers and inliers found by BSRR ➯ most of the outliers detected are correctly identified.

Experimental Results

Performance Metrics

Number of Data Points

1,000 – 5,000

Dimensions Tested

2 to 128

Outlier Fraction

10% – 80%

Noise Variance

0 – 14 σ²

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
BSRRO(N³+D³)● Practical128+
BPRRO(N³+D³)● Practical128+
M-Estimators (IRLS)O(D³/3+D²N)● Practical32
L1 RegressionO(N³)● Practical32
LMedSmin(log(1−p)/log(1−(1−f)D), N!/(D!(N−D)!))✗ Impractical4–5
RANSACCombinatorial in D✗ Impractical4–5
MSACCombinatorial in D✗ Impractical4–5

Real-World Application: Facial Age Estimation

Dataset: FG-Net Aging Database

Results

Category Mean Absolute Error (MAE) Interpretation
Inlier Samples3.73 yearsHigh accuracy for regular/typical faces
Outlier Samples19.14 yearsPoor predictions for unusual cases
Overall6.45 yearsBalanced performance across all

Key Observations

Visualizations

robust-regression-sparse-learning-outlier-detection-animation-computational-imaging-lab-iit-madras

Animation: Sparse representation and outlier detection process ➯ points are processed one at a time as inliers and outliers are progressively identified.

robust-regression-sparse-learning-performance-comparison-computational-imaging-lab-iit-madras

Fig 1. Mean angle error vs. outlier fraction at dimensions 2, 8, and 32, comparing BSRR, BPRR, RANSAC, MSAC, LMedS, and M-estimators.

robust-regression-sparse-learning-scalability-computational-imaging-lab-iit-madras

Fig 2. Scalability across dimensions (linear and log scale) ➯ BSRR maintains the lowest error as dimension grows to 128.

robust-regression-sparse-learning-complexity-comparison-computational-imaging-lab-iit-madras

Fig 3. Computational complexity comparison ➯ BSRR and BPRR remain polynomial-time and feasible where combinatorial methods are not.

robust-regression-sparse-learning-age-estimation-application-computational-imaging-lab-iit-madras

Fig 4. Facial age estimation application on FG-Net ➯ inlier vs. outlier MAE and the dataset split found by BSRR.

robust-regression-sparse-learning-project-summary-computational-imaging-lab-iit-madras

Project Summary. One-page overview of the problem, solution, and key results.

Research Contributions

Novel Contributions

Technical Impact & Future Directions

Impact

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

Publications