2010/06/18 by Daniel M. Kane, Kane, Daniel M., Jelani Nelson +1 · 2 citations
Computer Science · Engineering · Mathematics · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Mathematical Analysis and Transform Methods #Sparse and Compressive Sensing Techniques #cs.CC #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1006.3585
v3: Improved seed length, alternative proof of JL row optimality, other minor changes; v2: Improved presentation. Added a warmup section, Section 4, which gives a short proof of the JL lemma
openalex publication_date 2010/06/18 · arxiv created 2010/12/07 · arxiv updated 2010/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. The main ingredient in our proof is a spectral moment bound for quadratic forms that was recently used in [Diakonikolas-Kane-Nelson, FOCS 2010].