Provable Approximations for Constrained ℓp Regression

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.