# Fast and Exact Least Absolute Deviations Line Fitting via Piecewise Affine Lower-Bounding

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 43 references that are in the map.
- First posted on arXiv 22 Dec 2025.

## Builds on (most cited first, 5 of 5)

- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [Clarabel: An interior-point solver for conic programs with quadratic objectives](https://mlsanity.com/paper/2405.12762/) (2024)
- [Fast Deterministic Selection](https://mlsanity.com/paper/1606.00484/) (2016)
- [Continuous Equality Knapsack with Probit-Style Objectives](https://mlsanity.com/paper/2211.02237/) (2022)
- [Degrees-of-freedom penalized piecewise regression](https://mlsanity.com/paper/2312.16512/) (2023)

## Abstract (arXiv)

Least-absolute-deviations (LAD) line fitting is robust to outliers but computationally more involved than least squares regression. Although the literature includes linear and near-linear time algorithms for the LAD line fitting problem, these methods are difficult to implement and, to our knowledge, lack maintained public implementations. As a result, practitioners often resort to linear programming (LP) based methods such as the simplex-based Barrodale-Roberts method and interior-point methods, or on iteratively reweighted least squares (IRLS) approximation which does not guarantee exact solutions. To close this gap, we propose the Piecewise Affine Lower-Bounding (PALB) method, an exact algorithm for LAD line fitting. PALB uses supporting lines derived from subgradients to build piecewise-affine lower bounds, and employs a subdivision scheme involving minima of these lower bounds. We prove correctness and provide bounds on the number of iterations. On synthetic datasets with varied signal types and noise including heavy-tailed outliers as well as a real dataset from the NOAA's Integrated Surface Database, PALB exhibits empirical log-linear scaling. It is consistently faster than publicly available implementations of LP based and IRLS based solvers. We provide a reference implementation written in Rust with a Python API.