# Provable Approximations for Constrained ℓp Regression

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2019.

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

- [Provably Approximated ICP](https://mlsanity.com/paper/2101.03588/) (2021)

## Abstract (arXiv)

The ℓp linear regression problem is to minimize f(x)=||Ax-b||p over x∈ℝd, where A∈ℝn× d, b∈ ℝn, and p>0. To avoid overfitting and bound ||x||2, the constrained ℓp regression minimizes f(x) over every unit vector x∈ℝd. This makes the problem non-convex even for the simplest case d=p=2. Instead, ridge regression is used to minimize the Lagrange form f(x)+λ ||x||2 over x∈ℝd, which yields a convex problem in the price of calibrating the regularization parameter λ>0. We provide the first provable constant factor approximation algorithm that solves the constrained ℓp regression directly, for every constant p,d≥ 1. Using core-sets, its running time is O(n log n) including extensions for streaming and distributed (big) data. In polynomial time, it can handle outliers, p∈ (0,1) and minimize f(x) over every x and permutation of rows in A. Experimental results are also provided, including open source and comparison to existing software.