dc.contributor.author Kane, Daniel dc.contributor.author Meka, Raghu dc.contributor.author Nelson, Jelani dc.date.accessioned 2015-04-14T17:36:53Z dc.date.issued 2011 dc.identifier Quick submit: 2015-01-13T11:59:46-05:00 dc.identifier.citation 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. en_US dc.identifier.issn 1433-8092 en_US dc.identifier.uri http://nrs.harvard.edu/urn-3:HUL.InstRepos:14427422 dc.description.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. en_US dc.description.sponsorship Engineering and Applied Sciences en_US dc.language.iso en_US en_US dc.publisher Springer Science + Business Media en_US dc.relation.isversionof 10.1007/978-3-642-22935-0_53 en_US dc.relation.hasversion http://cseweb.ucsd.edu/~dakane/deranomizedJL.pdf en_US dash.license OAP dc.title Almost Optimal Explicit Johnson-Lindenstrauss Families en_US dc.type Conference Paper en_US dc.date.updated 2015-01-13T16:59:45Z dc.description.version Accepted Manuscript en_US dc.rights.holder Daniel M. Kane, Raghu Meka, Jelani Nelson dc.relation.journal Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques en_US dash.depositing.author Nelson, Jelani dc.date.available 2015-04-14T17:36:53Z dc.identifier.doi 10.1007/978-3-642-22935-0_53 * dash.contributor.affiliated Nelson, Jelani
﻿