Sampling Algorithms and Coresets for Lp Regression

The Lp regression problem takes as input a matrix $A\in {\text{Real}}^{n\times d}$, a vector $b\in {\text{Real}}^n$, and a number $p\in [1,\mathrm{\infty })$, and it returns as output a number $\mathcal{Z}$ and a vector $x_{opt}\in {\text{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,\mathrm{\infty })$. The first stage of our algorithm non-uniformly samples ${\widehat{r}}_1=O({36}^p{d}^{\max \{p\mathrm{/}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 ${\widehat{r}}_1\mathrm{/}{ϵ}^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.