Fast and memory-optimal dimension reduction using Kac’s walk

In this work, we analyze dimension reduction algorithms based on the Kac walk and discrete variants. (1) For n points in Rd, 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, and Bamberger and Krahmer. 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, and of Oliveira, 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. (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. Our moment-based analysis of this modification of the Kac walk may also be of independent interest in connection with repeated averaging processes.