# Sparse Dimensionality Reduction Revisited

arXiv: https://arxiv.org/abs/2302.06165 · HTML: https://mlsanity.com/paper/2302.06165/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 28 references that are in the map.
- First posted on arXiv 13 Feb 2023.

## Builds on (most cited first, 10 of 10)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Lower bounds for oblivious subspace embeddings](https://mlsanity.com/paper/1308.3280/) (2013)
- [Fully Understanding the Hashing Trick](https://mlsanity.com/paper/1805.08539/) (2018)
- [Understanding Sparse JL for Feature Hashing](https://mlsanity.com/paper/1903.03605/) (2019)
- [Practical Hash Functions for Similarity Estimation and Dimensionality Reduction](https://mlsanity.com/paper/1711.08797/) (2017)
- [On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/1706.10110/) (2017)
- [The Fast Johnson-Lindenstrauss Transform is Even Faster](https://mlsanity.com/paper/2204.01800/) (2022)
- [Fast and memory-optimal dimension reduction using Kac's walk](https://mlsanity.com/paper/2003.10069/) (2020)
- [Lower Bounds for Sparse Oblivious Subspace Embeddings](https://mlsanity.com/paper/2112.10987/) (2021)

## Built on by (most cited first, 1 of 1)

- [Distributed Differentially Private Data Analytics via Secure Sketching](https://mlsanity.com/paper/2412.00497/) (2024)

## Abstract (arXiv)

The sparse Johnson-Lindenstrauss transform is one of the central techniques in dimensionality reduction. It supports embedding a set of n points in ℝd into m=O(varepsilon-2 lg n) dimensions while preserving all pairwise distances to within 1 ± varepsilon. Each input point x is embedded to Ax, where A is an m × d matrix having s non-zeros per column, allowing for an embedding time of O(s |x|0). Since the sparsity of A governs the embedding time, much work has gone into improving the sparsity s. The current state-of-the-art by Kane and Nelson (JACM'14) shows that s = O(varepsilon -1 lg n) suffices. This is almost matched by a lower bound of s = Omega(varepsilon -1 lg n/lg(1/varepsilon)) by Nelson and Nguyen (STOC'13). Previous work thus suggests that we have near-optimal embeddings. In this work, we revisit sparse embeddings and identify a loophole in the lower bound. Concretely, it requires d ≥ n, which in many applications is unrealistic. We exploit this loophole to give a sparser embedding when d = o(n), achieving s = O(varepsilon-1(lg n/lg(1/varepsilon)+lg2/3n lg1/3 d)). We also complement our analysis by strengthening the lower bound of Nelson and Nguyen to hold also when d ll n, thereby matching the first term in our new sparsity upper bound. Finally, we also improve the sparsity of the best oblivious subspace embeddings for optimal embedding dimensionality.