Random $\epsilon$-Cover on Compact Symmetric Space

Abstract

A randomized scheme that succeeds with probability $1-\delta$ (for any $\delta >0$) has been devised to construct (1) an equidistributed $\epsilon$-cover of a compact Riemannian symmetric space $\mathbb{M}$ of dimension $d_{\mathbb{M}}$ and antipodal dimension ${\bar{d}}_{\mathbb{M}}$, and (2) an approximate $({\lambda }_r,2)$-design, using $n(\epsilon ,\delta )$-many Haar-random isometries of $\mathbb{M}$, where \begin{equation}n(ε,δ):=O_{\mathbb M}\left(d_{\mathbb M}\ln \left(\frac 1ε\right)+\log\left(\frac 1δ\right)\right)\,,\end{equation} and ${\lambda }_r$ is the $r$-th smallest eigenvalue of the Laplace-Beltrami operator on $\mathbb{M}$. The $\epsilon$-cover so-produced can be used to compute the integral of 1-Lipschitz functions within additive $\tilde{O}(\epsilon )$-error, as well as in comparing persistence homology computed from data cloud to that of a hypothetical data cloud sampled from the uniform measure.