ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR10-098 | 8th December 2010 13:47

A Derandomized Sparse Johnson-Lindenstrauss Transform

RSS-Feed




Revision #2
Authors: Daniel Kane, Jelani Nelson
Accepted on: 8th December 2010 13:47
Downloads: 607
Keywords: 


Abstract:

Recent work of [Dasgupta-Kumar-Sarlos, 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 Johnson-Lindenstrauss transform in data streams with sublinear update time.



Changes to previous version:

Improved seed length and includes alternative proof of JL row optimality (see appendix); other minor changes.


Revision #1 to TR10-098 | 8th July 2010 20:07

A Derandomized Sparse Johnson-Lindenstrauss Transform





Revision #1
Authors: Daniel Kane, Jelani Nelson
Accepted on: 8th July 2010 20:07
Downloads: 631
Keywords: 


Abstract:

Recent work of [Dasgupta-Kumar-Sarl\'{o}s, 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. The main ingredient in our proof is a spectral moment bound for quadratic forms that was recently used in [Diakonikolas-Kane-Nelson, FOCS 2010].



Changes to previous version:

-- Improved introduction and related work section, and fixed various typos.

-- Added a warmup section, Section 4, which gives a new short proof of the standard, non-sparse Johnson-Lindenstrauss lemma.


Paper:

TR10-098 | 17th June 2010 23:06

A Derandomized Sparse Johnson-Lindenstrauss Transform





TR10-098
Authors: Daniel Kane, Jelani Nelson
Publication: 18th June 2010 18:22
Downloads: 801
Keywords: 


Abstract:

Recent work of [Dasgupta-Kumar-Sarl\'{o}s, 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. The main ingredient in our proof is a spectral moment bound for quadratic forms that was recently used in [Diakonikolas-Kane-Nelson, CoRR abs/0911.3389].



ISSN 1433-8092 | Imprint