Approximate quadrature measures on data--defined spaces

An important question in the theory of approximate integration is to study the conditions on the nodes $x_{k,n}$ and weights $w_{k,n}$ that allow an estimate of the form $$\underset{f\in {\mathcal{B}}_{\gamma }}{\sup }\mathrm{\mid }\sum _k{w}_{k,n}f(x_{k,n})-{\int }_{\mathbb{X}}fd{\mu }^{\ast }\mathrm{\mid }\le c{n}^{-\gamma },n=1,2,\cdots ,$$ where $\mathbb{X}$ is often a manifold with its volume measure ${\mu }^{\ast }$, and ${\mathcal{B}}_{\gamma }$ is the unit ball of a suitably defined smoothness class, parametrized by $\gamma$. In this paper, we study this question in the context of a quasi-metric, locally compact, measure space $\mathbb{X}$ with a probability measure ${\mu }^{\ast }$. We show that quadrature formulas exact for integrating the so called diffusion polynomials of degree $<n$ satisfy such estimates. Without requiring exactness, such formulas can be obtained as a solutions of some kernel-based optimization problem. We discuss the connection with the question of optimal covering radius. Our results generalize in some sense many recent results in this direction.