Rapid mixing of geodesic walks on manifolds with positive curvature

Abstract

We introduce a Markov chain for sampling from the uniform distribution on a Riemannian manifold $\mathcal{M}$, which we call the geodesic walk. We prove that the mixing time of this walk on any manifold with positive sectional curvature $C_{x}(u,v)$ bounded both above and below by $0<\mathfrak{m}_{2}\leq C_{x}(u,v)\leq\mathfrak{M}_{2}<\infty$ is $\mathcal{O}^{*}(\frac{\mathfrak{M}_{2}}{\mathfrak{m}_{2}})$. In particular, this bound on the mixing time does not depend explicitly on the dimension of the manifold. In the special case that $\mathcal{M}$ is the boundary of a convex body, we give an explicit and computationally tractable algorithm for approximating the exact geodesic walk. As a consequence, we obtain an algorithm for sampling uniformly from the surface of a convex body that has running time bounded solely in terms of the curvature of the body.

Locations

• arXiv (Cornell University) - View - PDF
• The Annals of Applied Probability - View - PDF