# Fast Approximate L_infty Minimization: Speeding Up Robust Regression

arXiv: https://arxiv.org/abs/1304.1250 · HTML: https://mlsanity.com/paper/1304.1250/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2013.

## Built on by (most cited first, 1 of 1)

- [Projected Randomized Smoothing for Certified Adversarial Robustness](https://mlsanity.com/paper/2309.13794/) (2023)

## Abstract (arXiv)

Minimization of the L_∞ norm, which can be viewed as approximately solving the non-convex least median estimation problem, is a powerful method for outlier removal and hence robust regression. However, current techniques for solving the problem at the heart of L_∞ norm minimization are slow, and therefore cannot scale to large problems. A new method for the minimization of the L_∞ norm is presented here, which provides a speedup of multiple orders of magnitude for data with high dimension. This method, termed Fast L_∞ Minimization, allows robust regression to be applied to a class of problems which were previously inaccessible. It is shown how the L_∞ norm minimization problem can be broken up into smaller sub-problems, which can then be solved extremely efficiently. Experimental results demonstrate the radical reduction in computation time, along with robustness against large numbers of outliers in a few model-fitting problems.