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

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 $\mathrm{\Pi }\in {\mathbb{R}}^{O(\text{poly}(d))\times n}$ that embeds ${\text{A}}_p$, the ${\mathrm{\ell }}_p$ subspace spanned by $A$’s columns, into $({\mathbb{R}}^{O(\text{poly}(d))},\mathrm{\parallel }\cdot {\mathrm{\parallel }}_p)$; the distortion of our embeddings is only $O(\text{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 ${\mathrm{\ell }}_2$ subspace embedding by Clarkson and Woodruff [STOC’13]; and for completeness, we present a simpler and improved analysis of their construction for ${\mathrm{\ell }}_2$. These input-sparsity time ${\mathrm{\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 ϵ)$-distortion ${\mathrm{\ell }}_p$ subspace embedding and relative-error ${\mathrm{\ell }}_p$ regression. For ${\mathrm{\ell }}_2$, we show that a $(1+ϵ)$-approximate solution to the ${\mathrm{\ell }}_2$ regression problem specified by the matrix $A$ and a vector $b\in {\mathbb{R}}^n$ can be computed in $O(\text{nnz}(A)+d^3\log (d\mathrm{/}ϵ)\mathrm{/}{ϵ}^2)$ time; and for ${\mathrm{\ell }}_p$, via a subspace-preserving sampling procedure, we show that a $(1\pm \epsilon)$-distortionembeddingof$\A_p$into$\R^{O(\poly(d))}$ can be computed in $O(\text{nnz}(A)\cdot \log n)$ time, and we also show that a $(1+ϵ)$-approximate solution to the ${\mathrm{\ell }}_p$ regression problem $\min_{x \in \R^d} |A x - b|_p$canbecomputedin$O(\nnz(A) \cdot \log n + \poly(d) \log(1/\epsilon)/\epsilon^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.