Discretization of integrals on compact metric measure spaces

Abstract Let μ be a Borel probability measure on a compact path-connected metric space ( X , ρ ) for which there exist constants c , β ≥ 1 such that μ ( B ) ≥ c r β for every open ball B ⊂ X of radius r > 0 . For a class of Lipschitz functions Φ : [ 0 , ∞ ) → R that are piecewise within a finite-dimensional subspace of continuous functions, we prove under certain mild conditions on the metric ρ and the measure μ that for each positive integer N ≥ 2 , and each g ∈ L ∞ ( X , d μ ) with ‖ g ‖ ∞ = 1 , there exist points y 1 , … , y N ∈ X and real numbers λ 1 , … , λ N such that for any x ∈ X , | ∫ X Φ ( ρ ( x , y ) ) g ( y ) d μ ( y ) − ∑ j = 1 N λ j Φ ( ρ ( x , y j ) ) | ⩽ C N − 1 2 − 3 2 β log ⁡ N , 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 usual 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 − 1 2 log ⁡ N .