OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings 论文

2013引用 264

Sparse and Compressive Sensing TechniquesMatrix Theory and AlgorithmsTensor decomposition and applications

Matrix Theory and Algorithms Sparse and Compressive Sensing Techniques Tensor decomposition and applications

作者

摘要

An oblivious subspace embedding (OSE) given some parameters ε, d is a distribution D over matrices Π ∈ R m×n such that for any linear subspace W ⊆ R n with dim(W) = d, P Π~D (∀x ∈ W ||Πx|| 2 ∈ (1 ± ε)||x|| 2 ) > 2/3. We show that a certain class of distributions, Oblivious Sparse Norm-Approximating Projections (OSNAPs), provides OSE's with m = O(d 1+γ /ε 2 ), and where every matrix Π in the support of the OSE has only s = O γ (1/ε) non-zero entries per column, for γ > 0 any desired constant. Plugging OSNAPs into known algorithms for approximate least squares regression, ℓ p regression, low rank approximation, and approximating leverage scores implies faster algorithms for all these problems. Our main result is essentially a Bai-Yin type theorem in random matrix theory and is likely to be of independent interest: we show that for any fixed U ∈ R n×d with orthonormal columns and random sparse Π, all singular values of ΠU lie in [1 - ε, 1 + ε] with good probability. This can be seen as a generalization of the sparse Johnson-Lindenstrauss lemma, which was concerned with d = 1. Our methods also recover a slightly sharper version of a main result of [Clarkson-Woodruff, STOC 2013], with a much simpler proof. That is, we show that OSNAPs give an OSE with m = O(d 2 /ε 2 ), s = 1.

作者查看全部 (2)

Huy L. Nguyên

Jelani Nelson

OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings 论文

摘要

作者查看全部 (2)

相关技术查看全部 (1)

相关事件

相关文章