Analysis of Sparse Regularization Based Robust Regression Approaches
(IEEE Transactions on Signal Processing, 2013)
Abstract
Description
Problem Formulation
Method
- ℓ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.
- ℓ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.
- 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
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.
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.
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).
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.
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
- 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.
- 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.
- Scalability advantage. Compressive-sensing-based approaches (BPRR, BRR) scale polynomially, while traditional combinatorial methods (RANSAC, LMedS) become impractical in high dimensions.
- 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.
