Show simple item record

dc.contributor.authorKane, Daniel
dc.contributor.authorMeka, Raghu
dc.contributor.authorNelson, Jelani
dc.date.accessioned2015-04-14T17:36:53Z
dc.date.issued2011
dc.identifierQuick submit: 2015-01-13T11:59:46-05:00
dc.identifier.citationKane, 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.issn1433-8092en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:14427422
dc.description.abstractThe 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.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherSpringer Science + Business Mediaen_US
dc.relation.isversionof10.1007/978-3-642-22935-0_53en_US
dc.relation.hasversionhttp://cseweb.ucsd.edu/~dakane/deranomizedJL.pdfen_US
dash.licenseOAP
dc.titleAlmost Optimal Explicit Johnson-Lindenstrauss Familiesen_US
dc.typeConference Paperen_US
dc.date.updated2015-01-13T16:59:45Z
dc.description.versionAccepted Manuscripten_US
dc.rights.holderDaniel M. Kane, Raghu Meka, Jelani Nelson
dc.relation.journalApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniquesen_US
dash.depositing.authorNelson, Jelani
dc.date.available2015-04-14T17:36:53Z
dc.identifier.doi10.1007/978-3-642-22935-0_53*
dash.contributor.affiliatedNelson, Jelani


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record