Discretization on high-dimensional domains

Abstract

Let $\mu$ be a Borel probability measure on a compact path-connected metric space $(X,\rho )$ for which there exist constants $c,\beta >1$ such that $\mu (B)\ge c{r}^{\beta }$ for every open ball $B\subset X$ of radius $r>0$. For a class of Lipschitz functions $\Phi :[0,\infty )\to R$ that piecewisely lie in a finite-dimensional subspace of continuous functions, we prove under certain mild conditions on the metric $\rho$ and the measure $\mu$ that for each positive integer $N\ge 2$, and each $g\in L^{\infty }(X,d\mu )$ with $\Vert g{\Vert }_{\infty }=1$, there exist points $y_1,\dots ,y_N\in X$ and real numbers ${\lambda }_1,\dots ,{\lambda }_N$ such that for any $x\in X$, \begin{align*} & \left| \int_X Φ(ρ(x, y)) g(y) \,d μ(y) - \sum_{j = 1}^{ N} λ_j Φ(ρ(x, y_j)) \right| \leq C N^{- \frac{1}{2} - \frac{3}{2β}} \sqrt{\log N}, \end{align*} where the constant $C>0$ is independent of $N$ and $g$. In the case when $X$ is the unit sphere $S^d$ of $R^{d+1}$ with the ususal geodesic distance, we also prove that the constant $C$ here is independent of the dimension $d$. Our estimates are better than those obtained from the standard Monte Carlo methods, which typically yield a weaker upper bound $N^{-\frac{1}{2}}\sqrt{\log N}$.