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 common linear algebra problems. We show that, given a matrix A ∈ R n x d with n >> d and a p ∈ [1, 2), with a constant probability, we can construct a low-distortion embedding matrix Π ∈ R O(poly(d)) x n that embeds A p , the l 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 Π A in O(nnz(A)) time, i.e., input-sparsity time. Our result generalizes the input-sparsity time l 2 subspace embedding by Clarkson and Woodruff [STOC'13]; and for completeness, we present a simpler and improved analysis of their construction for l 2 . These input-sparsity time l 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 l p subspace embedding and relative-error l p regression. For l 2 , we show that a (1+ε)-approximate solution to the l 2 regression problem specified by the matrix A and a vector b ∈ R n can be computed in O(nnz(A) + d 3 log(d/ε) /ε^2) time; and for l p , via a subspace-preserving sampling procedure, we show that a (1 pm ε)-distortion embedding of A p into R O(poly(d)) can be computed in O(nnz(A) ⋅ log n) time, and we also show that a (1+ε)-approximate solution to the l p regression problem min x ∈ R d |A x - b| p can be computed in O(nnz(A) ⋅ log n + poly(d) log(1/ε)/ε 2 ) time. Moreover, we can also improve the embedding dimension or equivalently the sample size to O(d 3+p/2 log(1/ε) / ε 2 ) without increasing the complexity.

Authors

• Xiangrui Meng
• Michael W. Mahoney

Keywords

• input-sparsity time
• l p regression
• linear regression
• low-distortion embedding
• robust regression
• subspace embedding