A Sparse Johnson–Lindenstrauss Transform
📜 Abstract
Dimension reduction is a key algorithmic tool with many applications including nearest-neighbor search, compressed sensing and linear algebra in the streaming model. In this work we obtain a sparse version of the fundamental tool in dimension reduction — the Johnson–Lindenstrauss transform. Using hashing and local densification, we construct a sparse projection matrix with just \tilde{O}(\frac{1}{\epsilon}) non-zero entries per column. We also show a matching lower bound on the sparsity for a large class of projection matrices. Our bounds are somewhat surprising, given the known lower bounds of \Omega(\frac{1}{\epsilon^2}) both on the number of rows of any projection matrix and on the sparsity of projection matrices generated by natural constructions. Using this, we achieve an \tilde{O}(\frac{1}{\epsilon}) update time per non-zero element for a (1 ± \epsilon)-approximate projection, thereby substantially outperforming the \tilde{O}(\frac{1}{\epsilon^2}) update time required by prior approaches. A variant of our method offers the same guarantees for sparse vectors, yet its \tilde{O}(d) worst case running time matches the best approach of Ailon and Liberty.
✨ Summary
The paper develops a sparse Johnson–Lindenstrauss (JL) transform intended to reduce the cost of projecting high-dimensional vectors, particularly sparse vectors and streaming updates. Its construction combines a hash function, random ±1 signs, and local densification by replicating coordinates before hashing. Each original coordinate is mapped to a single hash bucket, producing a projection matrix with a controlled number of nonzero entries per column rather than independently sparsifying matrix entries.
For target dimension k = O(ε⁻² log(1/δ)), the construction achieves approximately \tilde{O}(ε⁻¹) nonzeros per column while preserving squared Euclidean norms within a (1 ± ε) factor with high probability. This yields an update time of approximately \tilde{O}(ε⁻¹) per nonzero input element, improving on earlier approaches requiring approximately \tilde{O}(ε⁻²) time. A block-Hadamard-based preconditioner extends the method to obtain a worst-case running time proportional to the smaller of the input sparsity and the ambient dimension, up to logarithmic factors.
The analysis addresses dependencies introduced by hashing. It bounds the contribution of individual buckets, controls collision-induced cross terms, and uses moment-generating-function arguments together with the FKG inequality to obtain concentration. The paper also proves lower bounds for a broad two-stage class of sparse projection constructions, showing that the upper bound is tight in its dependence on ε for that class. An additional construction provides an ℓ1-embedding result using Gaussian signs.
The work initiated a sequence of theoretical improvements. Kane and Nelson explicitly identify it as the source of a sparse JL construction whose efficient derandomization was an open question; they provide an alternative proof using bounded-independence hash functions and improve the sparsity bound. (arxiv.org) Braverman, Ostrovsky, and Rabani subsequently state that the paper introduced the sparse construction, and they further improve the sparsity and randomness bounds, building on the subsequent Kane–Nelson result. (arxiv.org) Later work continues to treat sparse JL transforms as a foundational primitive for fast sketching, randomized numerical linear algebra, compressed sensing, and related applications. (link.springer.com)