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

Vishesh Jain, Natesh S. Pillai, Ashwin Sah +2

In this work, we analyze dimension reduction algorithms based on the Kac walk and discrete variants. (1) For $n$ points in ${\mathbb{R}}^d$, we design an optimal Johnson-Lindenstra…