Almost Optimal Explicit Johnson-Lindenstrauss Families
View/ Open
Published Version
https://doi.org/10.1007/978-3-642-22935-0_53Metadata
Show full item recordCitation
Kane, Daniel, Raghu Meka, and Jelani Nelson. 2011. “Almost Optimal Explicit Johnson-Lindenstrauss Families.” Lecture Notes in Computer Science: 628–639. doi:10.1007/978-3-642-22935-0_53.Abstract
The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms. Constructions of linear embeddings satisfying the Johnson Lindenstrauss property necessarily involve randomness and much attention has been given to obtain explicit constructions minimizing the number of random bits used. In this work we give explicit constructions with an almost optimal use of randomness: For 0 < ε, δ < 1/2, we obtain explicit generators G : {0, 1} r → R s×d for s = O(log(1/δ)/ε2) such that for all d-dimensional vectors w of Euclidean norm 1, Pry∈u{0,1}r [ |kG(y)wk 2 − 1| > ε ] ≤ δ, with seed-length r = O log d + log(1/δ) · loglog(1/δ)ε. In particular, for δ = 1/ poly(d) and fixed ε > 0, we obtain seed-length O((log d)(log log d)). Previous constructions required Ω(log2d) random bits to obtain polynomially small error. We also give a new elementary proof of the optimality of the JL lemma showing a lower bound of Ω(log(1/δ)/ε2) on the embedding dimension. Previously, Jayram and Woodruff [9] used communication complexity techniques to show a similar bound.Other Sources
http://cseweb.ucsd.edu/~dakane/deranomizedJL.pdfTerms of Use
This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAPCitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:14427422
Collections
- FAS Scholarly Articles [18256]
Contact administrator regarding this item (to report mistakes or request changes)