Sampling Algorithms and Coresets for Lp Regression
| dc.creator | Dasgupta, Anirban | |
| dc.creator | Drineas, Petros | |
| dc.creator | Harb, Boulos | |
| dc.creator | Kumar, Ravi | |
| dc.creator | Mahoney, Michael W. | |
| dc.date | 2007-07-11 | |
| dc.date.accessioned | 2026-07-07T08:16:12Z | |
| dc.date.available | 2026-07-07T08:16:12Z | |
| dc.description | The Lp regression problem takes as input a matrix $A \in \Real^{n \times d}$, a vector $b \in \Real^n$, and a number $p \in [1,\infty)$, and it returns as output a number ${\cal Z}$ and a vector $x_{opt} \in \Real^d$ such that ${\cal Z} = \min_{x \in \Real^d} ||Ax -b||_p = ||Ax_{opt}-b||_p$. In this paper, we construct coresets and obtain an efficient two-stage sampling-based approximation algorithm for the very overconstrained ($n \gg d$) version of this classical problem, for all $p \in [1, \infty)$. The first stage of our algorithm non-uniformly samples $\hat{r}_1 = O(36^p 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 $\hat{r}_1/ε^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. | |
| dc.description | 19 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/0707.1714 | |
| dc.identifier | http://arxiv.org/abs/0707.1714 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/133696 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Sampling Algorithms and Coresets for Lp Regression | |
| dc.type | text |