2007/07/11 by Anirban Dasgupta, Petros Drineas, Dasgupta, Anirban +7 · 4 citations
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.DS
paper · pdf · doi:10.48550/arxiv.0707.1714
19 pages, 1 figure
arxiv created 2007/07/11 · openalex publication_date 2007/07/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Lp regression problem takes as input a matrix A ∈ \Realn × d, a vector b ∈ \Realn, and a number p ∈ [1,∞), and it returns as output a number \cal Z and a vector xopt ∈ \Reald such that \cal Z = minx ∈ \Reald ||Ax -b||p = ||Axopt-b||p. In this paper, we construct coresets and obtain an efficient two-stage sampling-based approximation algorithm for the very overconstrained (n ≫ d) version of this classical problem, for all p ∈ [1, ∞). The first stage of our algorithm non-uniformly samples r1 = O(36p d^max\p/2+1, p\+1) rows of A and the corresponding elements of b, and then it solves the Lp regression problem on the sample; we prove this is an 8-approximation. The second stage of our algorithm uses the output of the first stage to resample r1/ε2 constraints, and then it solves the Lp regression problem on the new sample; we prove this is a (1+ε)-approximation. Our algorithm unifies, improves upon, and extends the existing algorithms for special cases of Lp regression, namely p = 1,2. In course of proving our result, we develop two concepts--well-conditioned bases and subspace-preserving sampling--that are of independent interest.