Nelson, JelaniNguyễn, Huy L.2015-01-232014Nelson, 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.978-3-662-43947-0978-3-662-43948-70302-9743http://nrs.harvard.edu/urn-3:HUL.InstRepos:13820498An 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.en-USConference Paper2015-01-13Jelani Nelson, Nguyễn Lê Huy2015-01-2310.1007/978-3-662-43948-7_73