2019/02/27 by Ibrahim Jubran, Jubran, Ibrahim, David Cohn +3 · 1 citation
Computer Science · Engineering · Mathematics · #Applied mathematics #Approximations of π #Control Systems and Identification #Mathematics #Regression #Statistical Methods and Inference #Statistical and numerical algorithms #Statistics #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1902.10407
published in arXiv (Cornell University) (Cornell University)
arxiv created 2019/02/27 · openalex publication_date 2019/02/27 · arxiv updated 2019/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.