# Function recovery on manifolds
using scattered data

David Krieg and Mathias Sonnleitner  Institut für Analysis, Johannes Kepler
Universität Linz, Austria<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We consider the task of recovering a Sobolev function on a connected compact
Riemannian manifold $M$ when given a sample on a finite point set. We prove
that the quality of the sample is given by the $L_{\gamma}(M)$-average of the
geodesic distance to the point set and determine the value of
$\gamma\in(0,\infty]$. This extends our findings on bounded convex domains
[arXiv:2009.11275, 2020]. Further, a limit theorem for moments of the average
distance to a set consisting of i.i.d. uniform points is proven. This yields
that a random sample is asymptotically as good as an optimal sample in
precisely those cases with $\gamma<\infty$. In particular, we obtain that
cubature formulas with random nodes are asymptotically as good as optimal
cubature formulas if the weights are chosen correctly. This closes a
logarithmic gap left open by Ehler, Gräf and Oates [Stat. Comput.,
29:1203-1214, 2019].

###### Key words and phrases:

Bessel potential space, discrepancy, numerical integration, Sobolev space,
sphere

###### 2020 Mathematics Subject Classification:

41A25, 41A55, 41A63, 58C35, 62D05, 65D15

Disclaimer. This paper relies on our previous work [15] which is still in the
revision process. The reader may therefore not yet find a complete proof of
all the results that are presented in this paper. However, this only concerns
the lower bound of Theorem 2 for smoothness $s\not\in\mathbb{N}$ and the lower
bound of Corollary 1 in the case that the dimension $d$ is even. See Remark 2
below.

We are interested in the problem of recovering a real-valued function on a
connected compact Riemannian manifold which is only known through a finite
number of function values, obtained on a finite set of sampling points. We
study this problem in the worst case setting, where the function is assumed to
have some Sobolev regularity and the recovery error is measured in the
$L_{q}$-norm.

If the sampling points can be chosen freely, this setting is classical and
many results are known on the error that can be achieved with optimally chosen
sampling points. For Sobolev spaces on domains, Novak and Triebel [19] show
that the optimal rate of convergence can be achieved with evenly spaced quasi-
uniform points using a polynomial reproducing map due to Wendland [30, 31],
which is based on moving least squares. On the sphere, a special case of the
manifolds we consider, Mhaskar [17] derives an asymptotically optimal upper
bound in terms of zonal function networks. Wang and Sloan [29] use filtered
polynomial approximation and Lu and Wang [16] rely on weighted least squares
in the Hilbert space case to achieve optimal rates, improving upon Gröchenig
[11]. On general manifolds, some results are obtained in Mhaskar [18, Theorem
3.3], which relies on approximation by eigenfunctions of the Laplace-Beltrami
operator on the manifold. In the general case, more is known about recovering
only an integral instead of the function itself, see Brandolini et al. [2].
The proofs behind many of these results rely on Marcinkiewicz-Zygmund
inequalities and exact integration of such eigenfunctions by quadrature rules,
again using evenly spaced quasi-uniform points, see for example Filbir and
Mhaskar [10].

In all these papers, the recovery method is based on function values at very
specific point sets. Here, we ask for the minimal worst case error that can be
achieved with a given (arbitrary) set of sampling points that cannot be chosen
by us. How can we assess the quality of the given set of sampling points? This
question has been studied lately for Sobolev spaces on bounded convex domains
by the present authors in [15]. A characterization of the quality of sampling
points has been obtained which is based on the radius of the point set’s
largest hole (in the case of large $q$) or the radius of an average hole (in
the case of small $q$). The question arises whether the same can be done for
Sobolev spaces defined on connected compact Riemannian manifolds, which we
answer in the affirmative.

Before we state the result, let us shortly introduce the necessary notation.
We recall basic facts on Riemannian geometry in Section 1. Let $M$ be a
connected compact Riemannian manifold and let $\operatorname{vol}_{M}$ be the
Riemannian volume measure on $M$ and $\operatorname{dist}_{M}(x,y)$ be the
Riemannian distance between points $x$ and $y$. Let $\Delta_{M}$ be the
Laplace-Beltrami operator on $M$. Then for $1<p<\infty$ and $s\in\mathbb{R}$
the Bessel potential (Sobolev) space is given by

$H^{s}_{p}(M)\,:=\,\big{\\{}f\in L_{p}(M):(I-\Delta_{M})^{s/2}f\in
L_{p}(M)\big{\\}},$

where $I$ is the identity on $L_{p}(M)=L_{p}(M,\operatorname{vol}_{M})$. The
norm of $f\in H^{s}_{p}(M)$ is

$\left\|f\right\|_{H^{s}_{p}(M)}\,:=\,\left\|(I-\Delta_{M})^{s/2}f\,\right\|_{L_{p}(M)}.$

We assume that $s>d/p$ such that the functions in $H^{s}_{p}(M)$ are
continuous and function values are well-defined.

######  Remark 1.

There are various ways to define Sobolev spaces, also in the case $p=1$ and
$p=\infty$. We demonstrate our result in the case $1<p<\infty$, where many of
the standard definitions coincide, see Section 1.4.

We consider the recovery problem in $L_{q}(M)$ for $1\leq q\leq\infty$. For an
operator $A\colon H^{s}_{p}(M)\to L_{q}(M)$ the worst case error is defined by

$e(A,H^{s}_{p}(M),L_{q}(M))\,:=\,\sup_{\|f\|_{H^{s}_{p}(M)}\leq
1}\|f-A(f)\|_{L_{q}(M)}.$

We consider recovery operators of the form $A=\varphi\circ N_{P}$, where
$P\subset M$ is a given (finite) set of sampling points, $N_{P}\colon
H^{s}_{p}(M)\to\mathbb{R}^{P}$ is the information mapping of the form
$N_{P}(f)=(f(x))_{x\in P}$ and $\varphi\colon\mathbb{R}^{P}\to L_{q}(M)$ is
any reconstruction map. The minimal worst case error that can be achieved with
a sampling operator of this form is denoted by

$e(P,H^{s}_{p}(M),L_{q}(M))\,:=\,\inf_{A=\varphi\circ
N_{P}}e(A,H^{s}_{p}(M),L_{q}(M)).$

It is a measure for the quality of the sampling point set $P$. If we only
allow linear reconstruction maps $\varphi$, which might be beneficial for
practical purposes, the infimum is denoted by $e^{\rm
lin}(P,H^{s}_{p}(M),L_{q}(M))$.

We have the following theorem. Here, the notation $A(P)\asymp B(P)$ means that
there exist implied constants $c,C>0$ such that $cA(P)\leq B(P)\leq CA(P)$ for
all nonempty finite point sets $P\subset M$. Below, the notation is also used
for a positive integer $n$ instead of $P$. Further, the distance function of a
nonempty subset $P$ of a metric space $(M,\operatorname{dist}_{M})$ is defined
by

$\operatorname{dist}_{M}(\,\cdot\,,P)\colon
M\to[0,\infty),\quad\operatorname{dist}_{M}(x,P):=\inf_{y\in
P}\,\operatorname{dist}_{M}(x,y).$

######  Theorem 1.

Let $M$ be a connected compact Riemannian manifold of dimension
$d\in\mathbb{N}$ and let $1<p<\infty$, $1\leq q\leq\infty$ and $s>d/p$. Then
we have for any nonempty and finite point set $P\subset M$ that

$e\big{(}P,H^{s}_{p}(M),L_{q}(M)\big{)}\,\asymp\,e^{\rm
lin}\big{(}P,H^{s}_{p}(M),L_{q}(M)\big{)}\,\asymp\,\big{\|}\operatorname{dist}_{M}(\,\cdot\,,P)\big{\|}_{L_{\gamma}(M)}^{\alpha},$

where the implied constants are independent of $P$ and

$\gamma=\left\\{\begin{array}[]{ll}s(1/q-1/p)^{-1},&q<p,\\\ \infty,&q\geq
p,\end{array}\right.\qquad\alpha=\left\\{\begin{array}[]{ll}s,&q<p,\\\
s-d(1/p-1/q),&q\geq p.\end{array}\right.$

Thus, we can characterize the quality of an arbitrary set of sampling points
$P$ by the $L_{\gamma}(M)$-norm (or quasi-norm) of the distance function. In
the case $\gamma=\infty$, this is nothing but the covering radius of $P$ in
$M$, which is the radius of the largest hole in the data set. In the case
$\gamma<\infty$, this is the radius of an average-sized hole in the data set
and sometimes called the distortion of $P$ in $M$, see, e.g., Zador [32].

The upper bound of Theorem 1 is achieved by a linear algorithm which is
constructed from the algorithm in [15], which in turn is based on moving least
squares, applied locally to sets where the point set is “dense enough”. In the
case $p>q$, this yields the improvement $\gamma<\infty$ compared to previous
works supposing a small covering radius. This enables us to show optimality of
other point sets, possibly with rather large holes in them.

In particular, we are interested in the quality of i.i.d. sampling points
which are distributed according to the normalized Riemannian volume measure.
We think this is a good and common model for sampling points that cannot be
chosen freely. By Theorem 1, it only remains to examine the covering radius
and the distortion of random points. We refer to Cohort [7] as well as
Reznikov and Saff [22] where this has been done in similar settings. We obtain
the following.

######  Proposition 1.

Let $X_{1},X_{2},\ldots$ be i.i.d. with respect to the normalized Riemannian
volume on $M$ and let $\alpha>0$. Then

$\mathbb{E}\,\left\|\operatorname{dist}_{M}(\,\cdot\,,\\{X_{1},\ldots,X_{n}\\})\right\|_{L_{\gamma}(M)}^{\alpha}\,\asymp\,\begin{cases}n^{-\alpha/d}&\text{if
}0<\gamma<\infty,\\\ (n/\log n)^{-\alpha/d}&\text{if
}\gamma=\infty,\end{cases}$

where the implied constants are independent of $n$.

This should be compared with the quality of optimal sampling points, for which
it follows from elementary volume comparison arguments, see also Lemma 4,
that, for all $0<\gamma\leq\infty$ and $\alpha>0$,

(1) $\inf_{P\subset M\colon|P|\leq
n}\left\|\operatorname{dist}_{M}(\,\cdot\,,P)\right\|_{L_{\gamma}(M)}^{\alpha}\,\asymp\,n^{-\alpha/d},$

where the infimum is over all point sets of cardinality at most $n$. We refer
to Iacobelli [12] and Kloeckner [14], where exact asymptotics for this so-
called minimal quantization error are obtained. Thus, the distortion of random
points is asymptotically optimal, while the covering radius of random points
exceeds the covering radius of optimal points by a logarithmic factor. We
therefore obtain that i.i.d. uniform sampling points are, on average,
asymptotically optimal for $L_{q}(M)$-approximation on $H^{s}_{p}(M)$ if and
only if $q<p$. In the case $q\geq p$, there is a loss of a logarithmic factor
compared to optimally chosen sampling points.

We also consider the problem of integration with respect to the Riemannian
volume $\operatorname{vol}_{M}$. The worst case error of an operator $A\colon
H^{s}_{p}(M)\to\mathbb{R}$ for the integration problem on $H^{s}_{p}(M)$ is
defined by

$e(A,H^{s}_{p}(M),{\rm INT})\,:=\,\sup_{\|f\|_{H^{s}_{p}(M)}\leq 1}\left|\int
f\,\mathrm{dvol}_{M}-A(f)\right|.$

The minimal worst case error that can be achieved with a given set of sampling
points $P\subset M$ is denoted by

$e(P,H^{s}_{p}(M),{\rm INT})\,:=\,\inf_{A=\varphi\circ
N_{P}}e(A,H^{s}_{p}(M),{\rm INT})\,,$

where the infimum ranges over all mappings
$\varphi\colon\mathbb{R}^{P}\to\mathbb{R}$. Note that, in this case, the
infimum will not change if we only minimize over all linear mappings
$\varphi$. This is a classical result due to Smolyak and Bakhvalov, see, e.g.,
Theorem 4.7 in the book by Novak and Woźniakowski [20]. Thus, it is no
restriction to assume that $A$ is of the form

$A(f)\,=\,\sum_{x\in P}w_{x}f(x),\quad w_{x}\in\mathbb{R}.$

The results that we obtain for the integration problem are the same as for the
$L_{1}(M)$-approximation problem.

######  Theorem 2.

Let $M$ be a connected compact Riemannian manifold and let $1<p<\infty$ and
$s>d/p$. Then we have the equivalence

$e\big{(}P,H^{s}_{p}(M),{\rm
INT}\big{)}\,\asymp\,\|\operatorname{dist}_{M}(\,\cdot\,,P)\|_{L_{sp^{*}}(M)}^{s}\,,$

where $p^{*}$ is the Hölder conjugate of $p$ and the implied constants are
independent of the point set $P\subset M$.

This improves upon Theorem 1 in Ehler, Gräf and Oates [9] by replacing the
covering radius of a point set with its distortion. In particular, we obtain
via Proposition 1 that independent and uniformly distributed points are, on
average, asymptotically optimal for numerical integration on $H^{s}_{p}(M)$
for all $1<p<\infty$ and close a logarithmic gap in Corollary 1 of [9].

As a geometric application of our results, we deduce an asymptotic equivalence
for the minimal weighted spherical $L_{2}$-discrepancy. To this end, consider
the $d$-dimensional sphere
$\mathbb{S}^{d}=\\{x\in\mathbb{R}^{d+1}:\|x\|_{2}=1\\}$ equipped with a
Riemannian metric inducing the usual geodesic distance
$\operatorname{dist}_{\mathbb{S}^{d}}$. Then the balls with respect to this
metric are the spherical caps

$C(x,t):=\\{y\in\mathbb{S}^{d}:x\cdot y\geq t\\}\quad\text{with center
}x\in\mathbb{S}^{d}\text{ and height }t\in[-1,1].$

Given points $x_{1},\ldots,x_{n}\in\mathbb{S}^{d}$ and weights
$w_{1},\ldots,w_{n}\in\mathbb{R}$ attached to them, their weighted spherical
$L_{2}$-discrepancy is given by

$D_{2}(\\{(x_{j},w_{j})\\}_{j=1}^{n}):=\Big{(}\int_{[-1,1]}\int_{\mathbb{S}^{d}}\Big{|}\sum_{j=1}^{n}w_{j}\mathbf{1}_{C(x,t)}(x_{j})-\sigma_{d}(C(x,t))\Big{|}^{2}\mathrm{d}\sigma_{d}(x)\mathrm{d}t\Big{)}^{1/2},$

where $\sigma_{d}$ is the normalized uniform measure on $\mathbb{S}^{d}$ and
$\mathbf{1}_{A}$ denotes the characteristic function of a set $A$. It is a
measure of equidistribution of the weighted point set and returns the average
approximation error when one uses the measure
$\sum_{j=1}^{n}w_{j}\delta_{x_{j}}$ to measure the volume of spherical caps.
For equal weights $w_{j}=1/n$ it reduces to the spherical $L_{2}$-discrepancy,
see, e.g., Drmota and Tichy [8, Chapter 2.1.3].

If we are interested in recovering the integral of a function $f$ in the
Sobolev space $H=H^{(d+1)/2}_{2}(\mathbb{S}^{d})$ with respect to $\sigma_{d}$
by means of evaluating $f$ at the points $P=\\{x_{1},\ldots,x_{n}\\}$, the
best we can do is to consider a linear algorithm $f\mapsto
Q_{P,w}(f):=\sum_{j=1}^{n}w_{j}f(x_{j})$, where
$w=(w_{1},\ldots,w_{n})\in\mathbb{R}^{n}$ are suitable weights. The
representation of the reproducing kernel of $H$, obtained by Brauchart and
Dick [3], together with the formula on the worst-case integration error for
functions in a reproducing kernel Hilbert space, give the identity

(2)
$e(Q_{P,w},H^{(d+1)/2}_{2}(\mathbb{S}^{d}),\mathrm{INT})\,=\,D_{2}(\\{(x_{j},w_{j})\\}_{j=1}^{n}),$

if the Sobolev space is normed as in [3], see Section 1.5 for details. Thus,
Theorem 2 has the following consequence for the minimal weighted spherical
$L_{2}$-discrepancy.

######  Corollary 1.

For all $d\in\mathbb{N}$, we have the equivalence

$\inf_{w_{1},\ldots,w_{n}}D_{2}(\\{(x_{j},w_{j})\\}_{j=1}^{n})\,\asymp\,\|\operatorname{dist}_{\mathbb{S}^{d}}(\,\cdot\,,P)\|_{L_{d+1}(\mathbb{S}^{d})}^{(d+1)/2}\,,$

where the implied constants are independent of the point set
$P\subset\mathbb{S}^{d}$.

From this and the lower bound (1) for the minimal distortion one can deduce in
particular the known lower bound on spherical $L_{2}$-discrepancy of any
$n$-point set which is of order $n^{-1/2-1/2d}$.

######  Remark 2.

Let us now elaborate on the details regarding the disclaimer. The lower bound
in Theorem 2 for smoothness $s\not\in\mathbb{N}$ and consequently the lower
bound in Corollary 1 for even $d$ rely on the validity of Proposition 3 below
in the case of non-integral $s$. However, it cannot be concluded from [15]
that the function in (1) is non-negative, see [15, Remark 7]. This may be
resolved using atomic decompositions. An updated proof will be published in an
upcoming version of [15].

We give a brief overview of the remainder of this article. In Section 1 we
introduce notation and concepts underlying our results and their proofs.
Section 2 contains the proofs of Theorems 1 and 2 and in Section 3 we analyze
the distortion of random points. In particular, we prove a limit theorem which
is stronger and more general than needed and might be of independent interest.

##  1\. Preliminaries

Let $d\in\mathbb{N}$ and $M=(M,g)$ be a connected compact Riemannian manifold
of dimension $d$, which is equipped with a smooth Riemannian metric $g$. Note
that $M$ is smooth, without boundary and closed. In the following we present
useful information needed later on which we derive from Chavel [5], Jost [13]
and Triebel [27, Chapter 7.2].

If $U\subset M$ is open and $x:U\to\mathbb{R}^{d}$ is any smooth chart, we can
identify the tangent space $T_{p}M$ at $p\in U$ with $\mathbb{R}^{d}$ by
taking the basis $\\{\frac{\partial}{\partial x_{i}}:i=1,\ldots,d\\}$ and any
tangent vector in $T_{p}M$ may be written as
$\xi=\sum_{i=1}^{d}\xi^{i}\frac{\partial}{\partial x_{i}}$,
$\xi^{i}\in\mathbb{R}$. In the coordinates given by $x$ the metric tensor $g$
at $p\in U$ can be written as a positive definite matrix, whose entries are
given by the inner product of the tangent vectors $\frac{\partial}{\partial
x_{i}}$ and $\frac{\partial}{\partial x_{j}}$ in the tangent space $T_{p}M$,
where $i,j=1,\ldots,d$. We denote these entries by $g_{ij}^{x}(z)$, where
$z=x(p)$. Then $g_{ij}^{x}:x(U)\to\mathbb{R}$ is a smooth function.

###  1.1. The exponential map

Choosing a basis $\\{e_{1},\ldots,e_{d}\\}$ of the tangent space $T_{p}M$ at
$p\in M$ which is orthonormal with respect to $g$ we can identify $T_{p}M$
with $\mathbb{R}^{d}$ and, abusing notation, we write $\exp_{p}$ for the
exponential map taking $y\in\mathbb{R}^{d}$ to $c_{v}(1)\in M$, where
$v=\sum_{i=1}^{d}y_{i}e_{i}$ and $c_{v}$ is the unique geodesic with
$c_{v}(0)=p$ and tangent vector $v$. This map is a diffeomorphism defined on a
neighbourhood around $0\in\mathbb{R}^{d}$ and the supremum of all $\varrho>0$
such that it is a diffeomorphism on the Euclidean ball
$B(0,\varrho):=\\{x\in\mathbb{R}^{d}:\left\|x\right\|_{2}<\varrho\\}$ is
called the local injectivity radius $r_{p}$. The (global) injectivity radius
is $\operatorname{inj}(M)=\inf_{p\in M}r_{p}$, which is positive as $M$ is
compact. For $0<\varrho<\operatorname{inj}(M)$ the set
$B_{M}(p,\varrho):=\exp_{p}(B(0,\varrho))$ is a geodesic ball with center $p$
and radius $\varrho$. Then $\exp_{p}^{-1}:B_{M}(p,\varrho)\to B(0,\varrho)$ is
a chart and the corresponding coordinates are called normal coordinates with
center $p$.

The Riemannian metric $g$ induces a metric $\operatorname{dist}_{M}$ on $M$,
which then becomes a complete metric space. We want to record the following
basic result, which allows us to locally compare the Riemannian distance with
the Euclidean distance. It is well known and can be deduced for example from
the proof of [13, Corollary 1.4.1].

######  Lemma 1.

Let $p\in M$ and $0<\varrho<\operatorname{inj}(M)$. The map
$\exp_{p}:B(0,\varrho)\to B_{M}(p,\varrho)$ is bi-Lipschitz. That is, there
are constants $0<c<C$ such that

$c\|z_{1}-z_{2}\|_{2}\,\leq\,\operatorname{dist}_{M}(\exp_{p}(z_{1}),\exp_{p}(z_{2}))\,\leq\,C\|z_{1}-z_{2}\|_{2}\qquad\text{for
all }z_{1},z_{2}\in B(0,\varrho).$

###  1.2. Integration

Let $U\subset M$ be open and let $x:U\to\mathbb{R}^{d}$ be a chart of $M$. If
$z\in x(U)$, we let $g^{x}(z)$ be the determinant of
$(g_{ij}^{x}(z))_{i,j=1}^{d}$. If $f:M\to\mathbb{R}$ is supported in $U$ and
measurable with respect to the Borel $\sigma$-algebra we define the integral
of $f$ by

(3)
$\int_{M}f\,\mathrm{dvol}_{M}:=\int_{x(U)}f(x^{-1}(z))\sqrt{g^{x}(z)}\,\mathrm{d}z,$

if this quantity exists and is finite. It is independent of the choice of the
coordinates $x$. We can extend the integral to global functions using a
partition of unity, which we now describe. Since $M$ is compact, there is a
finite atlas $\\{(U_{j},x_{j})\\}_{j\leq J}$ of $M$. For every such atlas,
there exists a subordinate partition of unity $\\{(U_{j},\psi_{j})\\}_{j\leq
J}$ satisfying

(4) $\psi_{j}\in C^{\infty}(M),\quad\mathrm{supp}\,\psi_{j}\subset U_{j},\quad
0\leq\psi_{j}(x)\leq 1,\quad\sum_{j=1}^{J}\psi_{j}(x)=1$

for all $j\leq J$ and $x\in M$, see, e.g., Tu [28, Proposition 13.6]. Here
supp denotes the support of a function. We define the integral of a measurable
function $f\colon M\to\mathbb{R}$ by setting

(5)
$\int_{M}f\,\mathrm{dvol}_{M}:=\sum_{j=1}^{J}\int_{M}f\psi_{j}\,\mathrm{dvol}_{M}$

if this quantity exists and is finite. This definition of the integral is
independent of the atlas and the partition of unity. In particular, (3) and
(5) yield the same result if $f$ is supported in $U$. As usual, the integral
over a Borel measurable set $E\subset M$ is defined by

$\int_{E}f\,\mathrm{dvol}_{M}:=\int_{M}f\,\mathbf{1}_{E}\,\mathrm{dvol}_{M}$

and the Riemannian volume of $E$ is defined by
$\operatorname{vol}_{M}(E)=\int_{M}\mathbf{1}_{E}\,\mathrm{dvol}_{M}$. Note
that the volume is well-defined and finite for all Borel sets $E\subset M$.

###  1.3. Bounded Geometry

Being compact, $M$ is of bounded geometry in the sense of Triebel [26, 27]
(see also Cheeger, Gromov and Taylor [6] and Shubin [23]). This means that for
every $0<\varrho<\operatorname{inj}(M)$ and every multiindex
$\alpha\in\mathbb{N}_{0}^{d}$ there exist constants $c>0$ and $c_{\alpha}>0$
such that

(6) $\sqrt{g(z)}\geq c\qquad\text{and}\qquad|D^{\alpha}g_{ij}(z)|\leq
c_{\alpha}\ \text{ for every multiindex }\alpha$

in the normal coordinates of every local chart
$(B_{M}(p,\varrho),\exp_{p}^{-1})$, where $z\in B(0,\varrho)$ is arbitrary.
From now on, we shall work in normal coordinates only, which justifies the
abuse of notation. In particular, we find constants $c,C>0$ such that
$c\leq\sqrt{g(z)}\leq C$ for all $z\in B(0,\varrho)$ in coordinates of the
chart $(B_{M}(p,\varrho),\exp_{p}^{-1})$. This follows from (6) via
$|g_{ij}(z)|\leq c_{0}$ and a determinant bound in terms of entries. From this
one can obtain a useful integral estimate, which we now state.

######  Lemma 2.

There exist constants $c,C>0$ such that for every non-negative function $f$
and every $p\in M$ and $0<\delta<\operatorname{inj}(M)/2$ it holds that

$c\int_{B(0,\delta)}f(\exp_{p}(z))\,\mathrm{d}z\,\leq\int_{B_{M}(p,\delta)}f(x)\,\mathrm{dvol}_{M}(x)\,\leq\,C\int_{B(0,\delta)}f(\exp_{p}(z))\,\mathrm{d}z.$

###### Proof.

We use the chart $\exp_{p}^{-1}\colon B_{M}(p,2\delta)\to B(0,2\delta)$ and
the definition (3) of the integral to compute

$\int_{B_{M}(z,\delta)}f(x)\,\mathrm{dvol}_{M}(x)=\int_{M}(f\,\mathbf{1}_{B_{M}(p,\delta)})(x)\,\mathrm{dvol}_{M}(x)\\\
=\int_{B(0,2\delta)}(f\,\mathbf{1}_{B_{M}(p,\delta)})(\exp_{p}(z))\sqrt{g(z)}\,\mathrm{d}z=\int_{B(0,\delta)}f(\exp_{p}(z))\sqrt{g(z)}\,\mathrm{d}z.$

Using the estimates $c\leq\sqrt{g(z)}\leq C$ completes the proof. ∎

###  1.4. Sobolev Spaces

In this subsection we collect useful information about the Bessel potential
(Sobolev) spaces $H^{s}_{p}(M)$, where $s>0$ and $1<p<\infty$. First we give
some details regarding their definition and then present an equivalent
definition by means of a partition of unity. This will be important for the
proof of Theorem 1. Recall that

$H^{s}_{p}(M)=\\{f\in L_{p}(M):(I-\Delta_{M})^{s/2}f\in L_{p}(M)\\},$

where $I$ is the identity on $L_{p}(M)$ and $\Delta_{M}$ is the Laplace-
Beltrami operator on $M$. The norm of $f\in H^{s}_{p}(M)$ is

$\left\|f\right\|_{H^{s}_{p}(M)}=\left\|(I-\Delta_{M})^{s/2}f\right\|_{L_{p}(M)}.$

In addition to [27] see also Strichartz [24] for details. Alternatively, the
spaces can be defined using a partition of unity and the corresponding spaces
on $\mathbb{R}^{d}$.

Let $\Delta$ be the usual Laplace operator on $\mathbb{R}^{d}$. Then the
Bessel potential space on $\mathbb{R}^{d}$ is given by

$\displaystyle H^{s}_{p}(\mathbb{R}^{d})$ $\displaystyle:=\\{f\in
L_{p}(\mathbb{R}^{d}):(I-\Delta)^{s/2}\in L_{p}(\mathbb{R}^{d})\\}$
$\displaystyle=\\{f\in
L_{p}(\mathbb{R}^{d}):\mathfrak{F}^{-1}((1+\|\xi\|_{2}^{2})^{s/2}\mathfrak{F}f)\in
L_{p}(\mathbb{R}^{d})\\},$

where $I$ is the identity on $L_{p}(\mathbb{R}^{d})$, with
$\left\|f\right\|_{H^{s}_{p}(\mathbb{R}^{d})}=\left\|\mathfrak{F}^{-1}((1+\|\xi\|_{2}^{2})^{s/2}\mathfrak{F}f)\right\|_{L_{p}}$
for $f\in H^{s}_{p}(\mathbb{R}^{d})$. Here $\mathfrak{F}$
($\mathfrak{F}^{-1}$) denotes the (inverse) Fourier transform.

In order to give the equivalent definition, we follow Triebel [27, Section 7],
who considers the more general scale of $F$-spaces, also known as Triebel-
Lizorkin spaces. Let $0<\delta<\operatorname{inj}(M)/8$ be small enough and
consider a finite covering of $M$ by the geodesic balls
$B_{j}:=B_{M}(p_{j},\delta),j\leq J,$ as well as a subordinate partition of
unity $\Psi=\\{(B_{j},\psi_{j})\colon j\leq J\\}$ satisfying (4) with $U_{j}$
replaced by $B_{j}$.

We can now state the equivalent definition.

######  Proposition 2.

Let $M$ and $\Psi=\\{(B_{j},\psi_{j})\colon j\leq J\\}$ be as above. Further,
let $s>0$ and $1<p<\infty$. Then the space of all functions $f\in L_{p}(M)$,
for which

$\|f\|_{H^{s}_{p}(M)}^{\Psi}:=\Big{(}\sum_{j=1}^{J}\|(f\psi_{j})\circ\exp_{p_{j}}\|_{H^{s}_{p}(\mathbb{R}^{d})}^{p}\Big{)}^{1/p}$

is finite, coincides with $H^{s}_{p}(M)$ and $\|\cdot\|_{H^{s}_{p}(M)}^{\Psi}$
defines an equivalent norm on it. Moreover, if $\Phi$ is another partition of
unity as above, the norms $\|\cdot\|_{W^{s}_{p}(M)}^{\Psi}$ and
$\|\cdot\|_{W^{s}_{p}(M)}^{\Phi}$ are equivalent.

###### Proof.

This follows from [27, Theorem 7.2.3] and the fact that the spaces $H^{s}_{p}$
are contained in the scale of $F$-spaces, see [25, Theorem 2.5.6] and [27,
Theorem 7.4.5] for this on $\mathbb{R}^{d}$ and $M$, respectively. ∎

######  Remark 3.

Actually, one can define the more general scales of Triebel-Lizorkin and Besov
spaces on $M$ completely analogously as in Proposition 2, and as in [15], our
results may be obtained for the Triebel-Lizorkin spaces $F^{s}_{p\tau}(M)$,
where $1<p<\infty$ and $0<\tau\leq\infty$.

It follows from Proposition 2 and the corresponding embedding on
$\mathbb{R}^{d}$ that $H^{s}_{p}(M)$ is continuously embedded into $C(M)$, the
space of continuous functions on $M$ whenever $s>d/p$. If $s\in\mathbb{N}$,
then $H^{s}_{p}(\mathbb{R}^{d})$ coincides with the Sobolev space
$W^{s}_{p}(\mathbb{R}^{d})$ of functions with finite norm

$\left\|f\right\|_{W^{s}_{p}(\mathbb{R}^{d})}:=\Big{(}\sum_{\left|\alpha\right|\leq
s}\left\|D^{\alpha}f\right\|_{L_{p}(\mathbb{R}^{d})}^{p}\Big{)}^{1/p},$

where $\alpha\in\mathbb{N}_{0}^{d}$ is a multiindex,
$|\alpha|=\alpha_{1}+\dots+\alpha_{d}$ and
$D^{\alpha}=\frac{\partial^{|\alpha|}}{\partial
x_{1}^{\alpha_{1}}\cdots\partial x_{d}^{\alpha_{d}}}f$ denotes a weak partial
derivative of order $|\alpha|$. For this fact note that norms on finite-
dimensional spaces are equivalent and see, e.g., [25, Theorem 2.5.6].
Analogously, one can use covariant derivatives to define a Sobolev space of
integer smoothness $s\in\mathbb{N}$ on a manifold and these coincide again
with $H^{s}_{p}(M)$, see Theorem 7.4.5 in [27]. More about the spaces
$H^{s}_{p}(M)$ may be found in the paper [2] by Brandolini et al., where the
eigensystem of $\Delta_{M}$ is employed and also $p=1,\infty$ is allowed. We
exclude these boundary values of $p$ because of Proposition 2.

###  1.5. Spherical cap discrepancy

As mentioned in the introduction, see (2), the minimal worst case error of a
point set for the integration problem on $H:=H^{(d+1)/2}_{2}(\mathbb{S}^{d})$
equals the minimal weighted spherical cap discrepancy of the point set. For
completeness, we give some details on this relation while relying on standard
techniques, see, e.g., Novak and Woźniakowski [21, Section 9].

According to [3, Theorem 1], an equivalent norm on the Hilbert space $H$ is
given via the reproducing kernel

$K\colon\mathbb{S}^{d}\times\mathbb{S}^{d}\to\mathbb{R},\quad
K(x,y)\,=\,\int_{[-1,1]}\int_{\mathbb{S}^{d}}\,\mathbf{1}_{C(z,t)}(x)\mathbf{1}_{C(z,t)}(y)\,\mathrm{d}\sigma_{d}(z)\mathrm{d}t.$

The representer $h\in H$ of the integral on $H$ is given by

$h(x)\,=\,\langle
h,K(x,\cdot)\rangle\,=\,\int_{\mathbb{S}^{d}}\,K(x,y)\,\mathrm{d}\sigma_{d}(y).$

Thus the worst case error of the cubature rule $f\mapsto
Q(f):=\sum_{j=1}^{n}w_{j}f(x_{j})$ can be computed as

$e(Q,H,\mathrm{INT})^{2}\,=\,\sup_{\|f\|_{H}\leq
1}\left|\int_{\mathbb{S}^{d}}\,f(x)\,\mathrm{d}\sigma_{d}(x)-\sum_{j=1}^{n}w_{j}f(x_{j})\right|^{2}\,=\,\left\|h-\sum_{j=1}^{n}w_{j}K(x_{j},\cdot)\right\|^{2}\\\
\,=\,\int_{\mathbb{S}^{d}}\int_{\mathbb{S}^{d}}K(x,y)\,\mathrm{d}\sigma_{d}(y)\mathrm{d}\sigma_{d}(x)-2\int_{\mathbb{S}^{d}}\sum_{j=1}^{n}w_{j}K(x_{j},y)\,\mathrm{d}\sigma_{d}(y)+\sum_{i,j=1}^{n}w_{i}w_{j}K(x_{i},x_{j}).$

Inserting the definition of the kernel $K$ and interchanging integrals, we
arrive at

$=\,\int_{[-1,1]}\int_{\mathbb{S}^{d}}\bigg{[}\sigma_{d}(C(z,t))^{2}-2\sum_{j=1}^{n}w_{j}\mathbf{1}_{C(z,t)}(x_{j})\,\sigma_{d}(C(z,t))\\\
\qquad+\sum_{i,j=1}^{n}w_{i}w_{j}\mathbf{1}_{C(z,t)}(x_{i})\mathbf{1}_{C(z,t)}(x_{j})\bigg{]}\mathrm{d}\sigma_{d}(z)\mathrm{d}t\,=\,D_{2}(\\{(x_{j},w_{j})\\}_{j=1}^{n}).$

##  2\. The proof of Theorems 1 and 2

Thanks to our preparations, we are able to lift Theorem 1 from Euclidean balls
to Riemannian manifolds. More precisely, we use the following proposition from
[15]. All parameters are given as in Theorem 1.

######  Proposition 3 ([15]).

Let $\delta>0$ and set $B=B(0,\delta)\subset\mathbb{R}^{d}$. Then there are
positive constants $C$ and $c$ such that the following holds for all finite
and nonempty point sets $P\subset B$.

  1. (1)

There is a non-negative function $f\in H_{p}^{s}(\mathbb{R}^{d})$ with support
in $B$ and $f|_{P}=0$ such that $\|f\|_{H_{p}^{s}(\mathbb{R}^{d})}\leq 1$ and

$\|f\|_{L_{q}(B)}\,\geq\,c\,\left\|\operatorname{dist}(\cdot,P)\right\|_{L_{\gamma}(B)}^{\alpha}.$

  2. (2)

There are bounded functions $u_{x}\colon B\to\mathbb{R}$ for $x\in P$ such
that for all $f\in H_{p}^{s}(\mathbb{R}^{d})$ with support in $B$ and
$\|f\|_{H_{p}^{s}(\mathbb{R}^{d})}\leq 1$ we have

$\bigg{\|}f-\sum_{x\in
P}f(x)u_{x}\bigg{\|}_{L_{q}(B)}\,\leq\,C\,\left\|\operatorname{dist}(\cdot,P\cup\partial
B)\right\|_{L_{\gamma}(B)}^{\alpha}.$

###### Proof.

The first property is proven precisely this way in [15] and thus we turn to
the second property. Let $Q\subset\partial B$ be finite. By Theorems 1 and 2
in [15] there are bounded functions $u_{x}\colon B\to\mathbb{R}$ for $x\in
P\cup Q$ such that we have for all $f\in H_{p}^{s}(B)$ with
$\|f\|_{H_{p}^{s}(B)}\leq 1$ that

$\bigg{\|}f-\sum_{x\in P\cup
Q}f(x)u_{x}\bigg{\|}_{L_{q}(B)}\leq\,C\,\left\|\operatorname{dist}(\cdot,P\cup
Q)\right\|_{L_{\gamma}(B)}^{\alpha}$

with a constant $C$ independent of $P$ and $Q$ (and $f$). See also [15, Remark
8]. If $f$ is supported in $B$, this turns into

$\bigg{\|}f-\sum_{x\in
P}f(x)u_{x}\bigg{\|}_{L_{q}(B)}\leq\,C\,\left\|\operatorname{dist}(\cdot,P\cup
Q)\right\|_{L_{\gamma}(B)}^{\alpha}$

Taking the infimum over all finite point sets $Q\subset\partial B$, we get the
statement. More precisely, we find a sequence of finite point sets
$Q_{k}\subset\partial B$ such that the $1/k$-balls centered at $Q_{k}$ cover
$\partial B$. Then $\operatorname{dist}(\cdot,P\cup Q_{k})$ converges
uniformly to $\operatorname{dist}(\cdot,P\cup\partial B)$ on $B$ and thus
$\left\|\operatorname{dist}(\cdot,P\cup
Q_{k})\right\|_{L_{\gamma}(B)}^{\alpha}$ converges to
$\left\|\operatorname{dist}(\cdot,P\cup\partial
B)\right\|_{L_{\gamma}(B)}^{\alpha}$. ∎

In the following, fix a partition of unity $\Psi=\\{(B_{j},\psi_{j})\colon
j\leq J\\}$ as in Proposition 2, where $B_{j}=B_{M}(p_{j},\delta)$ with
$0<\delta<\operatorname{inj}(M)/24$ small enough to accommodate for a factor
of three, see the proof of the lower bound below for a justification. We use
the shorthand $B=B(0,\delta)$ and $\exp_{j}=\exp_{p_{j}}$.

###  2.1. The upper bound

We construct our algorithm as follows. Let $f\in H^{s}_{p}(M)$ with
$\|f\|_{H^{s}_{p}(M)}\leq 1$ and $j\leq J$ be arbitrary but fixed for now. We
write

$f_{j}:=(\psi_{j}f)\circ\exp_{j}$

which is supported in $B$ and belongs to $H^{s}_{p}(\mathbb{R}^{d})$ with

$\|f_{j}\|_{H^{s}_{p}(\mathbb{R}^{d})}\leq\|f\|_{H^{s}_{p}(M)}^{\Psi}\leq
C_{\Psi}\|f\|_{H^{s}_{p}(M)}\leq C_{\Psi},$

where $C_{\Psi}$ is independent of $f$. This follows from Proposition 2. We
take the point set $P_{j}:=\exp_{j}^{-1}(P\cap B_{j})\subset B$. Applying
Proposition 3 to the rescaled functions $C_{\Psi}^{-1}f_{j}$ we get bounded
functions $u_{x}\colon B\to\mathbb{R}$, $x\in P_{j}$, such that we have for
all $f\in H^{s}_{p}(M)$ that

(7) $\Big{\|}f_{j}-\sum_{x\in
P_{j}}f_{j}(x)u_{x}^{(j)}\Big{\|}_{L_{q}(B)}\,\leq\,C_{\Psi}C\,\left\|\operatorname{dist}(\cdot,P_{j}\cup\partial
B)\right\|_{L_{\gamma}(B)}^{\alpha}.$

Define a function $A_{j}(f)$ on $B_{j}$ by

$A_{j}(f):=\Big{(}\sum_{x\in
P_{j}}f_{j}(x)\,u_{x}^{(j)}\Big{)}\circ\exp_{j}^{-1}=\sum_{p\in P\cap
B_{j}}(\psi_{j}f)(p)\,u_{p}^{(j)}$

and extend the function to $M$ by zero. Here we carried out the substitution
$p=\exp_{j}(x)$ and denote $u_{p}^{(j)}=u_{x}^{(j)}\circ\exp_{j}^{-1}$.
Rewriting (7) gives

(8)
$\left\|(\psi_{j}f-A_{j}(f))\circ\exp_{j}\,\right\|_{L_{q}(B)}\,\leq\,C\,\left\|\operatorname{dist}(\cdot,P_{j}\cup\partial
B)\right\|_{L_{\gamma}(B)}^{\alpha}.$

We proceed like this for every $j\leq J$. Note that the constant $C$ is
independent of $f$, $P$ and $j$. We set

$A(f):=\sum_{j=1}^{J}A_{j}(f).$

The recovery operator $A\colon H_{p}^{s}(M)\to L_{\infty}(M)$ is linear and
uses only function values at $P$. It remains to exhibit an appropriate upper
bound. This is now straightforward. The triangle inequality and
$\sum_{j=1}^{J}\psi_{j}\equiv 1$ imply

$\displaystyle\left\|f-A(f)\right\|_{L_{q}(M)}\leq\sum_{j=1}^{J}\left\|\psi_{j}f-A_{j}(f)\right\|_{L_{q}(M)}.$

We apply the upper estimate of Lemma 2 for every $j$ to the non-negative
functions $|\psi_{j}f-A_{j}(f)|^{q},$ supported in
$B_{j}=B_{M}(z_{j},\delta)$, and arrive at

$\left\|f-A(f)\right\|_{L_{q}(M)}\leq
C^{1/q}\sum_{j=1}^{J}\left\|(\psi_{j}f-A_{j}(f))\circ\exp_{j}\,\right\|_{L_{q}(B)}.$

Applying the local estimate (8) to each term in the sum yields

$\left\|f-A(f)\right\|_{L_{q}(M)}\lesssim\sum_{j=1}^{J}\big{\|}\operatorname{dist}(\cdot,P_{j}\cup\partial
B)\big{\|}_{L_{\gamma}(B)}^{\alpha}.$

Let us note that the constants of Lemma 1 and Lemma 2 are independent of $p$,
but we do not need this fact here and in the following, since we use the
lemmas only for a constant number of points $p_{j}$. Here and in the
following, the notation $A\lesssim B$ means that there exists an implicit
constant $C>0$, which does not depend on $f$ or $P$, such that $A\leq CB$
everywhere. We interpret $A\gtrsim B$ as $B\lesssim A$.

Using the lower estimate of Lemma 2 for
$\operatorname{dist}(\exp_{j}^{-1}(\cdot),P_{j}\cup\partial B)^{\gamma}$ for
every $j$ gives

(9)
$\left\|f-A(f)\right\|_{L_{q}(M)}\,\lesssim\,\sum_{j=1}^{J}\left\|\operatorname{dist}(\exp_{j}^{-1}(\cdot),P_{j}\cup\partial
B)\right\|_{L_{\gamma}(B_{j})}^{\alpha}.$

Note that $\exp_{j}(P_{j}\cup\partial B)=(P\cap B_{j})\cup\partial B_{j}$ and
Lemma 1 implies that

$\operatorname{dist}(\exp_{j}^{-1}(x),P_{j}\cup\partial B)\leq
c^{-1}\operatorname{dist}_{M}(x,(P\cap B_{j})\cup\partial B_{j})\leq
c^{-1}\operatorname{dist}_{M}(x,P)$

for some $c>0$ and all $x\in B_{j}$. Combining these inequalities and taking
the $L_{\gamma}(B_{j})$-norm we derive from (9) that

$\left\|f-A(f)\right\|_{L_{q}(M)}\,\lesssim\,\sum_{j=1}^{J}\left\|\operatorname{dist}_{M}(\cdot,P)\right\|_{L_{\gamma}(B_{j})}^{\alpha}\leq
J\left\|\operatorname{dist}_{M}(\cdot,P)\right\|_{L_{\gamma}(M)}^{\alpha}.$

This proves the upper bound for Theorem 1, where we allow the implicit
constants to depend on the chosen partition, and in particular on $J$. The
upper bound in Theorem 2 is achieved by the cubature rule
$Q(f):=\int_{M}A(f)\,\mathrm{dvol}_{M}$ which follows from

$\Big{|}\int_{M}f\,\mathrm{dvol}_{M}-\int_{M}A(f)\,\mathrm{dvol}_{M}\Big{|}\,\leq\,\|f-A(f)\|_{L_{1}(M)}.$

###  2.2. The lower bound

As in [15], the proof of the lower bound relies on the well-known technique of
fooling functions. Namely, we provide a non-negative function $f_{*}$ which
belongs to the unit ball of $H_{p}^{s}(M)$ that vanishes on the point set $P$.
Then any algorithm based on $P$ cannot distinguish $f_{*}$ from its negative
and for one of the two functions, the algorithm makes an error at least
$\|f_{*}\|_{L_{q}(M)}$, respectively
$\int_{M}f_{*}\,\mathrm{dvol}_{M}=\|f_{*}\|_{L_{1}(M)}$ for the integration
problem. It thus suffices to find $f_{*}$ with

(10)
$\|f_{*}\|_{L_{q}(M)}\,\gtrsim\,\left\|\operatorname{dist}_{M}(\,\cdot\,,P)\right\|_{L_{\gamma}(M)}^{\alpha}.$

In order to prepare the proof, we introduce a set of nice partitions of unity,
which are well adapted for constructing our fooling function. Namely, for each
$k\leq J$ we choose a partition of unity $\Psi_{k}$ by removing all elements
of the partition $\Psi$ which intersect the ball $B_{k}$ and adjoin the larger
ball $3B_{k}$ together with the sum of the deleted functions. In this way, we
obtain a partition with only one element not equal to the zero function on
$B_{k}$. More precisely, let $J_{k}:=\\{j\leq J:B_{j}\cap B_{k}=\emptyset\\}$
and

$\Psi_{k}:=\\{(3B_{j},\psi_{j})\colon j\in
J_{k}\\}\cup\\{(3B_{k},\widetilde{\psi}_{k})\\}\quad\text{with}\quad\widetilde{\psi}_{k}=\sum_{j\in
J_{k}^{C}}\psi_{j},$

where $J_{k}^{C}=\\{j\leq J:B_{j}\cap B_{k}\neq\emptyset\\}$. It is readily
checked that we have a partition of unity as before: Any point which belonged
to some $B_{j},j\in J_{k}^{C},$ is included in $3B_{k}$ and
$\widetilde{\psi}_{k}$ is supported in $3B_{k}$. Moreover, we gain the
property $\widetilde{\psi}_{k}(x)=1$ for $x\in B_{k}$. The enlargement of the
balls $B_{j}$, $j\in J_{k},$ to $3B_{j}$ is due to technical reasons since
only equally sized balls are used in [27]. As the Sobolev norms
$\left\|\cdot\right\|_{H^{s}_{p}(M)}^{\Psi_{k_{1}}}$ and
$\left\|\cdot\right\|_{H^{s}_{p}(M)}^{\Psi_{k_{2}}}$ are equivalent for all
$k_{1},k_{2}\leq J$, we can take suitable constants $c_{\Psi},C_{\Psi}>0$ such
that for all $f\in H^{s}_{p}(M)$ and all $k_{1},k_{2}\leq J$, we have

$c_{\Psi}\left\|f\right\|_{H^{s}_{p}(M)}^{\Psi_{k_{1}}}\leq\left\|f\right\|_{H^{s}_{p}(M)}^{\Psi_{k_{2}}}\leq
C_{\Psi}\left\|f\right\|_{H^{s}_{p}(M)}^{\Psi_{k_{1}}}.$

We begin to construct our fooling function. If $\gamma<\infty$, then because
of

$\displaystyle\|\operatorname{dist}_{M}(\cdot,P)\|_{L_{\gamma}(M)}^{\gamma}$
$\displaystyle=\sum_{j=1}^{J}\int_{M}\psi_{j}(x)\operatorname{dist}_{M}(x,P)^{\gamma}\,\mathrm{dvol}_{M}(x)$
$\displaystyle\leq\sum_{j=1}^{J}\int_{B_{j}}\operatorname{dist}_{M}(x,P)^{\gamma}\,\mathrm{dvol}_{M}(x),$

there must exist $i_{0}\leq J$ such that

(11)
$\int_{B_{i_{0}}}\operatorname{dist}_{M}(x,P)^{\gamma}\,\mathrm{dvol}_{M}(x)\,\geq\,\frac{1}{J}\,\|\operatorname{dist}_{M}(\cdot,P)\|_{L_{\gamma}(M)}^{\gamma}.$

If $\gamma=\infty$, we replace formula (11) by

$\|\operatorname{dist}_{M}(\cdot,P)\|_{L_{\infty}(B_{i_{0}})}=\|\operatorname{dist}_{M}(\cdot,P)\|_{L_{\infty}(M)}.$

We consider now the partition of unity $\Psi_{i_{0}}$. Recall that
$3B_{i_{0}}$ belongs to it and $\widetilde{\psi}_{i_{0}}=1$ on $B_{i_{0}}$.
The exponential maps $\exp_{j}$ are now considered as mappings from $3B$ to
$3B_{j}$ for $j\in J_{k}$.

We construct a fooling function on $B$ on which we consider the point set
$P_{i_{0}}=\exp_{i_{0}}^{-1}(P\cap B_{i_{0}})$. By Proposition 3 we get a non-
negative function $f\in H^{s}_{p}(\mathbb{R}^{d})$ with support in $B$,

$\left\|f\right\|_{H^{s}_{p}(\mathbb{R}^{d})}\leq 1,\quad
f|_{P_{i_{0}}}=0\quad\text{and}\quad\|f\|_{L_{q}(B)}\gtrsim\|\operatorname{dist}(\cdot,P_{i_{0}})\|_{L_{\gamma}(B)}^{\alpha}.$

We define the function $f_{\ast}$ by $f_{\ast}(x)=f(\exp^{-1}_{i_{0}}(x))$ if
$x\in B_{i_{0}}$ and zero else.

We compute that $\psi_{j}f_{\ast}\circ\exp_{j}=0$ if $j\in J_{i_{0}}$, since
$\psi_{j}\equiv 0$ on $B_{i_{0}}$ for those $j$, and
$\widetilde{\psi}_{i_{0}}f_{\ast}\circ\exp_{i_{0}}=f$. By definition

$\left\|f_{\ast}\right\|_{H^{s}_{p}(M)}^{\Psi_{i_{0}}}=\Big{(}\sum_{j\in
J_{i_{0}}}\|\psi_{j}f_{\ast}\circ\exp_{j}\|_{H^{s}_{p}(\mathbb{R}^{d})}^{p}+\|\widetilde{\psi}_{i_{0}}f_{\ast}\circ\exp_{i_{0}}\|_{H^{s}_{p}(\mathbb{R}^{d})}^{p}\Big{)}^{1/p}$

and thus, by Proposition 2,

$\left\|f_{\ast}\right\|_{H^{s}_{p}(M)}\,\asymp\,\left\|f_{\ast}\right\|_{H^{s}_{p}(M)}^{\Psi_{i_{0}}}=\left\|\widetilde{\psi}_{i_{0}}f_{\ast}\circ\exp_{i_{0}}\right\|_{H^{s}_{p}(\mathbb{R}^{d})}=\left\|f\right\|_{H^{s}_{p}(\mathbb{R}^{d})}\leq
1.$

Therefore, we can replace $f_{\ast}$ by a rescaled version such that
$\|f_{\ast}\|_{H^{s}_{p}(M)}\leq 1$. Additionally, we have $f_{\ast}|_{P}=0$.
In the case $q<\infty$, we apply Lemma 2 to the support $B_{i_{0}}$ to get

$\|f_{*}\|_{L_{q}(M)}\,\gtrsim\,\|f\|_{L_{q}(B)}\,\gtrsim\,\|\operatorname{dist}(\cdot,P_{i_{0}})\|_{L_{\gamma}(B)}^{\alpha}.$

It is straightforward that this relation also holds for $q=\infty$. It remains
to to prove a lower estimate of the form

(12)
$\|\operatorname{dist}(\cdot,P_{i_{0}})\|_{L_{\gamma}(B)}\,\gtrsim\,\left\|\operatorname{dist}_{M}(\cdot,P)\right\|_{L_{\gamma}(B_{i_{0}})},$

which by means of (11) yields that the function $f_{\ast}$ satisfies (10) and
concludes the proof of the lower bounds of Theorems 1 and 2.

We start with the right-hand side of (12). By Lemma 2 we have for
$\gamma<\infty$

$\left\|\operatorname{dist}_{M}(\cdot,P)\right\|_{L_{\gamma}(B_{i_{0}})}\,\lesssim\,\left\|\operatorname{dist}(\exp_{i_{0}}(\cdot),P)\right\|_{L_{\gamma}(B)}.$

For $\gamma=\infty$, we even have equality. We estimate for $z\in B$ using
Lemma 1

$\operatorname{dist}_{M}(\exp_{i_{0}}(z),P)\leq\min_{x\in P\cap
B_{i_{0}}}\operatorname{dist}_{M}(\exp_{i_{0}}(z),x)\,\lesssim\,\min_{y\in
P_{i_{0}}}\|z-y\|_{2}=\operatorname{dist}(z,P_{i_{0}}).$

Applying the $L_{\gamma}(B)$-norm gives

$\left\|\operatorname{dist}_{M}(\exp_{i_{0}}(\cdot),P)\right\|_{L_{\gamma}(B)}\,\lesssim\,\left\|\operatorname{dist}(\cdot,P_{i_{0}})\right\|_{L_{\gamma}(B)},$

and we arrive at (12).

##  3\. Random points

In this section, we will essentially prove Proposition 1.

For $\gamma=\infty$ the upper and lower bound from Proposition 1 follow from
Theorems 2.1 and 2.2 in Reznikov and Saff [22] and the Ahlfors-regularity of
$M$, see Lemma 4 below. For $0<\gamma<\infty$ the lower bound follows from
relation (1) since random points can be no better than optimal points. We now
proceed with the upper bound in the case $0<\gamma<\infty$. In fact, we prove
the following more general and more precise statement. This is a simple
modification of Cohort [7, Theorem 2].

######  Theorem 3.

Let $M$ be a compact Riemannian manifold of dimension $d\in\mathbb{N}$ and
$\gamma\in(0,\infty)$. Let $\nu$ be a Borel probability measure on $M$ which
is absolutely continuous with respect to $\operatorname{vol}_{M}$ with density
$h_{\nu}:M\to[c,\infty)$ for some $c>0$. Let $X_{1},X_{2},\ldots$ be i.i.d.
with law $\nu$. Then the distortion of the random point set
$P_{n}=\\{X_{1},\ldots,X_{n}\\}$ satisfies

$n^{\gamma/d}\int_{M}\operatorname{dist}_{M}(x,P_{n})^{\gamma}\,\mathrm{dvol}_{M}(x)\
\longrightarrow\
\omega_{d}^{-\gamma/d}\,\Gamma\Big{(}1+\frac{\gamma}{d}\Big{)}\int_{M}h_{\nu}(x)^{-\gamma/d}\,\mathrm{dvol}_{M}(x),$

as $n\to\infty$ in $L_{p}$ for all $p\in(0,\infty)$.

The proof of Proposition 1 is complete if we apply Theorem 3 for
$p=\alpha/\gamma$. Thus, it remains to prove Theorem 3. The only essential
thing we shall use is the following lemma, a proof of which can be found for
example in Blümlinger [1, Lemma 2].

######  Lemma 3.

Let $M$ be a compact $d$-dimensional Riemannian manifold. Then

$\lim_{r\to
0}\frac{\operatorname{vol}_{M}(B_{M}(p,r))}{\operatorname{vol}(B(0,r))}=1$

uniformly in $p\in M$, where $\operatorname{vol}$ denotes the $d$-dimensional
Lebesgue measure.

In other words, letting $\omega_{d}$ be the $d$-dimensional volume of the unit
ball of $\mathbb{R}^{d}$ we have $\lim_{r\to
0}\operatorname{vol}_{M}(B_{M}(p,r))r^{-d}=\omega_{d}$ uniformly in $p\in M$.
As a consequence of Lemma 3, one can obtain the well-known fact that the
volume and the metric on $M$ satisfy a compatibility condition which is also
known as Ahlfors-regularity.

######  Lemma 4.

Let $M$ be a compact $d$-dimensional Riemannian manifold. Then there are
constants $c,C>0$ such that

$c\,r^{d}\leq\operatorname{vol}_{M}(B_{M}(p,r))\leq C\,r^{d}\quad\text{for all
}0<r<\mathrm{diam}(M)\text{ and all }p\in M.$

We are now ready to prove the limit theorem for the distortion of i.i.d.
random points on a manifold.

###### Proof of Theorem 3.

To ease the notation in this proof, we denote the geodesic distance by
$\operatorname{dist}$ and the volume integral on $M$ by $\mathrm{d}x$. We set

$\displaystyle Z_{n}\,$
$\displaystyle:=\,n^{\gamma/d}\int_{M}\operatorname{dist}(x,P_{n})^{\gamma}\,\mathrm{d}x,$
$\displaystyle z\,$
$\displaystyle:=\,\omega_{d}^{-\gamma/d}\,\Gamma\Big{(}1+\frac{\gamma}{d}\Big{)}\int_{M}h_{\nu}(x)^{-\gamma/d}\mathrm{d}x.$

We show that

(13) $\mathbb{E}\,Z_{n}^{p}\to z^{p}\quad\text{for all }\ p\in\mathbb{N}.$

From this it follows that, for any even integer $p$,

$\mathbb{E}\,|Z_{n}-z|^{p}\,=\,\sum_{k=0}^{p}\binom{p}{k}(-z)^{p-k}\,\mathbb{E}\,Z_{n}^{k}\
\xrightarrow{n\to\infty}\ \sum_{k=0}^{p}\binom{p}{k}(-z)^{p-k}z^{k}\,=\,0,$

i.e., that $Z_{n}$ converges to $z$ in $L_{p}$ for all even integers $p$. By
Jensen’s inequality, the convergence holds for all $p\in(0,\infty)$, which
completes the proof.

We show (13). We have

$\mathbb{E}\,Z_{n}^{p}\,=\,\mathbb{E}\int_{(M)^{p}}\prod_{j=1}^{p}n^{\gamma/d}\operatorname{dist}(x_{j},P_{n})^{\gamma}\,\mathrm{d}x_{1}\cdots\mathrm{d}x_{p}.$

Interchanging the integrals yields

$\mathbb{E}\,Z_{n}^{p}\,=\,\int_{(M)^{p}}\mathbb{E}\prod_{j=1}^{p}n^{\gamma/d}\operatorname{dist}(x_{j},P_{n})^{\gamma}\,\mathrm{d}x_{1}\cdots\mathrm{d}x_{p}.$

We use
$a_{j}=\int_{\mathbb{R}_{+}}\mathbf{1}_{[v_{j},\infty)}(a_{j})\,\mathrm{d}v_{j}$
for $a_{j}=n^{\gamma/d}\operatorname{dist}(x_{j},P_{n})^{\gamma}$ and put

${\rm
I}_{n}(v_{1},\ldots,v_{p},x_{1},\ldots,x_{p})\,:=\,\mathbb{E}\,\prod_{j=1}^{p}\mathbf{1}_{[v_{j},\infty)}(n^{\gamma/d}\operatorname{dist}(x_{j},P_{n})^{\gamma})$

to see after an interchange of integrals that

$\mathbb{E}\,Z_{n}^{p}\,=\,\int_{(M)^{p}}\int_{(\mathbb{R}_{+})^{p}}{\rm
I}_{n}(v_{1},\ldots,v_{p},x_{1},\ldots,x_{p})\,\mathrm{d}v_{1}\cdots\mathrm{d}v_{p}\,\mathrm{d}x_{1}\cdots\mathrm{d}x_{p}.$

Since

$\int_{(M)^{p}}\int_{(\mathbb{R}_{+})^{p}}\exp\Big{(}-\omega_{d}\sum_{j=1}^{p}v_{j}^{d/\gamma}h_{\nu}(x_{j})\Big{)}\,\mathrm{d}v_{1}\cdots\mathrm{d}v_{p}\,\mathrm{d}x_{1}\cdots\mathrm{d}x_{p}\,=\,z^{p},$

the desired statement (13) follows from the dominated convergence theorem once
we show that

(14) ${\rm
I}_{n}(v_{1},\ldots,v_{p},x_{1},\ldots,x_{p})\,\xrightarrow{n\to\infty}\,\exp\Big{(}-\omega_{d}\sum_{j=1}^{p}v_{j}^{d/\gamma}h_{\nu}(x_{j})\Big{)}$

for almost all $v_{1},\ldots,v_{p},x_{1},\ldots,x_{p}$ and find an integrable
majorant of $I_{n}$. For the latter we observe that

${\rm
I}_{n}(v_{1},\ldots,v_{p},x_{1},\ldots,x_{p})=\,\mathbb{P}\left[n^{\gamma/d}\operatorname{dist}_{M}(x_{j},P_{n})^{\gamma}\geq
v_{j}\text{ for all }j\right]\\\ \,=\,\mathbb{P}\left[X_{i}\not\in
B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d})\text{ for all
}i,j\right]=\,\bigg{(}1-\nu\Big{(}\bigcup_{j=1}^{p}B_{M}\big{(}x_{j},v_{j}^{1/\gamma}n^{-1/d}\big{)}\Big{)}\bigg{)}^{n}.$

Clearly, it holds that $I_{n}=0$ whenever there is some $j\leq p$ with
$v_{j}^{1/\gamma}n^{-1/d}\geq\mathrm{diam}(M)$. In the other case, we use
Lemma 4 and the lower bound on the density of $\nu$ to find a constant
$c_{1}>0$ such that $\nu(B_{M}(x,r))\geq c_{1}r^{d}$ for all $x\in M$ and
$0<r<\mathrm{diam}(M)$. Therefore,

${\rm
I}_{n}(v_{1},\ldots,v_{p},x_{1},\ldots,x_{p})\,\leq\,\bigg{(}1-\max_{j\leq
p}\,\nu\big{(}B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d})\big{)}\bigg{)}^{n}\\\
\leq\,\bigg{(}1-\frac{c_{1}\max_{j\leq
p}\,v_{j}^{d/\gamma}}{n}\bigg{)}^{n}\,\leq\,\exp\left(-c_{1}\max_{j\leq
p}\,v_{j}^{d/\gamma}\right)\,\leq\,\exp\bigg{(}-\frac{c_{1}}{p}\sum_{j=1}^{p}\,v_{j}^{d/\gamma}\bigg{)}$

which gives an integrable majorant of $I_{n}$.

For the almost sure convergence, we use that for almost every choice of the
$x_{j}$ and $v_{j}$ we have for $n$ large enough that the balls
$B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d})$ are disjoint and thus

${\rm
I}_{n}(v_{1},\ldots,v_{p},x_{1},\ldots,x_{p})\,=\,\bigg{(}1-\sum_{j=1}^{p}\nu\big{(}B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d})\big{)}\bigg{)}^{n}.$

Define $a_{n}:=\sum_{j=1}^{p}\nu(B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d}))$. We
will establish the almost sure convergence of $na_{n}\to
a:=\omega_{d}\sum_{j=1}^{p}v_{j}^{d/\gamma}h_{\nu}(x_{j})$, from which it
follows that $(1-a_{n})^{n}\to{\rm e}^{-a}$. This implies the almost sure
convergence (14) and completes the proof.

To this end, write, for $1\leq j\leq p$,

$n\nu(B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d}))=\frac{n\operatorname{vol}_{M}(B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d}))}{\operatorname{vol}_{M}(B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d}))}\int_{B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d})}h_{\nu}(x)\,\mathrm{d}x,$

where $h_{\nu}\in L_{1}(M)$ is the density of $\nu$. By Lemma 3 the numerator
satisfies

$n\operatorname{vol}_{M}(B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d}))\,\to\,\omega_{d}v_{j}^{d/\gamma}\quad\text{as
}\ n\to\infty,$

and by the differentiation theorem of Lebesgue we have

$\frac{1}{\operatorname{vol}_{M}(B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d}))}\int_{B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d})}h_{\nu}(x)\,\mathrm{d}x\,\to\,h_{\nu}(x_{j})$

for almost all $x_{j}$ and $v_{j}$. Therefore,

$n\nu(B_{M}(x_{j},v_{j}^{1/\gamma}n^{-1/d}))\to\omega_{d}v_{j}^{d/\gamma}h_{\nu}(x_{j})$

and the desired convergence $na_{n}\to a$ follows. ∎

######  Remark 4.

In the case of $\gamma<\infty$ and the sphere $\mathbb{S}^{d}$ one can prove
the upper bound of Proposition 1 with the help of a covering by holes in the
random point set and Theorem 2.2 in [4] due to Brauchart et al. which states
that the average hole size behaves well.

### Acknowledgement

We thank Aicke Hinrichs for initiating the collaboration of the two authors on
this project and Martin Ehler for interesting discussions on the topic. Both
authors are supported by the Austrian Science Fund (FWF) Project F5513-N26,
which is a part of the Special Research Program _Quasi-Monte Carlo Methods:
Theory and Applications_. This research was funded in whole, or in part, by
the Austrian Science Fund (FWF), Project P34808. For the purpose of open
access, the authors have applied a CC BY public copyright license to any
Author Accepted Manuscript arising from this submission.

## References

  * [1] M. Blümlinger.  Asymptotic distribution and weak convergence on compact Riemannian manifolds.  Monatsh. Math., 110(3-4):177–188, 1990.
  * [2] L. Brandolini, C. Choirat, L. Colzani, G. Gigante, R. Seri, and G. Travaglini.  Quadrature rules and distribution of points on manifolds.  Ann. Sc. Norm. Super. Pisa Cl. Sci. (5), 13(4):889–923, 2014.
  * [3] J. S. Brauchart and J. Dick.  A characterization of Sobolev spaces on the sphere and an extension of Stolarsky’s invariance principle to arbitrary smoothness.  Constr. Approx., 38(3):397–445, 2013.
  * [4] J. S. Brauchart, A. B. Reznikov, E. B. Saff, I. H. Sloan, Y. G. Wang, and R. S. Womersley.  Random point sets on the sphere—hole radii, covering, and separation.  Exp. Math., 27(1):62–81, 2018.
  * [5] I. Chavel.  Riemannian geometry—a modern introduction.  Cambridge University Press, Cambridge, 1993.
  * [6] J. Cheeger, M. Gromov, and M. Taylor.  Finite propagation speed, kernel estimates for functions of the Laplace operator, and the geometry of complete Riemannian manifolds.  J. Differential Geometry, 17(1):15–53, 1982.
  * [7] P. Cohort.  Limit theorems for random normalized distortion.  Ann. Appl. Probab., 14(1):118–143, 2004.
  * [8] M. Drmota and R. F. Tichy.  Sequences, discrepancies and applications.  Springer-Verlag, Berlin, 1997.
  * [9] M. Ehler, M. Graef, and C. J. Oates.  Optimal Monte Carlo integration on closed manifolds.  Stat. Comput., 29:1203–1214, 2019.
  * [10] F. Filbir and H. N. Mhaskar.  Marcinkiewicz-Zygmund measures on manifolds.  J. Complexity, 27(6):568–596, 2011.
  * [11] K. Gröchenig.  Sampling, Marcinkiewicz-Zygmund inequalities, approximation, and quadrature rules.  J. Approx. Theory, 257:105455, 20, 2020.
  * [12] M. Iacobelli.  Asymptotic quantization for probability measures on Riemannian manifolds.  ESAIM Control Optim. Calc. Var., 22(3):770–785, 2016.
  * [13] J. Jost.  Riemannian geometry and geometric analysis.  Springer, Cham, 2017.
  * [14] B. Kloeckner.  Approximation by finitely supported measures.  ESAIM Control Optim. Calc. Var., 18(2):343–359, 2012.
  * [15] D. Krieg and M. Sonnleitner.  Random points are optimal for the approximation of Sobolev functions.  arXiv preprints, arXiv:2009.11275, 2020.
  * [16] Wanting Lu and Heping Wang.  Approximation and quadrature by weighted least squares polynomials on the sphere.  arXiv preprints, arXiv:2101.03658, 2021.
  * [17] H. N. Mhaskar.  Weighted quadrature formulas and approximation by zonal function networks on the sphere.  J. Complexity, 22(3):348–370, 2006.
  * [18] H. N. Mhaskar.  Eignets for function approximation on manifolds.  Appl. Comput. Harmon. Anal., 29(1):63–87, 2010.
  * [19] E. Novak and H. Triebel.  Function Spaces in Lipschitz Domains and Optimal Rates of Convergence for Sampling.  Constr. Approx., 23:325–350, 2006.
  * [20] E. Novak and H. Woźniakowski.  Tractability of multivariate problems. Volume I: Linear information.  European Mathematical Society (EMS), Zürich, 2008.
  * [21] E. Novak and H. Woźniakowski.  Tractability of multivariate problems. Volume II: Standard information for functionals.  European Mathematical Society (EMS), Zürich, 2010.
  * [22] A. Reznikov and E. B. Saff.  The covering radius of randomly distributed points on a manifold.  Int. Math. Res. Not. IMRN, 2016(19):6065–6094, 2016.
  * [23] M. A. Shubin.  Spectral theory of elliptic operators on noncompact manifolds.  Astérisque, (207):35–108, 1992.
  * [24] R. S. Strichartz.  Analysis of the Laplacian on the complete Riemannian manifold.  J. Functional Analysis, 52(1):48–79, 1983.
  * [25] H. Triebel.  Theory of function spaces.  Birkhäuser Verlag, Basel, 1983.
  * [26] H. Triebel.  Spaces of Besov-Hardy-Sobolev type on complete Riemannian manifolds.  Ark. Mat., 24(2):299–337, 1986.
  * [27] H. Triebel.  Theory of function spaces II.  Birkhäuser Verlag, Basel, 1992.
  * [28] L. W. Tu.  An introduction to manifolds.  Springer, New York, 2011.
  * [29] Heping Wang and I. H. Sloan.  On filtered polynomial approximation on the sphere.  J. Fourier Anal. Appl., 23(4):863–876, 2017.
  * [30] H. Wendland.  Local polynomial reproduction and moving least squares approximation.  IMA J. Numer. Anal., 21(1):285–300, 2001.
  * [31] H. Wendland.  Scattered Data Approximation.  Cambridge University Press, 2004.
  * [32] P. L. Zador.  Asymptotic quantization error of continuous signals and the quantization dimension.  IEEE Trans. Inform. Theory, 28(2):139–149, 1982.