# On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2017.

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

- [A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guarantee](https://mlsanity.com/paper/2302.00248/) (2023)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [The Fast Johnson-Lindenstrauss Transform is Even Faster](https://mlsanity.com/paper/2204.01800/) (2022)
- [Statistical optimality conditions for compressive ensembles](https://mlsanity.com/paper/2106.01092/) (2021)
- [Sparse Dimensionality Reduction Revisited](https://mlsanity.com/paper/2302.06165/) (2023)
- [Confidence-Optimal Random Embeddings](https://mlsanity.com/paper/2104.05628/) (2021)

## Abstract (arXiv)

The Johnson-Lindenstrauss lemma is one of the corner stone results in dimensionality reduction. It says that given N, for any set of N vectors X subset ℝn, there exists a mapping f : X → ℝm such that f(X) preserves all pairwise distances between vectors in X to within (1 ± varepsilon) if m = O(varepsilon-2 lg N). Much effort has gone into developing fast embedding algorithms, with the Fast Johnson-Lindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The current fastest algorithm that yields the optimal m = O(varepsilon-2lg N) dimensions has an embedding time of O(n lg n + varepsilon-2 lg3 N). An exciting approach towards improving this, due to Hinrichs and Vyb'iral, is to use a random m × n Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in O(n lg m) time. The big question is of course whether m = O(varepsilon-2 lg N) dimensions suffice for this technique. If so, this would end a decades long quest to obtain faster and faster Johnson-Lindenstrauss transforms. The current best analysis of the embedding of Hinrichs and Vyb'iral shows that m = O(varepsilon-2lg2 N) dimensions suffices. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exists a set of N vectors requiring m = Omega(varepsilon-2 lg2 N) for the Toeplitz approach to work.