Publication: A Derandomized Sparse Johnson-Lindenstrauss Transform
Loading...
Date
2010
Authors
Published Version
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
The Harvard community has made this article openly available. Please share how this access benefits you.
Citation
Kane, Daniel M. and Nelson, Jelani. 2010. "A Derandomized Sparse Johnson-Lindenstrauss Transform." Working paper.
Abstract
Recent work of [Dasgupta-Kumar-Sarl´os, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently derandomized. We answer their question affirmatively by giving an alternative proof of their result requiring only bounded independence hash functions. Furthermore, the sparsity bound obtained in our proof is improved. Our work implies the first implementation of a JohnsonLindenstrauss transform in data streams with sublinear update time.
Description
Research Data
Keywords
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service