Subspace Embeddings and ${\ell }_p$-Regression Using Exponential Random Variables

Abstract

Oblivious low-distortion subspace embeddings are a crucial building block for numerical linear algebra problems. We show for any real $p,1\le p<\infty$, given a matrix $M\in {\mathbb{R}}^{n\times d}$ with $n\gg d$, with constant probability we can choose a matrix $\Pi$ with $\max(1, n^{1-2/p}) \poly(d)$ rows and $n$ columns so that simultaneously for all $x\in {\mathbb{R}}^d$, $\|Mx\|_p \leq \|ΠMx\|_{\infty} \leq \poly(d) \|Mx\|_p.$ Importantly, $\Pi M$ can be computed in the optimal $O(\nnz(M))$ time, where $\nnz(M)$ is the number of non-zero entries of $M$. This generalizes all previous oblivious subspace embeddings which required $p\in [1,2]$ due to their use of $p$-stable random variables. Using our matrices $\Pi$, we also improve the best known distortion of oblivious subspace embeddings of ${\ell }_1$ into ${\ell }_1$ with $\tilde{O}(d)$ target dimension in $O(\nnz(M))$ time from $\tilde{O}(d^3)$ to $\tilde{O}(d^2)$, which can further be improved to $\tilde{O}(d^{3/2}){\log }^{1/2}n$ if $d=\Omega (\log n)$, answering a question of Meng and Mahoney (STOC, 2013). We apply our results to ${\ell }_p$-regression, obtaining a $(1+\eps)$-approximation in $O(\nnz(M)\log n) + \poly(d/\eps)$ time, improving the best known $\poly(d/\eps)$ factors for every $p\in [1,\infty )\setminus \{2\}$. If one is just interested in a $\poly(d)$ rather than a $(1+\eps)$-approximation to ${\ell }_p$-regression, a corollary of our results is that for all $p\in [1,\infty )$ we can solve the ${\ell }_p$-regression problem without using general convex programming, that is, since our subspace embeds into ${\ell }_{\infty }$ it suffices to solve a linear programming problem. Finally, we give the first protocols for the distributed ${\ell }_p$-regression problem for every $p\ge 1$ which are nearly optimal in communication and computation.

Corrected some technical issues in Sec. 4.4

References in corpus (2)

• LSRN: A Parallel Iterative Solver for Strongly Over- or Under-Determined Systems
• Tight conditions for consistent variable selection in high dimensional nonparametric regression

Cited by in corpus (8)

• Random projections for Bayesian regression
• On Coresets for Logistic Regression
• Minimum Cost Flows, MDPs, and ${\ell }_1$-Regression in Nearly Linear Time for Dense Instances
• Low Rank Approximation with Entrywise ${\ell }_1$-Norm Error
• Fast Fixed Dimension L2-Subspace Embeddings of Arbitrary Accuracy, With Application to L1 and L2 Tasks
• Spectral estimation from simulations via sketching
• Structured random sketching for PDE inverse problems
• On Coresets For Regularized Regression