OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings

Abstract

An oblivious subspace embedding (OSE) given some parameters (\epsilon), d is a distribution (\mathcal{D}) over matrices (\Pi \in \mathbb{R}^{m×n}) such that for any linear subspace (W \subseteq \mathbb{R}^n) with dim(W) = d, (\mathbb{P}_{\Pi \sim \mathcal{D}}(\forall x \in W ||\Pi x||_2 \in (1 \pm \epsilon)||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+\gamma}/\epsilon^2)), and where every matrix (\Pi) in the support of the OSE has only (s = O{\gamma}(1/\epsilon)) non-zero entries per column, for (\gamma > 0) any desired constant. Plugging OSNAPs into known algorithms for approximate least squares regression, (\ell_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 \in \mathbb{R}^{n×d}) with orthonormal columns and random sparse (\Pi), all singular values of (\Pi U) lie in ([1 - \epsilon, 1 + \epsilon]) 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/\epsilon^2)), (s = 1).