Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression

Abstract

Low-distortion embeddings are critical building blocks for developing random sampling and random projection algorithms for linear algebra problems. We show that, given a matrix $A\in {\mathbb{R}}^{n\times d}$ with $n\gg d$ and a $p\in [1,2)$, with a constant probability, we can construct a low-distortion embedding matrix $Π\in \R^{O(\poly(d)) \times n}$ that embeds $\A_p$, the ${\ell }_p$ subspace spanned by $A$'s columns, into $(\R^{O(\poly(d))}, \| \cdot \|_p)$; the distortion of our embeddings is only $O(\poly(d))$, and we can compute $\Pi A$ in $O(\nnz(A))$ time, i.e., input-sparsity time. Our result generalizes the input-sparsity time ${\ell }_2$ subspace embedding by Clarkson and Woodruff [STOC'13]; and for completeness, we present a simpler and improved analysis of their construction for ${\ell }_2$. These input-sparsity time ${\ell }_p$ embeddings are optimal, up to constants, in terms of their running time; and the improved running time propagates to applications such as $(1\pm \epsilon )$-distortion ${\ell }_p$ subspace embedding and relative-error ${\ell }_p$ regression. For ${\ell }_2$, we show that a $(1+\epsilon )$-approximate solution to the ${\ell }_2$ regression problem specified by the matrix $A$ and a vector $b\in {\mathbb{R}}^n$ can be computed in $O(\nnz(A) + d^3 \log(d/ε) /ε^2)$ time; and for ${\ell }_p$, via a subspace-preserving sampling procedure, we show that a $(1\pm \epsilon )$-distortion embedding of $\A_p$ into $\R^{O(\poly(d))}$ can be computed in $O(\nnz(A) \cdot \log n)$ time, and we also show that a $(1+\epsilon )$-approximate solution to the ${\ell }_p$ regression problem ${\min }_{x\in {\mathbb{R}}^d}\Vert Ax-b{\Vert }_p$ can be computed in $O(\nnz(A) \cdot \log n + \poly(d) \log(1/ε)/ε^2)$ time. Moreover, we can improve the embedding dimension or equivalently the sample size to $O(d^{3+p/2}\log (1/\epsilon )/{\epsilon }^2)$ without increasing the complexity.

22 pages

References in corpus (2)

• OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
• Low Rank Approximation and Regression in Input Sparsity Time

Cited by in corpus (1)

• Sparsity Lower Bounds for Dimensionality Reducing Maps