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

Abstract:   Introduced in the 1950s by Mark Kac as a toy model for a one-dimensional Boltzmann gas, the Kac walk is the following simple and well-studied Markov chain on the special orthogonal group: at every time step, sample two distinct uniform coordinates $i,j$ and a uniform angle $\theta$, and rotate in the $(i,j)$-plane by $\theta$. In this talk, I will discuss how the Kac walk can be used for the purpose of dimensionality reduction, specifically, for the design of linear transformations with optimal Johnson–Lindenstrauss and Restricted Isometry properties, and which support memory-optimal fast matrix-vector multiplication. I will also discuss the performance of a variant of the Kac walk, for which $\theta = \pi/4$ at every time step

This is joint work with Natesh S. Pillai (Harvard), Ashwin Sah (MIT), Mehtaab Sawhney (MIT), and Aaron Smith (U Ottawa).