Analysis of Sparse Regularization Based Robust Regression Approaches

analysis-sparsity-based-robust-regression-computational-imaging-lab-iit-madras

Abstract

Description

Problem Formulation

Method

  1. ℓ0-norm regularization (combinatorial). Minimizes the number of outliers directly; provably correct under the right geometric conditions (Proposition II.1), but combinatorial and computationally intractable in general.
  2. ℓ1-norm relaxation. Replaces the NP-hard ℓ0 problem with a convex ℓ1-norm formulation. In the noise-free case this gives exact recovery of the true parameters (Fact II.1); once a bounded dense-noise term is added, the same relaxation is called BPRR (basis pursuit robust regression) and instead gives a bounded-error recovery guarantee (Theorem II.1). The paper formulates BPRR as a second-order cone program with N+D variables and one cone constraint of dimension N, giving complexity O((N+D)2.5N), where N is the number of observations and D the number of regression parameters.
  3. Bayesian robust regression (BRR). Models outliers with a sparse prior and performs MAP estimation; empirically performs very well in the paper's experiments (complexity O(N³), dominated by the MAP estimation step), and is suggested (citing prior work) to be a better approximation of the ℓ0 problem than the convex ℓ1 relaxation.

Visualizations

analysis-sparsity-robust-regression-phase-transition-curves-computational-imaging-lab-iit-madras

Figure (illustrative recreation). Phase transition behaviour at dimension 125 — M-Estimators collapse earliest, then BPRR (ℓ1), with BRR (Bayesian) transitioning latest and tolerating the most outliers, matching the ordering reported in the paper's Fig. 3(a)–(b). The paper's own outlier-fraction axis runs from 0–80%; the specific transition points shown here are an illustrative recreation rather than digitized values from the original figure.

analysis-sparsity-robust-regression-algorithm-scalability-robustness-comparison-computational-imaging-lab-iit-madras

Figure (illustrative recreation). Scalability vs. robustness by algorithm — BRR (O(N³)) and BPRR (O((N+D)2.5N), N = number of observations, D = number of regression parameters) both scale polynomially and rate highest on robustness, while RANSAC and LMedS score lowest on scalability. The paper describes RANSAC and LMedS only as combinatorial (random-sampling-based) in the dimension D, without giving a closed-form polynomial complexity for either, which is why they're impractical for high-dimensional problems.

analysis-sparsity-robust-regression-outlier-detection-recovery-animation-computational-imaging-lab-iit-madras

Animation. Outlier detection & recovery process — from raw corrupted data, through residual-based outlier thresholding, to the final robust model fit, tracked alongside overall pipeline progress (data prep, outlier detection, robust weighting, model fitting, convergence).

analysis-sparsity-robust-regression-algorithm-convergence-comparison-animation-computational-imaging-lab-iit-madras

Animation. Algorithm convergence comparison — outlier identification and sparse-error detection on synthetic data, with BPRR, BRR, and M-Estimators' recovery accuracy tracked side by side across iterations.

analysis-sparsity-robust-regression-phase-transition-discovery-animation-computational-imaging-lab-iit-madras

Animation. Phase transition discovery — the critical outlier fraction curve for BRR is traced out progressively across problem dimensions (log scale), showing the success region growing as dimension coverage increases.

Key Results & Findings

  1. Phase transition phenomenon. All algorithms show a sharp success-to-failure transition as the outlier fraction increases, mirroring the phase transitions seen in compressive sensing.
  2. Strong performance of BRR. The Bayesian sparse approach (BRR) gives very good performance in the paper's experiments, generally ahead of the convex ℓ1 relaxation (BPRR) — a gap the authors suggest (citing prior work) may be because BRR better approximates the underlying ℓ0 problem.
  3. Scalability advantage. Compressive-sensing-based approaches (BPRR, BRR) scale polynomially, while traditional combinatorial methods (RANSAC, LMedS) become impractical in high dimensions.
  4. Noise robustness. With inlier noise varied at fixed dimension 6 and 40% outlier fraction, all approaches except LMedS perform well — RANSAC and M-estimates handle inlier noise fine too, so this isn't unique to the sparse-regularization methods.

Publications