# Fast and memory-optimal dimension reduction using Kac's walk

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Mar 2020.

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

- [The Fast Johnson-Lindenstrauss Transform is Even Faster](https://mlsanity.com/paper/2204.01800/) (2022)
- [Sparse Dimensionality Reduction Revisited](https://mlsanity.com/paper/2302.06165/) (2023)

## Abstract (arXiv)

In this work, we analyze dimension reduction algorithms based on the Kac walk and discrete variants. (1) For n points in ℝd, we design an optimal Johnson-Lindenstrauss (JL) transform based on the Kac walk which can be applied to any vector in time O(dlogd) for essentially the same restriction on n as in the best-known transforms due to Ailon and Liberty [SODA, 2008], and Bamberger and Krahmer [arXiv, 2017]. Our algorithm is memory-optimal, and outperforms existing algorithms in regimes when n is sufficiently large and the distortion parameter is sufficiently small. In particular, this confirms a conjecture of Ailon and Chazelle [STOC, 2006] in a stronger form. (2) The same construction gives a simple transform with optimal Restricted Isometry Property (RIP) which can be applied in time O(dlogd) for essentially the same range of sparsity as in the best-known such transform due to Ailon and Rauhut [Discrete Comput. Geom., 2014]. (3) We show that by fixing the angle in the Kac walk to be π/4 throughout, one obtains optimal JL and RIP transforms with almost the same running time, thereby confirming -- up to a loglogd factor -- a conjecture of Avron, Maymounkov, and Toledo [SIAM J. Sci. Comput., 2010]. Our moment-based analysis of this modification of the Kac walk may also be of independent interest.