Lower Bounds for Oblivious Subspace Embeddings

DSpace/Manakin Repository

Lower Bounds for Oblivious Subspace Embeddings

Citable link to this page


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:
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:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search