Search papers, labs, and topics across Lattice.
This paper investigates the pseudo-mixing properties of Kac's walk on the special orthogonal group $\mathrm{SO}(n)$, specifically whether short trajectories can be indistinguishable from Haar measure using low-complexity tests. The authors establish that the first $k$ columns achieve mixing in Wasserstein distance within $O(n(k+\log n)\log n)$ steps for a fixed accuracy, thereby resolving a conjecture by Oliveira. Additionally, they demonstrate that for sufficiently large $T$, the expectation of degree-$k$ polynomials under the $T$-step law closely approximates their Haar expectation, which has implications for the efficiency of Johnson鈥揕indenstrauss transforms.
Short trajectories in Kac's walk can be indistinguishable from Haar measure after just $O(n(k+\log n)\log n)$ steps, challenging previous assumptions about mixing times.
Motivated by a conjecture of Vaikuntanathan and Zamir, we study the pseudo-mixing of Kac's walk on $\mathrm{SO}(n)$: whether short trajectories are indistinguishable from Haar measure by low-complexity tests. We prove that the first $k$ columns mix in Wasserstein distance in $O(n(k+\log n)\log n)$ steps for fixed accuracy, resolving a conjecture of Oliveira. Combining this with a representation-theoretic variance bound, we show that if $T=\omega(nk(k+\log n)\log n)$, then every degree-$k$ polynomial normalized to have unit Haar variance has expectation under the $T$-step law within $o(1)$ of its Haar expectation. As an application, we show that this pseudo-mixing estimate can be used to prove the effectiveness of a fast Johnson--Lindenstrauss transform with the usual target dimension.
