# Lower Bounds for Oblivious Subspace Embeddings

 Title: Lower Bounds for Oblivious Subspace Embeddings Author: Nelson, Jelani; Nguyễn, Huy L. Note: Order does not necessarily reflect citation order of authors. Citation: Nelson, Jelani, and Huy L. Nguyễn. 2014. “Lower Bounds for Oblivious Subspace Embeddings.” In Automata, Languages, and Programming: Proceedings of the 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Part I, Lecture Notes in Computer Science, Vol. 8572: 883–894. Berlin, Germany: Springer. Full Text & Related Files: ose_lb.pdf (446.8Kb; PDF) Abstract: An oblivious subspace embedding (OSE) for some $$\epsilon$$,$$\delta \in (0,1/3)$$ and d ≤ m ≤ n is a distribution $$\mathcal{D}$$ over $$\mathbb{R}^{m×n}$$ such that $$\underset {\Pi \sim \mathcal{D}} {Pr} (\forall x \in W, (1−\epsilon)|| x ||_2≤ || \Pi x ||_2≤(1+\epsilon)|| x||_2)≥1−\delta$$ for any linear subspace $$W \subset \mathbb{R}^n$$ of dimension d. We prove any OSE with $$\delta < 1/3$$ has $$m = \Omega((d + log(1/\delta))/\epsilon^2)$$, which is optimal. Furthermore, if every $$\Pi$$ in the support of $$\mathcal{D}$$ is sparse, having at most s non-zero entries per column, we show tradeoff lower bounds between m and s. Published Version: doi:10.1007/978-3-662-43948-7_73 Other Sources: http://arxiv.org/abs/1308.3280 Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:13820498 Downloads of this work: