ECCC-Report TR10-098https://eccc.weizmann.ac.il/report/2010/098Comments and Revisions published for TR10-098en-usWed, 08 Dec 2010 13:47:46 +0200
Revision 2
| A Derandomized Sparse Johnson-Lindenstrauss Transform |
Daniel Kane,
Jelani Nelson
https://eccc.weizmann.ac.il/report/2010/098#revision2Recent 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.Wed, 08 Dec 2010 13:47:46 +0200https://eccc.weizmann.ac.il/report/2010/098#revision2
Revision 1
| A Derandomized Sparse Johnson-Lindenstrauss Transform |
Daniel Kane,
Jelani Nelson
https://eccc.weizmann.ac.il/report/2010/098#revision1Recent 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].Thu, 08 Jul 2010 20:07:09 +0300https://eccc.weizmann.ac.il/report/2010/098#revision1
Paper TR10-098
| A Derandomized Sparse Johnson-Lindenstrauss Transform |
Daniel Kane,
Jelani Nelson
https://eccc.weizmann.ac.il/report/2010/098Recent 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].Fri, 18 Jun 2010 18:22:05 +0300https://eccc.weizmann.ac.il/report/2010/098