SCIENCE@home

Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression

Xiangrui Meng,Michael W. Mahoney

Published 2012 in Symposium on the Theory of Computing

ABSTRACT

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

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-30 of 30 references · Page 1 of 1

CITED BY

Showing 1-100 of 292 citing papers · Page 1 of 3

123
Next