Nelson, JelaniHuy, Nguyễn Lê2015-01-232014Nelson, Jelani, and Nguyễn Lê Huy. 2014. "OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings." In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), October 26-29, 2013, Berkeley, CA: 117-126. Piscataway, NJ: IEEE.978-0-7695-5135-70272-5428http://nrs.harvard.edu/urn-3:HUL.InstRepos:13820486An 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\).en-USConference Paper2015-01-13Jelani Nelson, Nguyễn Lê Huy2015-01-2310.1109/FOCS.2013.21