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 algo-rithms for common linear algebra problems. We show that, given a matrix A ∈ Rn×d with n d and a p ∈ [1, 2), with a constant probability, we can construct a low-distortion em-bedding matrix Π ∈ RO(poly(d))×n that embeds Ap, the `p subspace spanned by A’s columns, into (RO(poly(d)), ‖ · ‖p); the distortion of our embeddings is only O(poly(d)), and we can compute ΠA in O(nnz(A)) time, i.e., input-sparsity time. Our result generalizes the input-sparsity time `2 sub-space embedding by Clarkson and Woodruff [STOC’13]; and for completeness, we present a simpler and improved analy-sis of their construction for `2. These input-sparsity time `p embeddings are optimal, up to constants, in terms of their running time; and the improved running time propagates to applications such as (1 ± )-distortion `p subspace embed-ding and relative-error `p regression. For `2, we show that a (1 + )-approximate solution to the `2 regression problem specified by the matrix A and a vector b ∈ Rn can be com-puted in O(nnz(A) + d3 log(d/)/2) time; and for `p, via a subspace-preserving sampling procedure, we show that a (1 ± )-distortion embedding of Ap into RO(poly(d)) can be computed in O(nnz(A) · logn) time, and we also show that a (1 + )-approximate solution to the `p regression problem minx∈Rd ‖Ax − b‖p can be computed in O(nnz(A) · logn + poly(d) log(1/)/2) time. Moreover, we can also improve the embedding dimension or equivalently the sample size to O(d3+p/2 log(1/)/2) without increasing the complexity