Wasserstein mixing of a systematic-scan random rotation sampler
Abstract
We study the mixing time of a systematic-scan analogue of Kac's walk that was proposed as a fast surrogate for Haar-distributed orthogonal matrices in randomized high-dimensional algorithms and was conjectured to approach Haar measure after only logarithmically many sweeps. We show that this conjectured speed-up does not occur for convergence of the full matrix law to Haar measure in Frobenius Wasserstein distance. At fixed normalized accuracy, the mixing time lies between order n/log n and order n sweeps; at fixed absolute Frobenius accuracy, the corresponding bounds are between order n and order nlog n. More strongly, below the scale n/log n, the normalized Wasserstein distance remains asymptotically at its extremal value. We also show that the output law is singular with respect to Haar measure for fewer than n/2 sweeps. Thus the sampler may provide effective application-specific randomization without exhibiting the much faster full-Haar mixing.
Related
- Local Geometric Mixing via Dobrushin Contraction with Applications to Diffusion Path Monte Carlo and the Proximal Sampler
- p-Wasserstein distance and Cramér-type moderate deviations for the multi-dimensional elephant random walk
- Mixing time of the lazy and simple random walk on a randomly twisted hypercube
- Mixing Time of the Random-Pair Monte Shuffle
- Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold
BibTeX
@misc{sepehri2026wasserstein,
title = {{Wasserstein mixing of a systematic-scan random rotation sampler}},
author = {Amir Sepehri},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13424},
eprint = {2609.13424},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13424},
}
RIS
TY - UNPB
TI - Wasserstein mixing of a systematic-scan random rotation sampler
AU - Amir Sepehri
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.13424
UR - https://arxiv.org/abs/2609.13424
AB - We study the mixing time of a systematic-scan analogue of Kac's walk that was proposed as a fast surrogate for Haar-distributed orthogonal matrices in randomized high-dimensional algorithms and was conjectured to approach Haar measure after only logarithmically many sweeps. We show that this conjectured speed-up does not occur for convergence of the full matrix law to Haar measure in Frobenius Wasserstein distance. At fixed normalized accuracy, the mixing time lies between order n/log n and order n sweeps; at fixed absolute Frobenius accuracy, the corresponding bounds are between order n and order nlog n. More strongly, below the scale n/log n, the normalized Wasserstein distance remains asymptotically at its extremal value. We also show that the output law is singular with respect to Haar measure for fewer than n/2 sweeps. Thus the sampler may provide effective application-specific randomization without exhibiting the much faster full-Haar mixing.
ER -