A Derandomized Sparse Johnson-Lindenstrauss Transform

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. The main ingredient in our proof is a spectral moment bound for quadratic forms that was recently used in [Diakonikolas-Kane-Nelson, FOCS 2010].

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

References in corpus (2)

• Johnson-Lindenstrauss lemma for circulant matrices
• Almost Optimal Explicit Johnson-Lindenstrauss Transformations

Cited by in corpus (13)

• Randomized algorithms for matrices and data
• Johnson-Lindenstrauss Compression with Neuroscience-Based Constraints
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
• Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
• Almost Optimal Explicit Johnson-Lindenstrauss Transformations
• Embeddings of Schatten Norms with Applications to Data Streams
• Understanding Sparse JL for Feature Hashing
• Faster PAC Learning and Smaller Coresets via Smoothed Analysis
• Fast Moment Estimation in Data Streams in Optimal Space
• Sparsity Lower Bounds for Dimensionality Reducing Maps
• Faster Binary Embeddings for Preserving Euclidean Distances
• An Introduction to Johnson-Lindenstrauss Transforms
• Fast nonlinear embeddings via structured matrices