OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings

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.