remarkRemark hypothesisHypothesis claimClaim Distributed Uncertainty
Quantification of Kernel Interpolation on SpheresS.-B. Lin, X.Sun and D. Wang

# Distributed Uncertainty Quantification of Kernel Interpolation on Spheres
††thanks: The corresponding author is Di Wang. S. B. Lin was partially
supported by the National Key R&D Program of China (No.2020YFA0713900) and the
Natural Science Foundation of China [Grant No 62276209].

Shao-Bo Lin Center for Intelligent Decision-Making and Machine Learning,
School of Management, Xi’an Jiaotong University, Xi’an 710049, China ().
<EMAIL_ADDRESS>Xingping Sun  Department of Mathematics, Missouri State
University, Springfield, MO 65897, USA<EMAIL_ADDRESS>Di Wang
Center for Intelligent Decision-Making and Machine Learning, School of
Management, Xi’an Jiaotong University, Xi’an 710049, China ().
<EMAIL_ADDRESS>
###### Abstract

For radial basis function (RBF) kernel interpolation of scattered data,
Schaback [30] in 1995 proved that the attainable approximation error and the
condition number of the underlying interpolation matrix cannot be made small
simultaneously. He referred to this finding as an “uncertainty relation”, an
undesirable consequence of which is that RBF kernel interpolation is
susceptible to noisy data. In this paper, we propose and study a distributed
interpolation method to manage and quantify the uncertainty brought on by
interpolating noisy spherical data of non-negligible magnitude. We also
present numerical simulation results showing that our method is practical and
robust in terms of handling noisy data from challenging computing
environments.

###### keywords:

Kernel interpolation, distributed uncertainty mitigation, scattered spherical
data

68T05, 94A20, 41A35

##  1 Introduction

Numerical methods pertaining to scattered spherical data analysis are
increasingly needed and applied in a large swath of scientific fields
including geophysics [14], planetary science [35], computer graphic science
[33] and signal recovery [22]. In many of the real world application problems,
data collected are of the form $D:=\\{(x_{i},y_{i})\\}_{i=1}^{|D|}$, in which
$x_{i}\in\mathbb{S}^{d}$, the unit sphere embedded in the $(d+1)$-dimensional
Euclidean space $\mathbb{R}^{d+1}$, $y_{i}\in\mathbb{R}$, and $|D|$ denotes
the cardinality of the data set $D$. Data analysts aim to develop new and/or
apply existing numerical algorithms to generate an estimator $f_{D}$ that
approximates or fits the unknown but definitive relation between inputs and
outputs. We are interested in the following noisy data fitting model on
spheres:

(1) $y_{i}=f^{*}(x_{i})+\varepsilon_{i},\qquad\forall\ i=1,\dots,|D|,$

where $\\{\varepsilon_{i}\\}_{i=1}^{|D|}$ is a set of independent zero-mean
random noises satisfying $|\varepsilon_{i}|\leq M$ for some $M>0$ and $f^{*}$
is a function from $\mathbb{S}^{d}$ to $\mathbb{R}$ which we use to model the
relation between the input $x$ and output $y$.

Let $\phi$ be a positive definition function [13] on $\mathbb{S}^{d}$ and
$(\mathcal{N}_{\phi},\|\cdot\|_{\phi})$ the native space (also called
reproducing kernel Hilbert space) associated with $\phi$. Minimal norm kernel
interpolation defined by

(2)
$f_{D}:=\arg\min\limits_{f\in\mathcal{N}_{\phi}}\|f\|_{\phi},\qquad\mbox{s.t.}\quad
f(x_{i})=y_{i},\quad(x_{i},y_{i})\in D,$

is a classical and long-standing approach for spherical scattered data
fitting, in which $f_{D}$ is explicitly written as

(3) $f_{D}=\sum_{i=1}^{|D|}a_{i}\phi_{x_{i}},\qquad\mbox{with}\
(a_{1},\dots,a_{|D|})^{T}=:{\bf a}_{D}=\Phi_{D}^{-1}{\bf y}_{D}.$

Here $\phi_{x_{i}}$ denotes the function on $\mathbb{S}^{d}$:
$x\mapsto\phi(x_{i}\cdot x)$, ${\bf y}_{D}=(y_{1},\ldots,y_{|D|})^{T}$, and
$\Phi_{D}$ is the kernel matrix $(\phi(x_{i}\cdot x_{j}))_{i,j=1}^{|D|}$ in
which $x\cdot y$ is the usual dot product of $x$ and $y$. Customarily, it
requires orders of complexity $\mathcal{O}(|D|^{3})$ and
$\mathcal{O}(|D|^{2})$ in training and storage respectively to get such an
estimator as in (2). The “meshless” feature of kernel interpolation has
rendered itself useful in practice and attracted researchers’ attention on its
stability in numerical implementation or the lack thereof [26, 17].
Furthermore, approximation error estimates for kernel interpolation have been
established separately under the circumstances of fitting clean data [28, 27,
10, 9] and noisy data [11, 12, 8].

Despite its strength in utility, the stability in numerical implementation of
kernel interpolation has been a lingering concern. In 1995, Schaback used the
term “uncertainty relation” to describe the dichotomy between the
approximation error and condition number of kernel matrix $\Phi_{D}$ [30, 34].
(We will further elaborate on this topic in the next section.) In a nutshell,
Schaback’s uncertainty relation reveals that the approximation error and
condition number of kernel matrix $\Phi_{D}$ cannot be made small
simultaneously. An undesirable consequence of the uncertainty relation is that
kernel interpolation is susceptible to noisy data. Furthermore, our numerical
simulations (Figure 1) show that increasing sample size disproportionately
escalates severity of the uncertainty relation and negatively affects the
performance of kernel interpolation.

(a) RMSE and sample size (b) CNKM and sample size

Figure 1: Relations between training sample size and RMSE (rooted mean square
error)/CNKM (condition number of the kernel matrix). The training sample
inputs $\\{{x}_{i}\\}_{i=1}^{N}$ are generated by Womersley’s symmetric
spherical $t$-designs [36] on $\mathbb{S}^{2}$, and the corresponding outputs
are of the form $y_{i}=f(x_{i})+\varepsilon_{i}$, where $f$ is defined by (49)
below and $\varepsilon_{i}$ are independent Gaussian noise
$\mathcal{N}(0,\delta^{2})$. We ran simulations 30 times and recorded the
average RMSE using the kernel given as in (50) below.

A widely adopted approach to circumvent uncertainty in kernel interpolation is
the so called Tikhonov regularization which incorporates an additional
regularization parameter $\lambda>0$ to balance the approximation error and
condition number of the kernel matrix $\Phi_{D}+\lambda|D|I$. Hesse et al [11]
and Feng et al [8] analyzed the approximation error of Tikhonov regularization
fitting spherical data respectively with small and deterministic noise and
large and random noise. It is worth noting that deterministic noise and random
noise are merely two contrasting perspectives which data analysts take in
their effort to quantify uncertainty in kernel interpolation, as are the
mathematical tools utilized to tackle them.

This paper proposes and studies a new method: distributed kernel interpolation
(DKI). The basic idea of DKI is to break up judiciously the data set $D$ into
$m$ blocks $D_{1},\ldots,D_{m},$ where $m\in\mathbb{N}.$ Based on each
$D_{j}(1\leq j\leq m)$, we build an “interpolet” $f_{D_{j}}$. The final
product is a global estimator $f_{D}$ in the format of (14), which is
effectively a convex linear combination of interpolets $f_{D_{j}}$. We carry
out both theoretical analysis and numerical experiments in showing that DKI is
a robust way of fitting massive and noisy spherical data.

The rest of the paper is organized as follows. In Section 2, we give a
detailed account of the uncertainty relation under the setting of kernel
interpolation on spheres. In Section 3, we propose the DKI method and present
results of our theoretical analysis. Section 4 provides essential tools and
preparations for the proofs in Section 5, highlighting an employment of a
certain kind of quadrature rules of optimal orders incorporating an integral
operator approach. Section 6 devotes to the presentation of four numerical
simulation results.

##  2 Uncertainty Relation of Kernel Interpolation on Spheres

Let $L^{2}(\mathbb{S}^{d})$ be the Hilbert space with inner product

$\langle f,g\rangle=\int\limits_{\mathbb{S}^{d}}f(x)g(x)d\omega(x),\quad
f,g\in L^{2}(\mathbb{S}^{d}),$

where $d\omega$ denotes the rotational invariant probability measure on
$\mathbb{S}^{d}$. Let $\mathbb{H}^{d}_{k}$ be the subspace of
$L^{2}(\mathbb{S}^{d})$ consisting of all the homogeneous spherical harmonics
of degree $k$. Suppose that $\\{Y_{k,\ell}\\}_{\ell=1}^{Z(d,k)}$ is an
orthonormal basis of $\mathbb{H}_{k}^{d}$. Here $Z(d,k):=\mbox{dim}\
\mathbb{H}^{d}_{k}$. Let $P_{k}^{d+1}$ denote the Gegenbauer polynomial of
order $\frac{d-1}{2}$ and degree $k$ normalized so that $P_{k}^{d+1}(1)=1$. It
is known [25] that

(4)
$Z(d,k)=\left\\{\begin{array}[]{ll}\frac{2k+d-1}{k+d-1}{{k+d-1}\choose{k}},&\mbox{if}\
k\geq 1,\\\ 1,&\mbox{if}\ k=0,\end{array}\right.$

and that

(5)
$\sum_{\ell=1}^{Z(d,k)}Y_{k,\ell}(x)Y_{k,\ell}(x^{\prime})=\frac{Z(d,k)}{\Omega_{d}}P_{k}^{d+1}(x\cdot
x^{\prime}),\quad x,x^{\prime}\in\mathbb{S}^{d},$

in which $\Omega_{d}=\frac{2\pi^{\frac{d+1}{2}}}{\Gamma(\frac{d+1}{2})}$ is
the volume of $\mathbb{S}^{d}$. Equation (5) is recognized in the literature
as the addition formula for homogeneous spherical harmonics. For $f\in
L^{2}(\mathbb{S}^{d}),$ its Fourier coefficients $\hat{f}_{k,\ell}$ are
defined as
$\hat{f}_{k,\ell}:=\int_{\mathbb{S}^{d}}f(x)Y_{k,\ell}(x)d\omega(x).$ We take
the liberty of assuming that the Fourier coefficient definition above is
extended in a routine manner so that it is applicable to all the tempered
distributions on $\mathbb{S}^{d}.$

For a nonnegative integer $s$, denote by $\mathcal{P}_{s}^{d}$ the set of all
algebraic polynomials with degree at most $s$ defined on $\mathbb{S}^{d}$.
Then we have that $\mathcal{P}_{s}^{d}=\bigoplus_{k=0}^{s}\mathbb{H}^{d}_{k}$
and that dim$\mathcal{P}_{s}^{d}=\sum_{k=0}^{s}Z(d,k)=Z(d+1,s)\sim s^{d}$.
Here and hereafter by writing $A(p)\sim B(p)$ between the two nonnegative
quantities $A(p)$ and $B(p)$ depending on a parameter $p$ other than the
dimension $d$, we mean that there exist two constants $0<C_{1}<C_{2}$
depending only on $d$ such that $C_{1}B(p)\leq A(p)\leq C_{2}B(p).$ A
univariate tampered distribution $\phi$ supported on $[-1,1]$ is called a
spherical basis distribution (SBD) [27], if its Gegenbauer series expansion
$\phi(u)=\sum_{k=0}^{\infty}\hat{\phi}_{k}\frac{Z(d,k)}{\Omega_{d}}P_{k}^{d+1}(u)$
has all positive coefficients, i.e., $0<\hat{\phi}_{k}<\infty$ for all
$k=0,1,\ldots.$ Here the series convergence is under the topology of tampered
distributions. If in addition
$\sum_{k=0}^{\infty}\hat{\phi}_{k}{Z(d,k)}<\infty$, then $\phi$ is called a
spherical basis function (SBF). Given an SBD $\phi$, we define

$\mathcal{N}_{\phi}:=\left\\{f(x)=\sum_{k=0}^{\infty}\sum_{\ell=1}^{Z(d,k)}\hat{f}_{k,\ell}Y_{k,\ell}(x):\|f\|_{\phi}^{2}:=\sum_{k=0}^{\infty}\hat{\phi}_{k}^{-1}\sum_{\ell=1}^{Z(d,k)}\hat{f}_{k,\ell}^{2}<\infty\right\\}$

as the native space of $\phi$. In particular, if $\hat{\phi}_{k}=1$ for all
$k,$ then $\mathcal{N}_{\phi}$ coincides with $L^{2}(\mathbb{S}^{d})$.

The approximation power of the kernel interpolation scheme defined as in (2)
depends on the distribution of the point set of inputs
$\Lambda:=\\{x_{i}\\}_{i=1}^{|D|}$ on $\mathbb{S}^{d}$ and the spectrum of
$\Phi_{D}$; see e.g. [28, 27]. We follow what are prevalent in the scattered
data approximation literature in defining three parameters that quantify the
distribution of points $x_{1},\ldots,x_{|D|}$ on $\mathbb{S}^{d}$: the mesh
norm $h_{\Lambda}$, the separation radius $q_{\Lambda}$, and the mesh ratio
$\rho_{\Lambda}$:

(6) $\displaystyle h_{\Lambda}$
$\displaystyle:=\max_{x\in\mathbb{S}^{d}}\min_{x_{i}\in\Lambda}\mbox{dist}(x,x_{i}),$
(7) $\displaystyle q_{\Lambda}$ $\displaystyle:=\frac{1}{2}\min_{i\neq
i^{\prime}}\mbox{dist}(x_{i},x_{i^{\prime}}),$ (8)
$\displaystyle\rho_{\Lambda}$
$\displaystyle:=\frac{h_{\Lambda}}{q_{\Lambda}}.$

Here $\mbox{dist}(x,x^{\prime})$ is the geodesic (great circle) distance
between $x$ and $x^{\prime}$ on $\mathbb{S}^{d}$. If there is a constant
$\tau=\tau(d)$ depending only on $d$, such that $\rho_{\Lambda}\leq\tau$, then
we say that $\Lambda$ is $\tau$-quasi-uniformly distributed on
$\mathbb{S}^{d},$ or simply that $\Lambda$ is $\tau$-quasi-uniform. An
elementary sphere-packing argument shows that such a $\tau(d)$ must grow
exponentially with the dimension $d.$ We point out here that the mesh norm is
actually the Hausdorff distance between the two sets $\Lambda$ and
$\mathbb{S}^{d}.$ In the sequel, we will also refer to the points in $\Lambda$
as sampling sites.

If we have in (1) that $\varepsilon_{i}=0$ almost surely, then we refer to
this as the “noise-free model”, which has been extensively studied in the
literature; see e.g. [15, 28, 27, 10, 9]. In particular, the following result
was proved in [27, Theorem 5.5].

######  Lemma 2.1.

Suppose that $\phi$ is an SBF with $\hat{\phi}_{k}\sim k^{-2\gamma}$ with
$2\gamma>d$. Let $\alpha$ and $\beta$ be nonnegative real numbers satisfying
$0\leq\beta\leq\alpha\leq 1$ and $\alpha\gamma>d/2$. Suppose that $\psi$ and
$\varphi$ are SBFs such that

(9)
$\displaystyle\hat{\varphi}_{k}\sim\hat{\phi}_{k}^{\alpha},\quad\hat{\psi}_{k}\sim\hat{\phi}_{k}^{\beta}$

If $f^{*}\in\mathcal{N}_{\varphi}$, then the noise-free model in (1) of
kernel-$\phi$ interpolation yields the error estimate

(10) $\|f^{*}-f_{D}\|_{\psi}\leq
C\rho_{\Lambda}^{1-\alpha}h_{\Lambda}^{(\alpha-\beta)\gamma},$

where $C$ is a constant depending only on $d,\alpha,\beta,$ and $\gamma$.

However, a different picture emerges when one deals with noisy data. As is
well-known from basic numerical linear algebra, the stability or the lack
thereof for the kernel interpolation algorithm depend on the condition number
of the kernel matrix $\Phi_{D}$. In the RBF setting, Shaback [30] established
the following interesting inequality:

(11) $P^{2}(x)\left(\sigma_{\min}(\Phi^{(x)}_{D})\right)^{-1}\geq 1,\quad
x\in\mathbb{S}^{d}\setminus\\{x_{1},\ldots,x_{|D|}\\}.$

Here $\sigma_{\min}(A)$ denotes the smallest eigenvalue of a positive definite
matrix $A,$ $\Phi^{(x)}_{D}$ the $(|D|+1)\times(|D|+1)$ kernel matrix
associated with the $(|D|+1)$ points $x,x_{1},\ldots,x_{|D|}$, and $P(x)$ the
so called “power function” defined by

$P(x):=\|\phi_{x}-\mathcal{P}_{\Lambda}(\phi_{x})\|_{\phi},$

in which $\mathcal{P}_{\Lambda}$ denotes the projector from
$\mathcal{N}_{\phi}$ to its subspace
$S_{\Lambda}:=\mbox{span}\\{\phi_{x_{j}}\\}^{|D|}_{j=1}.$ Due to the
reminiscence of (11) to the uncertainty principle in quantum mechanics,
Schaback referred to it as the uncertainty relation of kernel interpolation.
Three timely remarks are in order. 1. The power function $P(x)$ has a direct
bearing on the rate of attainable approximation of the kernel interpolant; 2.
Schaback’s uncertainty relation carries over to the SBF setting in a routine
fashion; 3. The two quantities $\sigma_{\min}(\Phi^{(x)}_{D})$ and
$\sigma_{\min}(\Phi_{D})$ are indistinguishably close for appropriately chosen
$x\in\mathbb{S}^{d}\setminus\\{x_{1},\ldots,x_{|D|}\\}.$

Simply put, if the rate of attainable approximation of the kernel interpolant
is $R(h_{\Lambda})$, where $R:(0,\infty)\rightarrow(0,\infty)$ is an
increasing function and satisfies $\lim_{t\downarrow 0}R(t)=0,$ then
Schaback’s uncertainty relation asserts that
$\left(\sigma_{\min}(\Phi_{D})\right)^{-1}$ grows at least the magnitude
$R^{-1/2}(h_{\Lambda})$, resulting in a noise propagation of a sizable
proportion and accentuating the notion that for the type of noisy data
specified in (1), the approximation error of kernel interpolation of our
concern based on quasi-uniformly distributed sampling sites does not decrease
statistically when the sample size increases. The following result and our
numerical experiments further lend support to Schaback’s uncertainty relation;
see Figure 1.

######  Proposition 2.2.

Let $\Lambda$ be $\tau$-quasi-uniform for some $\tau>1$. Suppose that
$\hat{\phi}_{k}\sim k^{-2\gamma}$ with $\gamma>d/2$. Let
$\\{\varepsilon_{i}^{*}\\}_{i=1}^{|D|}$ be a set of random variables whose
supports are contained in $[-M,-\theta M]\cup[\theta M,M]$, where $0<\theta<1$
is an absolute constant. Then for all $f\in\mathcal{N}_{\varphi}$ with
$f|_{\Lambda}=0,$ there holds almost surely the following inequality:

(12) $\|f_{D}-f\|_{\phi}\geq\tilde{C},$

where $f_{D}$ is defined by (2) with $y_{i}=f(x_{i})+\varepsilon^{*}_{i}$ and
$\tilde{C}$ is a positive constant depending only on $\theta,\tau,\gamma,M,$
and $d$.

##  3 Distributed Kernel Interpolation

Corollary 2.2 shows that kernel interpolation performs poorly while
confronting noisy data of non-negligible magnitude. To overcome this major
drawback, we propose and study in this section a distributed kernel
interpolation (DKI) method, which is motivated by the “distributed learning”
in the literature [37, 19]. Figuratively speaking, this is a divide-and-
conquer strategy for uncertainty quantification. To elaborate, we describe the
method in three steps.

  * •

Step 1. Data set decomposition: For a fixed $1\leq m\leq|D|$, decompose the
data set $D$ into $m$ disjoint subsets
$D_{j}:=\\{(x_{i,j},y_{i,j}\\}_{i=1}^{|D_{j}|}$ so that
$D=\bigcup_{j=1}^{m}D_{j}$, $D_{j}\cap D_{j^{\prime}}=\varnothing$ for $j\neq
j^{\prime}$, and the input set $\Lambda_{j}$ of $D_{j}$ is $\tau$-quasi-
uniform for some $\tau>2$.

  * •

Step 2. Kernel interpolation on data sub-sets: On each subset $D_{j}$, carry
out the minimal norm interpolation as follows.

(13)
$f_{D_{j}}:=\arg\min\limits_{f\in\mathcal{N}_{\phi}}\|f\|_{\phi},\qquad\mbox{s.t.}\quad
f(x_{i,j})=y_{{i,j}},\quad(x_{i,j},y_{i,j})\in D_{j}.$

We will henceforth refer to the interpolant $f_{D_{j}}$ as an “interpolet”.

  * •

Step 3. Synthesization of interpolets: Build the DKI estimator by synthesizing
interpolets via weighted averaging

(14) $\overline{f}_{D}=\sum_{j=1}^{m}\frac{|D_{j}|}{|D|}f_{D_{j}}.$

|  $\Rightarrow$ |  |  $+$ |
---|---|---|---|---
Figure 2: The division of samples.

######  Remark 3.1.

Step 1 encompasses decomposing the whole data set $\Lambda$ as the union of
$m$ disjoint $\tau$-quasi-uniform sets. Figure 2 exhibits such an example. For
a general $\tau$-quasi-uniform data set, we adopt a selection-and-judgement
(SAJ) strategy for our decomposition purpose, for which the algorithm entails
an order $\mathcal{O}(|D|^{2})$ of complexity in computation. We present a
thorough analysis of the algorithm in Appendix A of the Supplementary Material
of the paper.

DKI in (14) has two major advantages over the classical KI. From the
computational point of view, DKI requires training complexity of order
$\mathcal{O}(\sum_{j=1}^{m}|D_{j}|^{3})$, which is considerably less than
$\mathcal{O}(|D|^{3})$ as required by KI. Furthermore, implementing DKI
requires $m$ matrix inversions respectively for $\Phi_{D_{j}},j=1,\dots,m$.
For each $j$, $D_{j}$ is $\tau$-quasi-uniform and $D_{j}$ pales in size to $D$
resulting in a much favorable minimal separation radius and therefore a
workable estimated value for $\sigma_{\min}(\Phi_{D_{j}})$, which translates
directly into superior algorithm execution stability. To further illustrate
the idea behind DKI, we carried out several rounds of simulations***We
employed a parallel computing technique in these simulations. More
specifically, interpolation on $D_{j}$ for different $j$’s are executed by
different PCs, which we refer to as “local machines”.; see the results in
Figure 3.

Figure 3: Relation between the number of local machines and the average
condition number of kernel matrices from local machines. The simulation
setting is the same as that in Figure 1.

######  Theorem 3.2.

Let $1\leq m\leq|D|.$ Suppose that $\phi,\psi$ and $\varphi$ are SBDs
satisfying the conditions set forth in Lemma 2.1. If $f^{*}\in N_{\varphi}$
and $\overline{f}_{D}$ is the DKI estimator defined by (14) and based on the
noisy data as in (1), then

$\displaystyle\mathbf{E}[\|\overline{f}_{D}-f^{*}\|_{\psi}^{2}]$
$\displaystyle\leq$
$\displaystyle\frac{C_{3}}{|D|}\sum_{j=1}^{m}|D_{j}|^{\frac{1+(2\beta-2\alpha)\gamma}{d}}\|f^{*}\|^{2}_{\varphi}$
$\displaystyle+$
$\displaystyle\frac{C_{3}M^{2}}{|D|^{2}}\sum_{j=1}^{m}|D_{j}|^{\frac{4\gamma+2\gamma\beta+2+2d}{d}},$

where $C_{3}$ is a constant depending only on $\alpha,\beta,\gamma,\tau$ and
$d$.

We deem the two sums on the right hand sides of (3.2) respectively as
(deterministic) fitting-error estimate and (stochastic) sampling-error
estimates. As opposed to KI, DKI gains strength in the sampling-error estimate
while giving away some power in fitting-error estimate. In the grand scheme of
things, this is a typical bias-variance trade-off. By choosing an optimal $m,$
DKI is capable of handling (statistically) data with large noise as the
following result shows.

######  Definition 3.3.

Let $0<\nu<1$ and $\tau>2$ be given. An input set $\Lambda$ is called a
$(\nu,\tau)$-decomposable if $\Lambda$ is the union of $m\sim|\Lambda|^{\nu}$
disjoint subsets $\Lambda_{1},\ldots,\Lambda_{m}$ satisfying: (i) Each
$\Lambda_{j}$ is $\tau$-quasi-uniform; (ii)
$|\Lambda_{j}|\sim|\Lambda_{j^{\prime}}|$ for all $j\neq j^{\prime}.$

######  Corollary 3.4.

Let $\hat{\phi}_{k}\sim k^{-2\gamma}$ with $2\gamma>d$. Suppose that the input
set $\Lambda$ is $(\nu,\tau)$-decomposable with
$\nu={\frac{6\gamma+2}{6\gamma+d+2}}$. If $f^{*}\in\mathcal{N}_{\phi}$, then
we have the following estimate

$\mathbf{E}[\|\overline{f}_{D}-f^{*}\|_{L^{2}(\mathbb{S}^{d})}^{2}]\leq
C_{4}|D|^{-\frac{2\gamma}{6\gamma+d+2}}(M^{2}+\|f^{*}\|_{\phi}^{2}),\quad
f^{*}\in\mathcal{N}_{\phi},$

where $C_{4}$ is a constant depending only on $\gamma,\tau$ and $d$.

In a sharp contrast to Proposition 2.2, Corollary 3.4 shows the consistency of
DKI in terms of handling noisy data of non-negligible magnitude and improves
the approximation performance of KI in challenging computing environments.

##  4 Operator Differences via Quadrature Rules

In this section, we first briefly exposit an integral-operator approach
initiated in [8] and then derive tight upper bounds for differences of
operators of our interest, obtaining a certain type of Sobolev sampling
inequalities [12] as a byproduct. Highlights of the section include
Proposition 4.6) and Lemma 4.10.

###  4.1 Integral operator approach and operator difference

Given a positive definite kernel $\phi$, define
$\mathcal{L}_{\phi}:L^{2}(\mathbb{S}^{d})\rightarrow L^{2}(\mathbb{S}^{d})$ to
be the integral operator given by

$\mathcal{L}_{\phi}f(x):=\int_{\mathbb{S}^{d}}\phi(x\cdot
x^{\prime})f(x^{\prime})d\omega(x^{\prime}).$

The following lemma established in [8] is a standard result to describe
relations among different SBDs via the integral operator $\mathcal{L}_{\phi}$.

######  Lemma 4.1.

Let $\phi$, $\psi$, $\varphi$ be SBDs satisfying (9). Then, for any
$f\in\mathcal{N}_{\psi}$ there holds

(16) $\|f\|_{\psi}=\|\mathcal{L}_{\phi}^{\frac{1-\beta}{2}}f\|_{\phi}.$

Moreover, for $f^{*}\in\mathcal{N}_{\varphi}$, there exists an
$h^{*}\in\mathcal{N}_{\varphi}$ such that

(17)
$f^{*}=\mathcal{L}_{\phi}^{\frac{\alpha-\beta}{2}}h^{*},\qquad\mbox{and}\quad\|f^{*}\|_{\varphi}=\|h^{*}\|_{\psi},$

where $g(\mathcal{L}_{\phi})f$ is defined by spectral calculus:

$g(\mathcal{L}_{\phi})f=\sum_{k=0}^{\infty}g(\hat{\phi}_{k})\sum_{\ell=1}^{Z(d,k)}\hat{f}_{k,\ell}Y_{k,\ell}(x).$

Lemma 4.1 shows the important role played by the integral operator
$\mathcal{L}_{\phi}$ in terms of bridging native spaces associated with
different SBDs. For the sake of clarity, we use $L_{\phi}$ to denote the
restriction of $\mathcal{L}_{\phi}$ on $\mathcal{N}_{\phi}$. Direct
computation yields the following lemma.

######  Lemma 4.2.

Let $\kappa=\sup_{x\in\mathbb{S}^{d}}\sqrt{\phi(x\cdot x)}$. For any
$g:[0,\kappa]\rightarrow\mathbb{R}_{+}$, there holds

(18) $g(\mathcal{L}_{\phi})f=g(L_{\phi})f,\qquad\forall\
f\in\mathcal{N}_{\phi}.$

Let $\\{w_{i}\\}_{i=1}^{|D|}$ be a set of real numbers. Define

$S_{D,W}f=(\sqrt{w_{1}}f(x_{1}),\dots,\sqrt{w_{|D|}}f(x_{|D|}))^{T}$

to be the weighted sampling operator from $\mathcal{N}_{\phi}$ to
$\mathbb{R}^{|D|}$ [31, 32]. Write $S^{T}_{D,W}{\bf c}=S_{D}^{T}{\sqrt{W}}{\bf
c}=\sum_{i=1}^{|D|}\sqrt{w_{i}}c_{i}\phi_{x_{i}},$ and

(19)
$L_{\phi,D,W}f=S^{T}_{D,W}S_{D,W}f=\sum_{i=1}^{|D|}w_{i}f(x_{i})\phi_{x_{i}}$

as the positive operator from $\mathcal{N}_{\phi}$ to $\mathcal{N}_{\phi}$,
where $W={\rm diag}(w_{1},\dots,w_{|D|})$. As usual, we will refer to the
above $w_{i}$’s as “weights”. If $w_{1}=\dots=w_{|D|}=1/|D|$, we denote
$S^{T}_{D,W}$ and $L_{\phi,D,W}$ as $S_{D}^{T}$ and $L_{\phi,D}$ respectively.
Since $\frac{1}{|D|}\Phi_{D}=S_{D}S_{D}^{T},$ it follows from (3) that

(20) $f_{D}=S_{D}^{T}(S_{D}S_{D}^{T})^{-1}S_{D}{\bf
y}_{D}=S_{D,W}^{T}(S_{D,W}S_{D,W}^{T})^{-1}{\bf y}_{D,W},$

where ${\bf y}_{D,W}=(\sqrt{w_{1}}y_{1},\dots,\sqrt{w_{|D|}}y_{|D|})^{T}.$

We call
$\mathcal{Q}_{\Lambda,s}:=\\{(w_{i,s},x_{i}):w_{i,s}>0\hbox{~{}and~{}}x_{i}\in\Lambda\\}$
a positive quadrature rule of order $s$ on $\mathbb{S}^{d}$ if

(21)
$\int_{\mathbb{S}^{d}}P(x)d\omega(x)=\sum_{x_{i}\in\Lambda}w_{i,s}P(x_{i}),\qquad\forall
P\in\mathcal{P}_{s}^{d}.$

Positive spherical quadrature rules such as the ones in (21) are discussed in
[23, 3]. In particular, Theorem 3.1 [3] asserts that for a $\tau$-quasi
uniform point set $\Lambda$, there is a positive quadrature rule of order $s$
with $s\leq\bar{c}_{1}|\Lambda|^{1/d}$ and
$0<w_{i,s}\leq\bar{c}_{2}|\Lambda|^{-1}$ for some constants
$\bar{c}_{1},\bar{c}_{2}$ depending only on $\tau,d,s$, which we will refer to
as a D-type quadrature rule for short, as it plays a crucial role in our
analysis in the present paper. For a D-type quadrature rule, we denote:

$W_{s}:={\rm diag}(w_{1,s},\dots,w_{|\Lambda|,s})\quad{\rm and}\quad
W^{1/2}_{s}:={\rm diag}(w^{1/2}_{1,s},\dots,w^{1/2}_{|\Lambda|,s}).$

Our main result in this section is the following theorem, which gives upper
bounds for norms of products of pertinent operators when the weights in (19)
are positive.

######  Theorem 4.3.

Let
$\mathcal{Q}_{\Lambda,s}:=\\{(w_{i,s},x_{i}):w_{i,s}>0\hbox{~{}and~{}}x_{i}\in\Lambda\\}$
be a D-type quadrature rule of order $s$ on $\mathbb{S}^{d}$. If
$\hat{\phi}_{k}\sim k^{-2\gamma}$ with $\gamma>d/2$, then there is a constant
$C^{\prime}$ depending only on $\gamma$ and $d$, such that for any
$\lambda\geq C^{\prime}s^{-2\gamma}$, there holds

(22) $\|(L_{\phi,D,W_{s}}+\lambda I)^{-1/2}(L_{\phi}+\lambda I)^{1/2}\|\leq
2\sqrt{3}/3$

and

(23) $\|(L_{\phi,D,W_{s}}+\lambda I)^{1/2}(L_{\phi}+\lambda
I)^{-1/2}\|\leq\sqrt{6}/2,$

where $g(L_{\phi,D,W_{s}})$ and $g(L_{\phi})$ are also defined by spectral
calculus for $g:R_{+}\rightarrow\mathbb{R}$.

The proof of Theorem 4.3 is involved and will be given in the next subsection.
Here we emphasize its usefulness in deriving approximation error estimates for
KI’s (2) and DKI’s (14). In particular, we use Theorem 4.3 to prove a class of
Sobolev-type sampling inequalities.

######  Corollary 4.4.

Let $\Lambda$ be a $\tau$-quasi-uniform set and
$\mathcal{Q}_{\Lambda,s}:=\\{(w_{i,s},x_{i}):w_{i,s}>0\hbox{~{}and~{}}x_{i}\in\Lambda\\}$
a D-type quadrature rule of order $s$ on $\mathbb{S}^{d}$. Suppose that
$\phi,\psi$ are SBDs satisfying $\hat{\phi}\sim k^{-2\gamma}$ with
$\gamma>d/2$ and $\hat{\psi}\sim(\hat{\phi})^{\beta}$ for some $0\leq\beta\leq
1.$ Then there exists a constant $C^{*}$ depending only on $\beta,\gamma$, and
$d,$ such that for any $\lambda\geq C^{*}s^{-2\gamma}$ and any
$f\in\mathcal{N}_{\phi}$, there holds

$\|f\|_{\psi}\leq(4/3)^{(1-\beta)/2}\left(\lambda^{(1-\beta)/2}\|f\|_{\phi}+\lambda^{-\beta/2}\left(\sum_{i=1}^{|D|}w_{i,s}(f(x_{i}))^{2}\right)^{1/2}\right).$

For a quasi-uniform point set $\Lambda$, we have $h_{\Lambda}\sim
q_{\Lambda}\sim{|D|}^{-1/d}$. Corollary 4.4 then yields the following sampling
inequality

$\|f\|_{\psi}\leq
C_{2}^{*}\left(\lambda^{1/2}\|f\|_{\phi}+\left(\frac{1}{|D|}\sum_{i=1}^{|D|}(f(x_{i}))^{2}\right)^{1/2}\right),$

where $C_{2}^{*}$ is a constant independent of $|D|$. In particular, the case
$\beta=0$ gives rise to the $L^{2}$ sampling inequality on spheres established
in [11, Theorem 5.1]. We caution, however, that this implication is valid only
under the assumption that the point set $\Lambda$ is quasi-uniform.

######  Proof 4.5 (Proof of Corollary 4.4).

For a given $f\in\mathcal{N}_{\phi}$ and $0\leq\beta\leq 1$, we apply Lemma
4.1 and Theorem 4.3 to get

$\displaystyle\|f\|_{\psi}$ $\displaystyle=$
$\displaystyle\|L_{\phi}^{(1-\beta)/2}f\|_{\phi}$ $\displaystyle\leq$
$\displaystyle\|(L_{\phi}+\lambda I)^{(1-\beta)/2}(L_{\phi,D,W_{s}}+\lambda
I)^{-(1-\beta)/2}\|\|(L_{\phi,D,W_{s}}+\lambda I)^{(1-\beta)/2}f\|_{\phi}$
$\displaystyle\leq$
$\displaystyle(4/3)^{(1-\beta)/2}\lambda^{-\beta/2}\|(L_{\phi,D,W_{s}}+\lambda
I)^{1/2}f\|_{\phi}$ $\displaystyle\leq$
$\displaystyle(4/3)^{(1-\beta)/2}\lambda^{-\beta/2}\|L_{\phi,D,W_{s}}^{1/2}f\|_{\phi}+(4/3)^{(1-\beta)/2}\lambda^{-(1-\beta)/2}\|f\|_{\phi}.$

In developing the above inequalities, we have also used the basic inequality
$(a+b)^{1/2}\leq a^{1/2}+b^{1/2}$ for nonnegative real numbers $a,b$ and the
well-known Cordes inequality [1] for positive operators $A,B$,

(24) $\|A^{u}B^{u}\|\leq\|AB\|^{u},\qquad 0\leq u\leq 1.$

By the definition of $L_{\phi,D,W_{s}}$, we deduce

$\displaystyle\|L_{\phi,D,W_{s}}^{1/2}f\|_{\phi}^{2}=\langle
L_{\phi,D,W_{s}}^{1/2}f,L_{\phi,D,W_{s}}^{1/2}f\rangle_{\phi}=\langle
f,L_{\phi,D,W_{s}}f\rangle_{\phi}=\langle
f,S_{D}^{T}W_{s}S_{D}f\rangle_{\phi}$ $\displaystyle=$
$\displaystyle\langle\sqrt{W_{s}}S_{D}f,\sqrt{W_{s}}S_{D}f\rangle_{\phi}=\sum_{i=1}^{|D|}w_{i,s}(f(x_{i}))^{2}.$

It then follows that

$\displaystyle\|f\|_{\psi}$ $\displaystyle\leq$
$\displaystyle(4/3)^{(1-\beta)/2}\lambda^{-\beta/2}\left(\sum_{i=1}^{|D|}w_{i,s}(f(x_{i}))^{2}\right)^{1/2}+(4/3)^{(1-\beta)/2}\lambda^{-(1-\beta)/2}\|f\|_{\phi},$

which is the desired result.

###  4.2 Quadrature rule for products of functions

To prove Theorem 4.3, we need a quadrature rule for products of two functions
in $\mathcal{N}_{\phi}$ associated with certain positive operators of our
interest.

######  Proposition 4.6.

Let $\hat{\phi}_{k}\sim k^{-2\gamma}$ with $\gamma>d/2$ and $u,v\in[0,1/2]$.
If $\Lambda=\\{x_{i}\\}_{i=1}^{|\Lambda|}$ is $\tau$-quasi uniform and
$s\leq\tilde{c}_{1}|\Lambda|^{1/d}$, then for a D-type quadrature rule
$\mathcal{Q}_{\Lambda,s}=\\{(w_{i,s},x_{i}):\hbox{~{}and~{}}x_{i}\in\Lambda\\}$
of order $s$ and each pair of $f,g\in\mathcal{N}_{\phi}$, there holds

$\displaystyle\left|\int_{\mathbb{S}^{d}}(\eta_{\lambda,u}(L_{\phi})f)(x)(\eta_{\lambda,v}(L_{\phi})g)(x)d\omega(x)-\sum_{x_{i}\in\Lambda}w_{i,s}\left[(\eta_{\lambda,u}(L_{\phi})f)(x_{i})(\eta_{\lambda,v}(L_{\phi})g)(x_{i})\right]\right|$
$\displaystyle\leq\tilde{c}^{\prime}\lambda^{-\max\\{u,v\\}}s^{-\gamma}\|f\|_{\phi}\|g\|_{\phi},$

in which $\eta_{\lambda,u}(L_{\phi})f=(L_{\phi}+\lambda I)^{-u}f$ for $0\leq
u\leq 1/2$ and $0<\lambda\leq 1$, and $\tilde{c}^{\prime}$ is a constant
depending only on $\gamma,\kappa,u,v,\tau$ and $d$.

Proposition 4.6 extends [2, Corollary 3.6] which asserts that

(25)
$\left|\int_{\mathbb{S}^{d}}f(x)d\omega(x)-\sum_{x_{i}\in\Lambda}w_{i,s}f(x_{i})\right|\leq\tilde{c}_{1}^{\prime}s^{-\gamma}\|f\|_{\phi},\quad
f\in\mathcal{N}_{\phi},$

where $\tilde{c}_{1}^{\prime}$ is a constant depending only on $\gamma,d$. As
a matter of fact, setting $u=v=0$ and $g(x)\equiv 1$ in Proposition 4.6
recovers (25). Furthermore, the results of Proposition 4.6 improve those of
[8, Proposition 1], which gives the following estimate:

$\displaystyle\left|\int_{\mathbb{S}^{d}}(\eta_{\lambda,u}(L_{\phi})f)(x)(\eta_{\lambda,v}(L_{\phi})g)(x)d\omega(x)-\sum_{x_{i}\in\Lambda}w_{i,s}\left[(\eta_{\lambda,u}(L_{\phi})f)(x_{i})(\eta_{\lambda,v}(L_{\phi})g)(x_{i})\right]\right|$
$\displaystyle\leq\tilde{c}\|f\|_{\phi}\|g\|_{\phi}\begin{cases}\lambda^{-u-v}s^{-2\gamma}+s^{-(1-u-v)\gamma},&\mbox{if}\
u+v<1,\\\ \lambda^{-u-v}s^{-2\gamma}+\log s,&\mbox{if}\ u+v=1.\end{cases}$

Obtaining the sharper upper bound here requires the following two lemmas from
respectively Narcowich et al [27, Corollary 5.4] and Dai [5].

######  Lemma 4.7.

Let $\hat{\phi}_{k}\sim k^{-2\gamma}$ with $\gamma>d/2$. Let $\Lambda$ be a
finite subset of $\mathbb{S}^{d}$. Then there exists a constant
$\tilde{c}_{1}$ depending only on $\gamma$ and $d$, such that for any
$f\in\mathcal{N}_{\phi}$ and $s^{*}\geq\tilde{c}_{1}/q_{\Lambda}$, there is a
$P_{s^{*}}\in\mathcal{P}_{s^{*}}^{d}$ satisfying $\|P_{s^{*}}\|_{\phi}\leq
6\|f\|_{\phi}$ and $\|P_{s^{*}}\|_{L^{2}(\mathbb{S}^{d})}\leq
6\|f\|_{L^{2}(\mathbb{S}^{d})}$. Moreover, we have

(26) $f(x_{i})=P_{s^{*}}(x_{i}),\qquad i=1,\dots,|\Lambda|,$

and

(27)
$\|f-P_{s^{*}}\|_{L^{2}(\mathbb{S}^{d})}\leq\tilde{c}_{2}h_{\Lambda}^{\gamma}\|f\|_{\phi},$

where $\tilde{c}_{2}$ is a constant depending only on $d,\beta$ and $\gamma$.

######  Lemma 4.8.

Let $s\in\mathbb{N}$ and $\Lambda$ be quasi-uniform. Suppose that
$\mathcal{Q}_{\Lambda,s}:=\\{(w_{i,s},x_{i}):x_{i}\in\Lambda\\}$ is a D-type
quadrature rule of order $s$ on $\mathbb{S}^{d}$. Then for any
$P\in\Pi_{s^{\prime}}^{d}$ with $s^{\prime}\in\mathbb{N}$, there holds

$\displaystyle\sum_{x_{i}\in\Lambda}w_{i,s}|P(x_{i})|^{2}$ $\displaystyle\leq$
$\displaystyle\tilde{c}_{1}(s^{\prime}/s)^{d}\|P\|^{2}_{L^{2}(\mathbb{S}^{d})},\qquad
s^{\prime}>\lfloor s/3\rfloor,$

where $\tilde{c}_{1}$ is a constant depending only on $d$.

The above lemma can be derived by combining [5, Lemma 4.4] and [5, Lemma 4.5]
(see also [6, Theorem 2.1] and [24, Theorem 3.3]). With the help of above
lemmas, we are in a position to prove Proposition 4.6.

######  Proof 4.9 (Proof of Proposition 4.6).

Let $\tilde{c}\geq\tilde{c_{1}}$ be a positive constant properly chosen so
that $s:=\tilde{c}/q_{\Lambda}$ satisfies the pertinent interpolation
condition in Lemma 4.7. Let $P_{f}^{*}$ and $P_{g}^{*}$ be, respectively, the
interpolating polynomials (in accordance to Lemma 4.7) from $\Pi^{d}_{s}$ for
$\eta_{\lambda,u}(L_{\phi})f$ and
$\eta_{\lambda,v}(L_{\phi})g\in\mathcal{N}_{\phi}$. Using a standard “zero-
sum” technique and Hölder’s inequality, we derive that

$\displaystyle\left|\int_{\mathbb{S}^{d}}(\eta_{\lambda,u}(L_{\phi})f)(x)(\eta_{\lambda,v}(L_{\phi})g)(x)d\omega(x)-\sum_{x_{i}\in\Lambda}w_{i,s}\left[(\eta_{\lambda,u}(L_{\phi})f)(x_{i})(\eta_{\lambda,v}(L_{\phi})g)(x_{i})\right]\right|$
$\displaystyle\leq\mathcal{A}_{1}+\mathcal{A}_{2}+\mathcal{A}_{3},$

in which

$\displaystyle\mathcal{A}_{1}$ $\displaystyle:=$
$\displaystyle\|(\eta_{\lambda,u}(L_{\phi})f)\|_{L^{2}(\mathbb{S}^{d})}\|(\eta_{\lambda,v}(L_{\phi})g)-P_{g}^{*}\|_{L^{2}(\mathbb{S}^{d})},$
$\displaystyle\mathcal{A}_{2}$ $\displaystyle:=$
$\displaystyle\|P_{g}^{*}\|_{L^{2}(\mathbb{S}^{d})}\|(\eta_{\lambda,u}(L_{\phi})f)-P_{f}^{*}\|_{L^{2}(\mathbb{S}^{d})},$
$\displaystyle\mathcal{A}_{3}$ $\displaystyle:=$
$\displaystyle\left|\int_{\mathbb{S}^{d}}P_{f}^{*}(x)P_{g}^{*}(x)d\omega(x)-\sum_{x_{i}\in\Lambda}w_{i,s}P_{f}^{*}(x_{i})P_{g}^{*}(x_{i})\right|.$

Since $0\leq u,v\leq 1/2$, we get from (16) that

$\|(\eta_{\lambda,u}(L_{\phi})f)\|_{L^{2}(\mathbb{S}^{d})}\|\leq\kappa^{1-2u}\|f\|_{\phi},\quad\|(\eta_{\lambda,v}(L_{\phi})g)\|_{L^{2}(\mathbb{S}^{d})}\|\leq\kappa^{1-2v}\|g\|_{\phi}.$

We use the result of Lemma 4.7 to bound $\mathcal{A}_{1}$ and
$\mathcal{A}_{2}$ as follows.

(28)
$\mathcal{A}_{1}\leq\tilde{c}_{2}\kappa^{1-2u}h_{\Lambda}^{\gamma}\|\eta_{\lambda,v}(L_{\phi})g\|_{\phi}\|f\|_{\phi}\leq\tilde{c}_{2}\kappa^{1-2u}\lambda^{-v}h_{\Lambda}^{\gamma}\|f\|_{\phi}\|g\|_{\phi},\quad\mbox{and}$
(29) $\mathcal{A}_{2}\leq
6\tilde{c}_{2}\kappa^{1-2v}h_{\Lambda}^{\gamma}\|\eta_{\lambda,u}(L_{\phi})f\|_{\phi}\|g\|_{\phi}\leq
6\tilde{c}_{2}\kappa^{1-2v}\lambda^{-u}h_{\Lambda}^{\gamma}\|f\|_{\phi}\|g\|_{\phi}.$

It remains to bound $\mathcal{A}_{3}$. To this end, we let
$Q^{*}_{1},Q_{2}^{*}\in\mathcal{P}_{\lfloor s/6\rfloor}^{d}$ be the
$L^{2}$-projections of $P_{f}^{*}$ and $P_{g}^{*}$ onto $\mathcal{P}_{\lfloor
s/6\rfloor}^{d}$. The the following inequalities are immediate.

(30)
$\displaystyle\|P_{f}^{*}-Q_{1}\|_{L^{2}(\mathbb{S}^{d})}\leq\tilde{c}_{3}s^{-\gamma}\|\eta_{\lambda,u}(L_{\phi})f\|_{\phi},\quad{\rm
and}$
$\displaystyle\|P_{g}^{*}-Q_{2}\|_{L^{2}(\mathbb{S}^{d})}\leq\tilde{c}_{3}s^{-\gamma}\|\eta_{\lambda,v}(L_{\phi})g\|_{\phi},$

where $\tilde{c}_{3}$ is a constant depending only on $\gamma$. We then break
up $\mathcal{A}_{3}$ into five terms and use Hölder’s inequality to write
$\mathcal{A}_{3}\leq\sum_{k=1}^{5}\mathcal{A}_{3,k},$ where

$\displaystyle\mathcal{A}_{3,1}$ $\displaystyle:=$
$\displaystyle\|P^{*}_{f}-Q_{1}\|_{L^{2}(\mathbb{S}^{d})}\|P^{*}_{g}\|_{L^{2}(\mathbb{S}^{d})},$
$\displaystyle\mathcal{A}_{3,2}$ $\displaystyle:=$
$\displaystyle\|P^{*}_{g}-Q_{2}\|_{L^{2}(\mathbb{S}^{d})}\|Q_{1}\|_{L^{2}(\mathbb{S}^{d})},$
$\displaystyle\mathcal{A}_{3,3}$ $\displaystyle:=$
$\displaystyle\left(\sum_{x_{i}\in\Lambda}w_{i,s}(P^{*}_{f}(x_{i})-Q_{1}(x_{i}))^{2}\right)^{1/2}\left(\sum_{x_{i}\in\Lambda}w_{i,s}(P^{*}_{g}(x_{i}))^{2}\right)^{1/2},$
$\displaystyle\mathcal{A}_{3,4}$ $\displaystyle:=$
$\displaystyle\left(\sum_{x_{i}\in\Lambda
w_{i,s}}w_{i,s}(P^{*}_{g}(x_{i})-Q_{2}(x_{i}))^{2}\right)^{1/2}\left(\sum_{x_{i}\in\Lambda}w_{i,s}(Q_{1}(x_{i}))^{2}\right)^{1/2},$
$\displaystyle\mathcal{A}_{3,5}$ $\displaystyle:=$
$\displaystyle\left|\int_{\mathbb{S}^{d}}Q_{1}(x)Q_{2}(x)d\omega(x)-\sum_{x_{i}\in\Lambda}w_{i,s}Q_{1}(x_{i})Q_{2}(x_{i})\right|.$

The fact that $Q_{1}Q_{2}\in\mathcal{P}_{s}^{d}$ implies
$\mathcal{A}_{3,5}=0$. Furthermore, (30) together with
$\|Q_{1}\|_{L^{2}(\mathbb{S}^{d})}\leq\|P_{f}^{*}\|_{L^{2}(\mathbb{S}^{d})}$
and
$\|Q_{2}\|_{L^{2}(\mathbb{S}^{d})}\leq\|P_{g}^{*}\|_{L^{2}(\mathbb{S}^{d})}$
yields

$\displaystyle\mathcal{A}_{3,1}\leq
6\tilde{c}_{3}s^{-\gamma}\|\eta_{\lambda,u}(L_{\phi})f\|_{\phi}\|\eta_{\lambda,v}(L_{\phi})g\|_{L^{2}(\mathbb{S}^{d})}\leq
6\tilde{c}_{3}\kappa^{1-2v}\lambda^{-u}s^{-\gamma}\|f\|_{\phi}\|g\|_{\phi},\;{\rm
and}$ $\displaystyle\mathcal{A}_{3,2}\leq
6\tilde{c}_{3}\kappa^{1-2u}\lambda^{-v}s^{-\gamma}\|f\|_{\phi}\|g\|_{\phi}.$

Using Lemma 4.8 with $s^{\prime}=s^{*}=\tilde{c}q_{\Lambda}^{-1}$, we have

$\displaystyle
A_{3,3}\leq\tilde{c}_{1}(\tilde{c}q_{\Lambda}^{-1}s^{-1})^{2d}\mathcal{A}_{3,1}\leq
6\tilde{c}_{1}(\tilde{c}q_{\Lambda}^{-1}s^{-1})^{2d}\tilde{c}_{3}\kappa^{1-2v}\lambda^{-u}s^{-\gamma}\|f\|_{\phi}\|g\|_{\phi},\;{\rm
and}$ $\displaystyle
A_{3,4}\leq\tilde{c}_{1}(\tilde{c}q_{\Lambda}^{-1}s^{-1})^{2d}\mathcal{A}_{3,2}\leq
6\tilde{c}_{1}(\tilde{c}q_{\Lambda}^{-1}s^{-1})^{2d}\tilde{c}_{3}\kappa^{1-2u}\lambda^{-v}s^{-\gamma}\|f\|_{\phi}\|g\|_{\phi}.$

Combining the above five estimates, we have

(31) $\mathcal{A}_{3}\leq
12(\tilde{c}_{1}(\tilde{c}q_{\Lambda}^{-1}s^{-1})^{2d}\tilde{+}2)\tilde{c}_{3}(\kappa+1)\lambda^{-\max\\{u,v\\}}s^{-\gamma}\|f\|_{\phi}\|g\|_{\phi}.$

We then get from (28), (29) and (31) that

$\displaystyle\left|\int_{\mathbb{S}^{d}}(\eta_{\lambda,u}(L_{\phi})f)(x)(\eta_{\lambda,v}(L_{\phi})g)(x)d\omega(x)-\sum_{x_{i}\in\Lambda}w_{i,s}\left[(\eta_{\lambda,u}(L_{\phi})f)(x_{i})(\eta_{\lambda,v}(L_{\phi})g)(x_{i})\right]\right|$
$\displaystyle\leq
12(\tilde{c}_{1}(\tilde{c}q_{\Lambda}^{-1}s^{-1})^{2d}\tilde{+}2)\tilde{c}_{3}(\kappa+1)\lambda^{-\max\\{u,v\\}}s^{-\gamma}\|f\|_{\phi}\|g\|_{\phi}$
$\displaystyle\;\;+7\tilde{c}_{2}(\kappa+1)\lambda^{-\max\\{u,v\\}}h_{\Lambda}^{\gamma}\|f\|_{\phi}\|g\|_{\phi}.$

Since $\Lambda$ is $\tau$-quasi-uniform, we have
$q_{\Lambda}\sim|D|^{-1/d}\sim h_{\Lambda}\sim s^{-1}.$ It then follows that

$\displaystyle\left|\int_{\mathbb{S}^{d}}(\eta_{\lambda,u}(L_{\phi})f)(x)(\eta_{\lambda,v}(L_{\phi})g)(x)d\omega(x)-\sum_{x_{i}\in\Lambda}w_{i,s}\left[(\eta_{\lambda,u}(L_{\phi})f)(x_{i})(\eta_{\lambda,v}(L_{\phi})g)(x_{i})\right]\right|$
$\displaystyle\leq\tilde{c}^{\prime}\lambda^{-\max\\{u,v\\}}s^{-\gamma}\|f\|_{\phi}\|g\|_{\phi},$

where $\tilde{c}^{\prime}$ is a constant depending only on $\tau,u,v,\kappa$,
$\gamma$ and $d$. This completes the proof of Proposition 4.6.

###  4.3 Operator differences and products

Here we first use Proposition 4.6 to bound $\|L_{\phi}-L_{\phi,D,W_{s}}\|$ and
then prove Theorem 4.3.

######  Lemma 4.10.

Let
$\mathcal{Q}_{\Lambda,s}:=\\{(w_{i,s},x_{i}):w_{i,s}>0\hbox{~{}and~{}}x_{i}\in\Lambda\\}$
be a positive quadrature rule on $\mathbb{S}^{d}$ with degree
$s\in\mathbb{N}$. If $\hat{\phi}_{k}\sim k^{-2\gamma}$ with $\gamma>d/2$, then
for any $\lambda\geq s^{-2\gamma}$ and $u,v\in[0,1/2]$, there holds

(32) $\displaystyle\|(L_{\phi}+\lambda
I)^{-u}(L_{\phi,D,W_{s}}-L_{\phi})(L_{\phi}+\lambda
I)^{-v}\|\leq\tilde{c}^{\prime}\lambda^{-\max\\{u,v\\}}s^{-\gamma}.$

######  Proof 4.11.

Due to the definition of operator norm, we have from the reproducing property
of $\phi$, i.e. $\langle\phi_{x},f\rangle_{\phi}=f(x)$ for any
$f\in\mathcal{N}_{\phi}$ that

$\displaystyle\|(L_{\phi}+\lambda
I)^{-u}(L_{\phi,D,W_{s}}-L_{\phi})(L_{\phi}+\lambda I)^{-v}\|$
$\displaystyle=$ $\displaystyle\sup_{\|f\|_{\phi}\leq 1}\|(L_{\phi}+\lambda
I)^{-u}(L_{\phi,D,W_{s}}-L_{\phi})(L_{\phi}+\lambda I)^{-v}f\|_{\phi}$
$\displaystyle=$ $\displaystyle\sup_{\|f\|_{\phi}\leq 1}\sup_{\|g\|_{\phi}\leq
1}\langle(L_{\phi}+\lambda I)^{-u}(L_{\phi,D,W_{s}}-L_{\phi})(L_{\phi}+\lambda
I)^{-v}f,g\rangle_{\phi}$ $\displaystyle=$
$\displaystyle\sup_{\|f\|_{\phi}\leq 1}\sup_{\|g\|_{\phi}\leq
1}\langle(L_{\phi,D,W_{s}}-L_{\phi})(L_{\phi}+\lambda
I)^{-u}f,(L_{\phi}+\lambda I)^{-v}g\rangle_{\phi}$ $\displaystyle=$
$\displaystyle\sup_{\|g\|_{\phi}\leq 1,\|f\|_{\phi}\leq
1}\left|\left\langle\int_{\mathbb{S}^{d}}(L_{\phi}+\lambda
I)^{-u}f(x^{\prime})\phi_{x^{\prime}}d\omega(x^{\prime})\right.\right.$
$\displaystyle-$
$\displaystyle\left.\left.\sum_{i=1}^{|D|}w_{i,s}(L_{\phi}+\lambda
I)^{-u}f(x_{i})\phi_{x_{i}},(L_{\phi}+\lambda
I)^{-v}g\right\rangle_{\phi}\right|$ $\displaystyle=$
$\displaystyle\sup_{\|g\|_{\phi}\leq 1,\|f\|_{\phi}\leq
1}\left|\int_{\mathbb{S}^{d}}(L_{\phi}+\lambda
I)^{-u}f(x^{\prime})\langle\phi_{x^{\prime}},(L_{\phi}+\lambda
I)^{-v}g\rangle_{\phi}d\omega(x^{\prime})\right.$ $\displaystyle-$
$\displaystyle\left.\sum_{i=1}^{|D|}w_{i,s}(L_{\phi}+\lambda
I)^{-u}f(x_{i})\langle\phi_{x_{i}},(L_{\phi}+\lambda
I)^{-v}g\rangle_{\phi}\right|$ $\displaystyle=$
$\displaystyle\sup_{\|g\|_{\phi}\leq 1,\|f\|_{\phi}\leq
1}\left|\int_{\mathbb{S}^{d}}(L_{\phi}+\lambda
I)^{-u}f(x^{\prime})(L_{\phi}+\lambda
I)^{-v}g(x^{\prime})d\omega(x^{\prime})\right.$ $\displaystyle-$
$\displaystyle\left.\sum_{i=1}^{|D|}w_{i,s}(L_{\phi}+\lambda
I)^{-u}f(x_{i})(L_{\phi}+\lambda I)^{-v}g(x_{i})\right|.$

Then, Proposition 4.6 implies

$\|(L_{\phi}+\lambda I)^{-1/2}(L_{\phi,D,W_{s}}-L_{\phi})(L_{\phi}+\lambda
I)^{-1/2}\|\leq\tilde{c}^{\prime}\lambda^{-\max\\{u,v\\}}s^{-\gamma}.$

This completes the proof of Lemma 4.10.

######  Proof 4.12 (Proof of Theorem 4.3).

For $\lambda\geq 16\tilde{c}^{\prime 2}s^{-2}$, Lemma 4.10 yields

(33) $\|(L_{\phi}+\lambda
I)^{-1/2}(L_{\phi,D,W_{s}}-L_{\phi})(L_{\phi}+\lambda I)^{-1/2}\|\leq 1/4.$

Then,

$\displaystyle(L_{\phi}+\lambda I)^{1/2}(L_{\phi,D,W_{s}}+\lambda
I)^{-1}(L_{\phi}+\lambda I)^{1/2}$ $\displaystyle=$ $\displaystyle
I+(L_{\phi}+\lambda I)^{1/2}[(L_{\phi,D,W_{s}}+\lambda
I)^{-1}-(L_{\phi}+\lambda I)^{-1}](L_{\phi}+\lambda I)^{1/2}$ $\displaystyle=$
$\displaystyle I+(L_{\phi}+\lambda
I)^{-1/2}(L_{\phi}-L_{\phi,D,W_{s}})(L_{\phi}+\lambda
I)^{-1/2}(L_{\phi}+\lambda I)^{1/2}$
$\displaystyle\times(L_{\phi,D,W_{s}}+\lambda I)^{-1}(L_{\phi}+\lambda
I)^{1/2}.$

Thus,

$\displaystyle\|(L_{\phi}+\lambda I)^{1/2}(L_{\phi,D,W_{s}}+\lambda
I)^{-1}(L_{\phi}+\lambda I)^{1/2}\|$ $\displaystyle\leq$ $\displaystyle
1+\frac{1}{4}\|(L_{\phi}+\lambda I)^{1/2}(L_{\phi,D,W_{s}}+\lambda
I)^{-1}(L_{\phi}+\lambda I)^{1/2}\|.$

This implies

$\|(L_{\phi}+\lambda I)^{1/2}(L_{\phi,D,W_{s}}+\lambda
I)^{-1}(L_{\phi}+\lambda I)^{1/2}\|\leq\frac{4}{3},$

and therefore proves (22). We then turn to proving (23). It follows from (22)
and (33) that

$\displaystyle\|(L_{\phi,D,W_{s}}+\lambda
I)^{-1/2}(L_{\phi,D,W_{s}}-L_{\phi})(L_{\phi,D,W_{s}}+\lambda I)^{-1/2}\|$
$\displaystyle\leq$ $\displaystyle\|(L_{\phi,D,W_{s}}+\lambda
I)^{-1/2}(L_{\phi}+\lambda I)^{1/2}\|^{2}$
$\displaystyle\times\|(L_{\phi}+\lambda
I)^{-1/2}(L_{\phi,D,W_{s}}-L_{\phi})(L_{\phi}+\lambda
I)^{-1/2}\|\leq\frac{1}{3}.$

Therefore,

$\displaystyle\|(L_{\phi,D,W_{s}}+\lambda I)^{1/2}(L_{\phi}+\lambda
I)^{-1}(L_{\phi,D,W_{s}}+\lambda I)^{1/2}\|$ $\displaystyle\leq$
$\displaystyle 1+\frac{1}{3}\|(L_{\phi,D,W_{s}}+\lambda
I)^{1/2}(L_{\phi}+\lambda I)^{-1}(L_{\phi,D,W_{s}}+\lambda I)^{1/2}\|,$

which implies

$\|(L_{\phi,D,W_{s}}+\lambda I)^{1/2}(L_{\phi}+\lambda
I)^{-1}(L_{\phi,D,W_{s}}+\lambda I)^{1/2}\|\leq\frac{3}{2}.$

This proves (23) and completes the proof of Theorem 4.3.

##  5 Proofs

This section provides proofs of our main results.

######  Proof 5.1 (Proof of Proposition 2.2).

In view of (3), we use the reproducing property of $\phi$ to write

$\|f_{D}\|_{\phi}^{2}=\left\langle\sum_{i=1}^{|D|}a_{i}\phi_{x_{i}},\sum_{j=1}^{|D|}a_{j}\phi_{x_{j}}\right\rangle_{\phi}=\sum_{i=1}^{|D|}\sum_{j=1}^{|D|}a_{i}a_{j}\phi(x_{i}\cdot
x_{j})={\bf a}_{D}^{T}\Phi_{D}{\bf a}_{D},$

in which ${\bf a}_{D}=\Phi_{D}^{-1}{\bf y}_{D}$. Let
$\sigma_{1},\ldots,\sigma_{|D|}$ be the eigenvalues of $\Phi_{D}$ in
descending order. The invariance of trace yields the identity:
$\sigma_{1}+\cdots+\sigma_{|D|}=|D|\phi(1).$ Thus we have that
$\sigma_{1}<|D|\phi(1),$ and therefore that $\xi\geq(|D|\phi(1))^{-1},$ where
$\xi$ denotes the smallest eigenvalue of $\Phi_{D}^{-1}.$ Hence,

$\|f_{D}\|_{\phi}^{2}=({\bf y}_{D})^{T}\Phi_{D}^{-1}{\bf
y}_{D}\geq\xi\sum^{|D|}_{i=1}y_{i}^{2}\geq(\phi(1))^{-1}\theta^{2}M^{2}.$

This completes the proof.

To prove Theorem 3.2, we adopt a standard error decomposition strategy in
learning theory [32, 19] and the sampling inequality developed in Section 4.
Let $G_{D}$ be the projection operator from $\mathcal{N}_{\phi}$ to

$\mathcal{H}_{\phi,D}=\mbox{span}\\{\phi_{x_{1}},\dots,\phi_{x_{|D|}}\\}.$

Then it is easy to get

(34) $G_{D}:=S_{D}^{T}(S_{D}S_{D}^{T})^{-1}S_{D}.$

Define

(35) $f_{D}^{\diamond}=G_{D}f^{*}$

be the noise-free version of $f_{D}$. Then the triangle inequality yields

(36)
$\|f_{D}-f^{*}\|_{\psi}\leq\|f_{D}^{\diamond}-f^{*}\|_{\psi}+\|f_{D}^{\diamond}-f_{D}\|_{\psi}.$

The above two terms are called as the approximation error and sample error,
respectively. To bound the approximation error, we need the following lemma
whose proof is standard and can be eaisly derived from [29, 18].

######  Lemma 5.2.

Let $u,v\geq 0$ and $\lambda>0$. If
$\mathcal{Q}_{\Lambda,s}:=\\{(w_{i,s},x_{i}):w_{i,s}>0\hbox{~{}and~{}}x_{i}\in\Lambda\\}$
is a positive quadrature rule on $\mathbb{S}^{d}$ with degree
$s\in\mathbb{N}$, then

(37)
$\|L_{\phi}^{v}(I-G_{D})L_{\phi}^{u}\|\leq\lambda\|L_{\phi}^{u}(L_{\phi,D,W_{s}}+\lambda
I)^{-1}L_{\phi}^{v}\|.$

The above lemma describes the difference between $G_{D}$ and the identity
mapping $I$. We remove the proof of Lemma 5.2 for the sake of brevity. We then
can bound the approximation error as follows.

######  Lemma 5.3.

If $f\in N_{\varphi}$ with $\varphi$ satisfying (9) for $\alpha\geq 1$ and
$0\leq\alpha-\beta\leq 1$ and $\hat{\phi}_{k}\sim k^{-2\gamma}$ with
$\gamma>d/2$, then for some $s\sim|D|^{-1/d}$ and any $\lambda\geq
16\tilde{c}^{\prime 2}s^{-2\gamma}$, there holds

(38)
$\|f_{D}^{\diamond}-f^{*}\|_{\psi}\leq\frac{4}{3}\lambda^{\frac{\alpha-\beta}{2}}\|f^{*}\|_{\varphi}$

where $\bar{c}_{1}$ is a constant depending only on $\tilde{c}$, $c$,
$\alpha$, $\beta$ and $\gamma$.

######  Proof 5.4.

Since $f^{*}\in\mathcal{N}_{\varphi}$, we have from (17) and Lemma 4.2 that

$\displaystyle\|f_{D}^{\diamond}-f^{*}\|_{\psi}=\|L_{\phi}^{\frac{1-\beta}{2}}(G_{D}-I)\mathcal{L}_{\phi}^{\frac{\alpha-\beta}{2}}h^{*}\|_{\phi}$
$\displaystyle\leq$
$\displaystyle\|L_{\phi}^{\frac{1-\beta}{2}}(G_{D}-I)L_{\phi}^{\frac{\alpha-1}{2}}\|\|L_{\phi}^{\frac{1-\beta}{2}}h^{*}\|_{\phi}=\|L_{\phi}^{\frac{1-\beta}{2}}(G_{D}-I)L_{\phi}^{\frac{\alpha-1}{2}}\|\|h^{*}\|_{\psi}.$

But Theorem 4.3 and Lemma 5.2 with $u=\frac{1-\beta}{2}$ and
$v=\frac{1-\beta}{2}$ imply that for any $\lambda\geq 16\tilde{c}^{\prime
2}s^{-2\gamma}$ and $\alpha\leq\beta+1\leq 2$, there holds

$\displaystyle\|L_{\phi}^{\frac{1-\beta}{2}}(G_{D}-I)L_{\phi}^{\frac{\alpha-1}{2}}\|\leq\lambda\|L_{\phi}^{\frac{1-\beta}{2}}(L_{\phi,D,W_{s}}+\lambda
I)^{-1}L_{\phi}^{\frac{\alpha-1}{2}}\|$ $\displaystyle\leq$
$\displaystyle\lambda\|(L_{\phi}+\lambda
I)^{\frac{1-\beta}{2}}(L_{\phi,D,W_{s}}+\lambda I)^{-1}(L_{\phi}+\lambda
I)^{\frac{\alpha-1}{2}}\|$ $\displaystyle\leq$
$\displaystyle\frac{4}{3}\lambda^{\frac{\alpha-\beta}{2}}$

Therefore, we obtain (38) by noting (17) and then complete the proof of Lemma
5.3.

To prove Theorem 3.2, we need the following lemma from [8].

######  Lemma 5.5.

Let $\delta\in(0,1)$. If (1) holds, $\hat{\phi}_{k}\sim k^{-2\gamma}$ with
$\gamma>d/2$ and $\\{\varepsilon_{i}\\}_{i=1}^{|D|}$ are a set of i.i.d.
random variables satisfying $E[\varepsilon_{i}]=0$ and $|\varepsilon_{i}|\leq
M$ for all $i=1,2,\dots,|D|$, then for any diagnosis matrix $W$ with diagonal
element being $\\{w_{1},\dots,w_{|D|}\\}$ and $0<w_{i}\leq c_{1}|D|^{-1}$,
with confidence $1-\delta$, there holds

(39) $\displaystyle\left\|(L_{\phi}+\lambda
I)^{-1/2}(L_{\phi,D,W}f^{*}-S_{D,W}^{T}{\bf
y}_{D,W})\right\|_{\phi}\leq\bar{c}_{1}M\lambda^{-\frac{d}{4\gamma}}|D|^{-1/2}\log\frac{3}{\delta},$

where $\bar{c}_{1}$ is a constant depending only on $d$, $\gamma$ and
$\|f^{*}\|_{\varphi}$.

In view of (36), it is sufficient to bound the approximation and sample
errors, respectively. The approximation error has been handled in Lemma 5.3.
In what follows, we work on bounding the sample error
$\|f_{D}^{\diamond}-f_{D}\|_{\psi}$.

######  Lemma 5.6.

Let $\delta\in(0,1)$, $\hat{\phi}_{k}\sim k^{-2\gamma}$ and $\gamma>d/2$. If
(1) holds with $\\{\varepsilon_{i}\\}_{i=1}^{|D|}$ a set of i.i.d. random
variables satisfying $E[\varepsilon_{i}]=0$ and $|\varepsilon_{i}|\leq M$ for
all $i=1,2,\dots,|D|$, $f\in\mathcal{N}_{\varphi}$ with (9), then for any
$\mu\geq\bar{c}_{2}|D|^{-2\gamma/d}$, with confidence $1-\delta$, there holds

(40)
$\|f_{D}^{\diamond}-f_{D}\|_{\psi}\leq\bar{c}_{3}\mu^{-\frac{\beta}{2}}(1+\mu|D|(\sigma_{|D|}(\Phi_{D}))^{-1})M\mu^{-\frac{d}{4\gamma}}|D|^{-1/2}\log\frac{3}{\delta},$

where $\bar{c}_{2},\bar{c}_{3}$ are constants depending only on
$\tilde{c}^{\prime}$, $d$ and $\gamma$.

######  Proof 5.7.

For an arbitrary $\eta>0$, it follows from

(41)
$\frac{1}{t}=\frac{1}{t+\eta}+\frac{\eta}{(t+\eta)^{2}}+\frac{\eta^{2}}{t(t+\eta)^{2}},\qquad\forall
t>0,\quad\eta>0,$

that for any $\mu>0$ there hold

(42) $\displaystyle(S_{D,W_{s}}S_{D,W_{s}}^{T})^{-1}$ $\displaystyle=$
$\displaystyle(S_{D,W_{s}}S_{D,W_{s}}^{T}+\mu
I)^{-1}+\mu(S_{D,W_{s}}S_{D,W_{s}}^{T}+\mu I)^{-2}$ $\displaystyle+$
$\displaystyle\mu^{2}(S_{D,W_{s}}S_{D,W_{s}}^{T}+\mu
I)^{-2}(S_{D,W_{s}}S_{D,W_{s}}^{T})^{-1}.$

Since for any $h:[0,\infty)\rightarrow\mathbb{R}$ and positive operator $A$,
there holds [7]

(43) $h(A^{T}A)A^{T}=A^{T}h(AA^{T})$

for well defined $h(A^{T}A)$ and $h(AA^{T})$. it follows from (20), (34) and
(35) that

$\displaystyle
f_{D}^{\diamond}-f_{D}=S_{D}^{T}(S_{D}S_{D}^{T})^{-1}(S_{D}f^{*}-{\bf y}_{D})$
$\displaystyle=$ $\displaystyle
S_{D,W_{s}}^{T}(S_{D,W_{s}}S_{D,W_{s}}^{T})^{-1}(S_{D,W_{s}}f^{*}-{\bf
y}_{D,W_{s}})$ $\displaystyle=$ $\displaystyle
S_{D,W_{s}}^{T}(S_{D,W_{s}}S_{D,W_{s}}^{T}+\mu I)^{-1}(S_{D,W_{s}}f^{*}-{\bf
y}_{D,W_{s}})$ $\displaystyle+$ $\displaystyle\mu
S_{D,W_{s}}^{T}(S_{D,W_{s}}S_{D,W_{s}}^{T}+\mu I)^{-2}(S_{D,W_{s}}f^{*}-{\bf
y}_{D,W_{s}})$ $\displaystyle+$
$\displaystyle\mu^{2}S_{D,W_{s}}^{T}(S_{D,W_{s}}S_{D,W_{s}}^{T})^{-1}(S_{D,W_{s}}S_{D,W_{s}}^{T}+\mu
I)^{-2}(S_{D,W_{s}}f^{*}-{\bf y}_{D,W_{s}})$ $\displaystyle=$
$\displaystyle(L_{\phi,D,W_{s}}+\mu
I)^{-1}(L_{\phi,D,W_{s}}f^{*}-S_{D,W_{s}}^{T}{\bf y}_{D})$ $\displaystyle+$
$\displaystyle\mu(L_{\phi,D,W_{s}}+\mu
I)^{-2}(L_{\phi,D,W_{s}}f^{*}-S_{D,W_{s}}^{T}{\bf y}_{D})$ $\displaystyle+$
$\displaystyle\mu^{2}(L_{\phi,D,W_{s}}+\mu
I)^{-3/2}S_{D,W_{s}}^{T}(S_{D,W_{s}}S_{D,W_{s}}^{T})^{-1}$
$\displaystyle(S_{D,W_{s}}S_{D,W_{s}}^{T}+\mu I)^{-1/2}(S_{D,W_{s}}f^{*}-{\bf
y}_{D,W_{s}}).$

Since for any ${\bf c}=(c_{1},\dots,c_{|D|})^{T}$, there holds

$S_{D,W}^{T}(S_{D,W}S_{D,W}^{T})^{-1}{\bf
c}=S_{D}^{T}(S_{D}S_{D}^{T})^{-1}\sqrt{n}W_{s}^{1/2}{\bf
c}=S_{D}^{T}(S_{D}S_{D}^{T})^{-2}S_{D}S_{D,W}^{T}{\bf c},$

we obtain from the Cordes inequality (24), Lemma 4.2 and the inequality [18]

(44)
$\|S_{D}^{T}(S_{D}S_{D}^{T})^{-2}S_{D}\|\leq|D|(\sigma_{|D|}(\Phi_{D}))^{-1}$

that for any $\mu\geq 16\tilde{c}^{\prime 2}s^{-2\gamma}$, there holds

$\displaystyle\|f_{D}^{\diamond}-f_{D}\|_{\psi}\leq\|L_{\phi}^{\frac{1-\beta}{2}}(L_{\phi,D,W_{s}}+\mu
I)^{-1}(L_{\phi,D,W_{s}}f^{*}-S_{D,W_{s}}^{T}{\bf y}_{D})\|_{\phi}$
$\displaystyle+$
$\displaystyle\mu\|L_{\phi}^{\frac{1-\beta}{2}}(L_{\phi,D,W_{s}}+\mu
I)^{-2}(L_{\phi,D,W_{s}}f^{*}-S_{D,W_{s}}^{T}{\bf y}_{D})\|_{\phi}$
$\displaystyle+$
$\displaystyle\mu^{2}\|L_{\phi}^{\frac{1-\beta}{2}}(L_{\phi,D,W_{s}}+\mu
I)^{-3/2}S_{D}^{T}(S_{D}S_{D}^{T})^{-2}S_{D}\|$ $\displaystyle\times$
$\displaystyle\|(L_{\phi,D,W_{s}}+\mu
I)^{-1/2}(L_{\phi,D,W_{s}}f^{*}-S_{D,W_{s}}^{T}{\bf y}_{D,W_{s}})\|_{\phi}$
$\displaystyle\leq$ $\displaystyle 4\mu^{-\frac{\beta}{2}}\left\|(L_{\phi}+\mu
I)^{-1/2}(L_{\phi,D,W_{s}}f^{*}-S_{D,W_{s}}^{T}{\bf y}_{D})\right\|_{\phi}$
$\displaystyle+$ $\displaystyle
2\mu^{1-\beta/2}|D|(\sigma_{|D|}(\Phi_{D}))^{-1}\left\|(L_{\phi}+\mu
I)^{-1/2}(L_{\phi,D,W_{s}}f^{*}-S_{D}^{T}{\bf y}_{D,W_{s}})\right\|_{\phi}.$

Therefore, Lemma 5.5 implies that for any $\mu\geq 16\tilde{c}^{\prime
2}s^{-2\gamma}$, with confidence $1-\delta$, there holds

$\|f_{D}^{\diamond}-f_{D}\|_{\psi}\leq\mu^{-\frac{\beta}{2}}(1+\mu|D|(\sigma_{|D|}(\Phi_{D}))^{-1})\bar{c}_{3}M\mu^{-\frac{d}{4\gamma}}|D|^{-1/2}\log\frac{3}{\delta}.$

This completes the proof of Lemma 5.6 by noting $s\sim|D|^{1/d}$.

Based on Lemma 5.3 and Lemma 5.6, we can derive the following lemma.

######  Lemma 5.8.

Suppose that $\phi$, $\psi$ and $\varphi$ are given as in Lemma 2.1 and that
$f_{D}$ the minimal $\phi$-norm kernel interpolant defined in (2) based on
noisy data (of the type (1)). Then there are two constants $C_{1}$ and $C_{2}$
depending only on $\alpha,\beta,\gamma,\tau$ and $d$ such that for any
$f\in\mathcal{N}_{\varphi}$, $0<\delta<1$, and $\mu\geq
C_{1}|D|^{-2\gamma/d}$, there holds

(45) $\displaystyle\|f^{*}-f_{D}\|_{\psi}\leq$ $\displaystyle
C_{2}\Bigl{\\{}|D|^{\frac{(\beta-\alpha)\gamma}{d}}\|f^{*}\|_{\varphi}$
$\displaystyle+M\mu^{-\frac{2\gamma\beta\
+d}{4\gamma}}\left[1+\mu|D|(\sigma_{|D|}(\Phi_{D}))^{-1}\right]|D|^{-1/2}\log\frac{3}{\delta}\Bigr{\\}}$

with confidence at least $1-\delta$.

######  Proof 5.9.

Plugging (40) and (38) into (36), with confidence $1-\delta$, there holds

$\|f^{*}-f_{D}\|_{\psi}\leq
C_{4}(\lambda^{\frac{\alpha-\beta}{2}}\|f^{*}\|_{\varphi}+\mu^{-\frac{\beta}{2}}(1+\mu|D|(\sigma_{|D|}(\Phi_{D}))^{-1})M\mu^{-\frac{d}{4\gamma}}|D|^{-1/2}\log\frac{3}{\delta}$

for any $\mu,\lambda\geq C_{3}|D|^{-\frac{2\gamma}{d}}$. Then (45) follows
from $\lambda=C_{3}|D|^{-\frac{2\gamma}{d}}$. This completes the proof of
Lemma 5.8.

The following lemma provided in [26, Example 2.10] presents a lower bound of
$\sigma_{|D|}(\Phi_{D})$.

######  Lemma 5.10.

If $\hat{\phi}_{k}\sim k^{-2\gamma}$ with $2\gamma>d$ an integer, then

(46) $\sigma_{|D|}(\Phi_{D})\geq C^{\prime}q_{\Lambda}^{4\gamma-d+1},$

where $C^{\prime}$ is a constant depending only on $d,\gamma$.

To prove Theorem 3.2, we also need the following lemma that can be derived by
using the same approach as [21].

######  Lemma 5.11.

For $\overline{f}_{D}$ defined by (14), there holds

$\mathbf{E}[\|\overline{f}_{D}-f^{*}\|_{\psi}^{2}]\quad\leq\sum_{j=1}^{m}\frac{|D_{j}|^{2}}{|D|^{2}}\mathbf{E}[\|f_{D_{j}}-f^{*}\|_{\psi}^{2}]+\sum_{j=1}^{m}\frac{|D_{j}|}{|D|}\left\|f^{\diamond}_{D_{j}}-f^{*}\right\|_{\psi}^{2},$

where $f^{\diamond}_{D_{j}}$ is given by (34).

We then use the above lemmas to prove Theorem 3.2.

######  Proof 5.12 (Proof of Theorem 3.2).

Due to Lemma 5.3, we have

(47)
$\|f_{D_{j}}^{\diamond}-f^{*}\|_{\psi}^{2}\leq\bar{C}_{1}|D_{j}|^{\frac{2\beta-2\alpha}{d}}\|f^{*}\|^{2}_{\varphi}$

where $\bar{C}_{1}$ is a constant depending only on $\tilde{c}$, $c$,
$\alpha$, $\beta$ and $\gamma$. Furthermore, it follows from Lemma 5.8 that
for any $\mu_{j}\geq C_{3}|D_{j}|^{-\frac{2\gamma}{d}}$, with confidence
$1-\delta$, there holds

$\displaystyle\|f^{*}-f_{D_{j}}\|_{\psi}\leq$ $\displaystyle
C_{4}(|D_{j}|^{\frac{\beta-\alpha}{d}}\|f^{*}\|_{\varphi}$
$\displaystyle+\mu_{j}^{-\frac{\beta}{2}}(1+\mu_{j}|D_{j}|(\sigma_{|D_{j}|}(\Phi_{D_{j}}))^{-1})\mu_{j}^{-\frac{d}{4\gamma}}|D_{j}|^{-\frac{1}{2}}M\log\frac{3}{\delta}.$

Therefore, a direct calculation yields

$\displaystyle\mathbf{E}[\|f^{*}-f_{D_{j}}\|_{\psi}^{2}]\leq$
$\displaystyle\bar{C}_{2}(|D_{j}|^{\frac{2\beta-2\alpha}{d}}\|f^{*}\|^{2}_{\varphi}$
$\displaystyle+\mu_{j}^{-\beta}(1+\mu_{j}|D_{j}|(\sigma_{|D_{j}|}(\Phi_{D_{j}}))^{-1})^{2}\mu_{j}^{-\frac{d}{2\gamma}}|D_{j}|^{-1}M^{2},$

where $\bar{C}_{2}$ is a constant depending only on $\tilde{c}$, $c$,
$\alpha$, $\beta$ and $\gamma$. Recalling Lemma 5.10 and setting
$\mu_{j}=C_{3}|D_{j}|^{-\frac{2\gamma}{d}}$, we have from the above inequality
that

(48)
$\mathbf{E}[\|f^{*}-f_{D_{j}}\|_{\psi}^{2}]\leq\bar{C}_{3}(|D_{j}|^{\frac{2\beta-2\alpha}{d}}\|f^{*}\|^{2}_{\varphi}+|D_{j}|^{\frac{4\gamma+2\gamma\beta+2}{d}}M^{2}),$

where $\bar{C}_{3}$ is a constant depending only on $\tilde{c}$, $c$,
$\alpha$, $\beta$ and $\gamma$. Plugging (48) and (47) into Lemma 5.11, we
then get

$\displaystyle\mathbf{E}[\|\overline{f}_{D}-f^{*}\|_{\psi}^{2}]$
$\displaystyle\leq$
$\displaystyle\bar{C}_{3}\sum_{j=1}^{m}\frac{|D_{j}|^{2}}{|D|^{2}}|D_{j}|^{\frac{4\gamma+2\gamma\beta+2}{d}}M^{2}+(\bar{C}_{2}+1)\sum_{j=1}^{m}\frac{|D_{j}|}{|D|}|D_{j}|^{\frac{2\beta-2\alpha}{d}}\|f^{*}\|^{2}_{\varphi}.$

This completes the proof of Theorem 3.2

##  6 Numerical Verifications

Four simulations are carried out in this section to verify the excellent
performance of DKI. The first one shows that DKI succeeds in circumventing the
uncertainty of kernel interpolation. The second one exhibits the role of $m$
in DKI. The third one focuses on the role of the division strategy in DKI. The
last one compares DKI with several popular spherical data fitting schemes
including the distributed filtered hyperinterpolation (DFH) [21], sketching
with $s^{*}$-designs [20], and distributed kernel ridge regression (DKRR) [8].

The training samples are generated according to 1 with $\varepsilon_{i}$
i.i.d. being drawing i.i.d. according to the Gaussian distribution
$\mathcal{N}(0,\delta^{2})$ and the target function

(49)
$f({x})=\sum\limits_{i=1}^{\kappa}\tilde{\psi}\left(\frac{\|{x}-{z}_{i}\|_{2}}{c}\right),$

where $\tilde{\psi}(u)$ is the well-known Wendland function [4]

(50) $\tilde{\psi}(u)=(1-u)_{+}^{8}(32u^{3}+25u^{2}+8u+1),$

$u_{+}=\max\\{u,0\\}$, and ${z}_{i}\in\mathbb{S}^{d}$ ($i=1,\cdots,\kappa$)
are the center points of the regions of an equal area partitioned by
Leopardi’s recursive zonal sphere partitioning procedure
[16]†††http://eqsp.sourceforge.net. The inputs $\\{{x}_{i}\\}_{i=1}^{N}$ of
training samples are generated by Womersley’s symmetric spherical $t$-designs
with $N=(t)^{2}/2+t/2+O(1)$ points [36]
‡‡‡https://web.maths.unsw.edu.au/%7Ersw/Sphere/EffSphDes/. The testing samples
are generated according to the clean model $y_{j}^{\prime}=f(x_{j}^{\prime})$
whose inputs $\\{x_{j}^{\prime}\\}_{j=1}^{N^{\prime}}$ are $N^{\prime}=10000$
equally distributed spiral points on $\mathbb{S}^{2}$ generated by
$\left[\sin\alpha_{j}\cos\beta_{j},\sin\alpha_{j}\sin\beta_{j},\cos\alpha_{j})\right]^{\top}$
with $\alpha_{j}=\arccos(1-(2j-1)/N^{\prime})$ and
$\beta_{j}=\mod(1.8\sqrt{N^{\prime}}\theta_{j},2\pi)$. We take
$\phi_{1}(x_{1},x_{2})=\tilde{\psi}(\|x_{1}-x_{2}\|_{2})$ as the positive
definite kernel. All parameters in the simulations are selected by grid
search. Each simulation is conducted 30 times, and the average results are
recorded.

(a) Uncertainty of KI (b) Overcoming uncertainty by DKI

Figure 4: Relations between the RMSE and the number of training samples for KI
and DKI under different levels of Gaussian noise

Simulation 1: In this simulation, we show that DKI can circumvent the
uncertainty of KI via showing the relations between the RMSE and data size for
different noise levels. We firstly exhibit the uncertainty of KI. $t$-designs
with varying $t\in\\{1,3,\cdots,45\\}$ are generated and
$\delta\in\\{0.001,0.01,0.1,0.3,0.5\\}$ are taken as the training samples and
noise level, respectively . The curves of the testing RMSE of kernel
interpolation changing with the number of training samples are plotted in
Figure 4 (a). It can be seen that as the number of training samples grows, the
RMSE is decreasing for small noise (i.e., $\delta\leq 0.1$), and non-
decreasing for high noises (i.e., $\delta>0.1$), showing the uncertainty of
KI.

To show the outperformance of DKI, we involve more samples. The inputs of the
training data is generated by the following two steps: First, Womersley’s
symmetric spherical $45$-designs are used to generate $1038$ points
$\\{\hat{x}_{i}\\}_{i=1}^{1038}$. Secondly, the points
$\\{\hat{x}_{i}\\}_{i=1}^{1038}$ are rotated by the rotation matrix

$A_{k}:=\left(\begin{array}[]{ccc}\cos(k\pi/10)&-\sin(k\pi/10)&0\\\
\sin(k\pi/10)&\cos(k\pi/10)&0\\\ 0&0&1\\\ \end{array}\right)$

to obtain the new points $\\{{x}_{i,k}\\}_{i=1}^{1038}$ for $k=1,\cdots,200$,
i.e., ${x}_{i,k}=A_{k}\hat{x}_{i}$, and the points
$\\{x_{i,k}\\}_{i=1}^{1038}$ are used as the inputs of training samples on the
$k$th local machine. That is, there are totally $1038k$ samples for
$k=2,4,\dots,200$. The curves of the testing RMSE of DKI changing with $k$ are
shown in Figure 4 (b). From the results, we can see that the RMSE monotonously
decreases with respect to the size of samples for all levels of Gaussian
noise, which is consistent with our assertion that more samples would yield a
higher-quality approximation. This also demonstrates that the proposed divide-
and-conquer approach can effectively handle the uncertainty of kernel
interpolation.

Figure 5: Relation between RMSE and the number of local estimators for DKI
under different levels of Gaussian noise

Simulation 2: In this simulation, we show the role of the parameter $m$ in
DKI. We generate $10014$ training samples (with 141-designs as inputs). The
number of divisions, $m$, ranges from $\\{5,10,\cdots,200\\}$. Figure 5 shows
the relation between RMSE of DKI and the number of local machines under
different levels of Gaussian noise, provided that the total number of training
samples is given. From Figure 5, we can conclude the following assertions: 1)
For training samples with higher levels of noise, the testing RMSE generally
decreases at first and then increases slowly as the number of local machines
increases. Moderate values of $m$ are more conductive to good approximation
property for DKI. The reason is that too small $m$ does not successfully
address the uncertainty issue in kernel interpolation; too large $m$ increases
the fitting error, resulting in slightly worse generalization performance. 2)
The optimal number $m$ with the lowest RMSE grows with increasing Gaussian
noise. This verifies the equation (3.2) of Theorem 3.2, in which the
approximation error is primarily concerned with the sample error for large
noise (i.e., large $M$) and can be reduced using a large $m$.

Figure 6: Comparison of the testing RMSE for $\tau$-uniform and SAJ data
divisions with increasing levels of Gaussian noise on the 3-dimensional data.

(a) RMSE (b) Training time

Figure 7: The comparison of RMSE and training time among the four methods with
increasing levels of Gaussian noise on the 3-dimensional data.

(a) Groudtruth (b) $\delta=0.001$ (c) $\delta=0.1$

(d) $\delta=0.5$

Figure 8: Visualization of the 3-dimensional training data with different
levels of Gaussian noise.

$\delta=0.001$

$\delta=0.1$

$\delta=0.5$

(a) DFH

(b) Subsampling (c) DKRR(10) (d) DKI

Figure 9: Visualization of recovered results on the 3-dimensional data with
different noise standard deviations.

Simulation 3: This simulation study of the role of the division strategy that
is used in Step 1 of DKI. The data generation is the same as in Simulation 2,
but with 10 rotation matrices, so we generate 10 sets of samples
$S_{k}=\\{(x_{i,k},y_{i,k})\\}_{i=1}^{1038}$ for $k=1,\cdots,10$ with a total
of $N=10380$ training samples. The details of data division based on
$\tau$-uniform sets are as follows: Let $m$ ($m\geq 10$) be the number of
local machines, and $r:=\mod(m,10)$. If $r=0$, that is, if $m$ can be divided
by $10$, then the samples of each set $S_{k}$ are distributed randomly and
equally to $m/10$ local machines for $k=1,\cdots,10$. If $r>0$, we randomly
choose $r$ sets from $\\{S_{k}\\}_{k=1}^{10}$; samples from each chosen set
are distributed equally to $\lceil m/10\rceil$ local machines; samples of each
set from the remaining $10-r$ sets are distributed equally to $\lfloor
m/10\rfloor$ local machines. The number of local machines for data division
based on $\tau$-uniform is chosen from the set $\\{10,12,\dots,100\\}$. The
radius value $c_{0}$ of SAJ is chosen from the set $\\{0.05,0.1,\cdots,1\\}$.
The testing RMSE of the two data division methods with optimal parameters is
shown in Figure 6, from which we know that the two data division methods are
comparable. Data division based on $\tau$-uniform sets is slightly worse than
SAJ for large noise. This may be due to the fact that the optimal number of
local machines is typically large for large noise, resulting in some
differences in the number of samples distributed to the local machines using
data division based on $\tau$-uniform sets (e.g., some local machines have
$1038/\lceil m/10\rceil$ training samples and other machines have
$1038/\lfloor m/10\rfloor$ training samples), whereas the sample number
equalization steps in SAJ make the sample number in each local machine as
close as possible. Hence, the proposed SAJ approach is a feasible scheme for
dividing the spherically scattered data into disjoint $\tau$-quasi uniform
sets.

Simulation 4: In this simulation, we show the efficiency and effectiveness of
the proposed DKI when compared with DFH, sketching with $s^{*}$-design, and
DKRR. To satisfy the training requirements of DFH, the data generation is the
same as in Simulation 3. For DFH, the training samples are equally distributed
to $10$ local machines, i.e., the samples
$S_{k}:=\\{(x_{i,k},y_{i,k})\\}_{i=1}^{1038}$ obtained by the $k$th rotation
matrix are located on the $k$th local machine, and the parameter $L$ related
to the polynomial degree is selected from the set $\\{2,4,\dots,40\\}$. For
DKRR, as the number of local machines increases, the training complexity is
reduced while the generalization performance is degraded. Hence, we make a
trade-off between the training complexity and generalization performance and
set the number of local machines to $10$, the same as DFH. The regularization
parameter $\lambda$ of DKRR is chosen from the set
$\\{\frac{1}{2^{q}}:\frac{1}{2^{q}}>10^{-10},q=0,1,2,\dots\\}$. For sub-
sampling with $s^{*}$-designs, we choose $s^{*}$ from the set
$\\{1,3,\dots,121\\}$. For DKI, we employ the data division based on
$\tau$-uniform sets for simplicity and choose the number of local machines
from the set $\\{10,12,\dots,100\\}$. Figure 7 records the testing RMSE and
corresponding training time of the involved methods with the best parameters.
The number in parentheses after ‘DKRR’ is the number of local machines. In
order to have an intuitive comparison, the 3-dimensional training data and the
recovered results of the compared methods under different levels of Gaussian
noise are visualized in Figures 8 and 9, respectively. From the results, it
can be seen that DKI is highly efficient in the training stage while
generalizing comparably to state-of-the-art methods, which implies that DKI is
an effective approach to handling the uncertainty problem of kernel
interpolation on spheres.

## References

  * [1] R. Bhatia, Matrix Analysis, vol. 169, Springer Science & Business Media, 2013.
  * [2] J. S. Brauchart and K. Hesse, Numerical integration over spheres of arbitrary dimension, Constructive Approximation, 25 (2007), pp. 41–71.
  * [3] G. Brown and F. Dai, Approximation of smooth functions on compact two-point homogeneous spaces, Journal of Functional Analysis, 220 (2005), pp. 401–423.
  * [4] A. Chernih, I. H. Sloan, and R. S. Womersley, Wendland functions with increasing smoothness converge to a gaussian, Advances in Computational Mathematics, 40 (2014), pp. 185–200.
  * [5] F. Dai, Multivariate polynomial inequalities with respect to doubling weights and $a_{\infty}$ weights, Journal of Functional Analysis, 235 (2006), pp. 137–170.
  * [6] F. Dai, On generalized hyperinterpolation on the sphere, Proceedings of the American Mathematical Society, 134 (2006), pp. 2931–2941.
  * [7] H. W. Engl, M. Hanke, and A. Neubauer, Regularization of Inverse Problems, vol. 375, Springer Science & Business Media, 1996.
  * [8] H. Feng, S.-B. Lin, and D.-X. Zhou, Radial basis function approximation with distributively stored data on spheres, arXiv:2112.02499, (2021).
  * [9] T. Hangelbroek, F. J. Narcowich, X. Sun, and J. D. Ward, Kernel approximation on manifolds ii: The $l_{\infty}$ norm of the $l_{2}$ projector, SIAM Journal on Mathematical Analysis, 43 (2011), pp. 662–684.
  * [10] T. Hangelbroek, F. J. Narcowich, and J. D. Ward, Kernel approximation on manifolds i: bounding the lebesgue constant, SIAM Journal on Mathematical Analysis, 42 (2010), pp. 1732–1760.
  * [11] K. Hesse, I. H. Sloan, and R. S. Womersley, Radial basis function approximation of noisy scattered data on the sphere, Numerische Mathematik, 137 (2017), pp. 579–605.
  * [12] K. Hesse, I. H. Sloan, and R. S. Womersley, Local rbf-based penalized least-squares approximation on the sphere with noisy scattered data, Journal of Computational and Applied Mathematics, 382 (2021), p. 113061.
  * [13] S. Hubbert, Q. T. Lê Gia, and T. M. Morton, Spherical radial basis functions, theory and applications, Springer, 2015.
  * [14] M. A. King, R. J. Bingham, P. Moore, P. L. Whitehouse, M. J. Bentley, and G. A. Milne, Lower satellite-gravimetry estimates of antarctic sea-level contribution, Nature, 491 (2012), pp. 586–589.
  * [15] Q. T. Le Gia, F. J. Narcowich, J. D. Ward, and H. Wendland, Continuous and discrete least-squares approximation by radial basis functions on spheres, Journal of Approximation Theory, 143 (2006), pp. 124–133.
  * [16] P. Leopardi, A partition of the unit sphere into regions of equal area and small diameter, Electronic Transactions on Numerical Analysis, 25 (2006), pp. 309–327.
  * [17] J. Levesley, Z. Luo, and X. Sun, Norm estimates of interpolation matrices and their inverses associated with strictly positive definite functions, Proceedings of the American Mathematical Society, (1999), pp. 2127–2134.
  * [18] S.-B. Lin, X. Chang, and X. Sun, Kernel interpolation of high dimensional scattered data, arXiv preprint arXiv:2009.01514, (2020).
  * [19] S.-B. Lin, X. Guo, and D.-X. Zhou, Distributed learning with regularized least squares, The Journal of Machine Learning Research, 18 (2017), pp. 3202–3232.
  * [20] S.-B. Lin, D. Wang, and D.-X. Zhou, Sketching with spherical designs on spheres, SIAM Journal on Scientific Computation, in press (2023).
  * [21] S.-B. Lin, Y. G. Wang, and D.-X. Zhou, Distributed filtered hyperinterpolation for noisy data on the sphere, SIAM Journal on Numerical Analysis, 59 (2021), pp. 634–659.
  * [22] J. D. McEwen and Y. Wiaux, A novel sampling theorem on the sphere, IEEE Transactions on Signal Processing, 59 (2011), pp. 5876–5887.
  * [23] H. Mhaskar, F. Narcowich, and J. Ward, Spherical marcinkiewicz-zygmund inequalities and positive quadrature, Mathematics of Computation, 70 (2001), pp. 1113–1130.
  * [24] H. N. Mhaskar, Weighted quadrature formulas and approximation by zonal function networks on the sphere, Journal of Complexity, 22 (2006), pp. 348–370.
  * [25] C. Müller, Spherical Harmonics, vol. 17, Springer, 1966.
  * [26] F. J. Narcowich, N. Sivakumar, and J. D. Ward, Stability results for scattered-data interpolation on euclidean spheres, Advances in Computational Mathematics, 8 (1998), pp. 137–163.
  * [27] F. J. Narcowich, X. Sun, J. D. Ward, and H. Wendland, Direct and inverse sobolev error estimates for scattered data interpolation via spherical basis functions, Foundations of Computational Mathematics, 7 (2007), pp. 369–390.
  * [28] F. J. Narcowich and J. D. Ward, Scattered data interpolation on spheres: error estimates and locally supported basis functions, SIAM Journal on Mathematical Analysis, 33 (2002), pp. 1393–1410.
  * [29] A. Rudi, R. Camoriano, and L. Rosasco, Less is more: Nyström computational regularization., in NIPS, 2015, pp. 1657–1665.
  * [30] R. Schaback, Error estimates and condition numbers for radial basis function interpolation, Advances in Computational Mathematics, 3 (1995), pp. 251–264.
  * [31] S. Smale and D.-X. Zhou, Shannon sampling and function reconstruction from point values, Bulletin of the American Mathematical Society, 41 (2004), pp. 279–305.
  * [32] S. Smale and D.-X. Zhou, Shannon sampling ii: Connections to learning theory, Applied and Computational Harmonic Analysis, 19 (2005), pp. 285–302.
  * [33] Y.-T. Tsai and Z.-C. Shih, All-frequency precomputed radiance transfer using spherical radial basis functions and clustered tensor approximation, ACM Transactions on Graphics (TOG), 25 (2006), pp. 967–976.
  * [34] H. Wendland, Scattered data approximation, vol. 17, Cambridge university press, 2004.
  * [35] M. A. Wieczorek and R. J. Phillips, Potential anomalies on a sphere: Applications to the thickness of the lunar crust, Journal of Geophysical Research: Planets, 103 (1998), pp. 1715–1724.
  * [36] R. S. Womersley, Efficient spherical designs with good geometric properties, in Contemporary computational mathematics-A celebration of the 80th birthday of Ian Sloan, Springer, 2018, pp. 1243–1285.
  * [37] Y. Zhang, J. Duchi, and M. Wainwright, Divide and conquer kernel ridge regression: A distributed algorithm with minimax optimal rates, The Journal of Machine Learning Research, 16 (2015), pp. 3299–3340.


Johnson, R. Khurana, T. Kolberg, G. Martinez, H. Prosper, C. Schiber, R.
Yohay, J. Zhang Florida Institute of Technology, Melbourne, USA
M.M. Baarmand, S. Butalla, T. Elkafrawy90, M. Hohlmann, R. Kumar Verma, D.
Noonan, M. Rahmani, M. Saunders, F. Yumiceva University of Illinois at Chicago
(UIC), Chicago, USA
M.R. Adams, L. Apanasevich, H. Becerril Gonzalez, R. Cavanaugh, X. Chen, S.
Dittmer, O. Evdokimov, C.E. Gerber, D.A. Hangal, D.J. Hofman, C. Mills, G. Oh,
T. Roy, M.B. Tonjes, N. Varelas, J. Viinikainen, X. Wang, Z. Wu, Z. Ye The
University of Iowa, Iowa City, USA
M. Alhusseini, K. Dilsiz91, S. Durgut, R.P. Gandrajula, M. Haytmyradov, V.
Khristenko, O.K. Köseyan, J.-P. Merlo, A. Mestvirishvili92, A. Moeller, J.
Nachtman, H. Ogul93, Y. Onel, F. Ozok94, A. Penzo, C. Snyder, E. Tiras95, J.
Wetzel Johns Hopkins University, Baltimore, USA
O. Amram, B. Blumenfeld, L. Corcodilos, M. Eminizer, A.V. Gritsan, S.
Kyriacou, P. Maksimovic, J. Roskes, M. Swartz, T.Á. Vámi The University of
Kansas, Lawrence, USA
C. Baldenegro Barrera, P. Baringer, A. Bean, A. Bylinkin, T. Isidori, S.
Khalil, J. King, G. Krintiras, A. Kropivnitskaya, C. Lindsey, N. Minafra, M.
Murray, C. Rogan, C. Royon, S. Sanders, E. Schmitz, J.D. Tapia Takaki, Q.
Wang, J. Williams, G. Wilson Kansas State University, Manhattan, USA
S. Duric, A. Ivanov, K. Kaadze, D. Kim, Y. Maravin, T. Mitchell, A. Modak
Lawrence Livermore National Laboratory, Livermore, USA
F. Rebassoo, D. Wright University of Maryland, College Park, USA
E. Adams, A. Baden, O. Baron, A. Belloni, S.C. Eno, Y. Feng, N.J. Hadley, S.
Jabeen, R.G. Kellogg, T. Koeth, A.C. Mignerey, S. Nabili, M. Seidel, A. Skuja,
S.C. Tonwar, L. Wang, K. Wong Massachusetts Institute of Technology,
Cambridge, USA
D. Abercrombie, R. Bi, S. Brandt, W. Busza, I.A. Cali, Y. Chen, M. D’Alfonso,
G. Gomez Ceballos, M. Goncharov, P. Harris, M. Hu, M. Klute, D. Kovalskyi, J.
Krupa, Y.-J. Lee, P.D. Luckey, B. Maier, A.C. Marini, C. Mironov, X. Niu, C.
Paus, D. Rankin, C. Roland, G. Roland, Z. Shi, G.S.F. Stephans, K. Tatar, D.
Velicanu, J. Wang, T.W. Wang, Z. Wang, B. Wyslouch University of Minnesota,
Minneapolis, USA
R.M. Chatterjee, A. Evans, P. Hansen, J. Hiltbrand, Sh. Jain, M. Krohn, Y.
Kubota, Z. Lesko, J. Mans, M. Revering, R. Rusack, R. Saradhy, N. Schroeder,
N. Strobbe, M.A. Wadud University of Mississippi, Oxford, USA
J.G. Acosta, S. Oliveros University of Nebraska-Lincoln, Lincoln, USA
K. Bloom, M. Bryson, S. Chauhan, D.R. Claes, C. Fangmeier, L. Finco, F. Golf,
J.R. González Fernández, C. Joo, I. Kravchenko, J.E. Siado, G.R.
Snow${}^{\textrm{\textdagger}}$, W. Tabb, F. Yan State University of New York
at Buffalo, Buffalo, USA
G. Agarwal, H. Bandyopadhyay, L. Hay, I. Iashvili, A. Kharchilava, C. McLean,
D. Nguyen, J. Pekkanen, S. Rappoccio Northeastern University, Boston, USA
G. Alverson, E. Barberis, C. Freer, Y. Haddad, A. Hortiangtham, J. Li, G.
Madigan, B. Marzocchi, D.M. Morse, V. Nguyen, T. Orimoto, A. Parker, L.
Skinnari, A. Tishelman-Charny, T. Wamorkar, B. Wang, A. Wisecarver, D. Wood
Northwestern University, Evanston, USA
S. Bhattacharya, J. Bueghly, Z. Chen, A. Gilbert, T. Gunter, K.A. Hahn, N.
Odell, M.H. Schmitt, K. Sung, M. Velasco University of Notre Dame, Notre Dame,
USA
R. Bucci, N. Dev, R. Goldouzian, M. Hildreth, K. Hurtado Anampa, C. Jessop, K.
Lannon, N. Loukas, N. Marinelli, I. Mcalister, F. Meng, K. Mohrman, Y.
Musienko51, R. Ruchti, P. Siddireddy, M. Wayne, A. Wightman, M. Wolf, L.
Zygala The Ohio State University, Columbus, USA
J. Alimena, B. Bylsma, B. Cardwell, L.S. Durkin, B. Francis, C. Hill, A.
Lefeld, B.L. Winer, B.R. Yates Princeton University, Princeton, USA
F.M. Addesa, B. Bonham, P. Das, G. Dezoort, P. Elmer, A. Frankenthal, B.
Greenberg, N. Haubrich, S. Higginbotham, A. Kalogeropoulos, G. Kopp, S. Kwan,
D. Lange, M.T. Lucchini, D. Marlow, K. Mei, I. Ojalvo, J. Olsen, C. Palmer, D.
Stickland, C. Tully University of Puerto Rico, Mayaguez, USA
S. Malik, S. Norberg Purdue University, West Lafayette, USA
A.S. Bakshi, V.E. Barnes, R. Chawla, S. Das, L. Gutay, M. Jones, A.W. Jung, S.
Karmarkar, M. Liu, G. Negro, N. Neumeister, C.C. Peng, S. Piperov, A. Purohit,
J.F. Schulte, M. Stojanovic18, J. Thieman, F. Wang, R. Xiao, W. Xie Purdue
University Northwest, Hammond, USA
J. Dolen, N. Parashar Rice University, Houston, USA
A. Baty, S. Dildick, K.M. Ecklund, S. Freed, F.J.M. Geurts, A. Kumar, W. Li,
B.P. Padley, R. Redjimi, J. Roberts${}^{\textrm{\textdagger}}$, W. Shi, A.G.
Stahl Leiton University of Rochester, Rochester, USA
A. Bodek, P. de Barbaro, R. Demina, J.L. Dulemba, C. Fallon, T. Ferbel, M.
Galanti, A. Garcia-Bellido, O. Hindrichs, A. Khukhunaishvili, E. Ranken, R.
Taus Rutgers, The State University of New Jersey, Piscataway, USA
B. Chiarito, J.P. Chou, A. Gandrakota, Y. Gershtein, E. Halkiadakis, A. Hart,
M. Heindl, E. Hughes, S. Kaplan, O. Karacheban26, I. Laflotte, A. Lath, R.
Montalvo, K. Nash, M. Osherson, S. Salur, S. Schnetzer, S. Somalwar, R. Stone,
S.A. Thayil, S. Thomas, H. Wang University of Tennessee, Knoxville, USA
H. Acharya, A.G. Delannoy, S. Spanier Texas A&M University, College Station,
USA
O. Bouhali96, M. Dalchenko, A. Delgado, R. Eusebi, J. Gilmore, T. Huang, T.
Kamon97, H. Kim, S. Luo, S. Malhotra, R. Mueller, D. Overton, D. Rathjens, A.
Safonov Texas Tech University, Lubbock, USA
N. Akchurin, J. Damgov, V. Hegde, S. Kunori, K. Lamichhane, S.W. Lee, T.
Mengke, S. Muthumuni, T. Peltola, S. Undleeb, I. Volobouev, Z. Wang, A.
Whitbeck Vanderbilt University, Nashville, USA
E. Appelt, S. Greene, A. Gurrola, W. Johns, C. Maguire, A. Melo, H. Ni, K.
Padeken, F. Romeo, P. Sheldon, S. Tuo, J. Velkovska University of Virginia,
Charlottesville, USA
M.W. Arenton, B. Cox, G. Cummings, J. Hakala, R. Hirosky, M. Joyce, A.
Ledovskoy, A. Li, C. Neu, B. Tannenwald, E. Wolfe Wayne State University,
Detroit, USA
P.E. Karchin, N. Poudyal, P. Thapa University of Wisconsin - Madison, Madison,
WI, USA
K. Black, T. Bose, J. Buchanan, C. Caillol, S. Dasu, I. De Bruyn, P.
Everaerts, C. Galloni, H. He, M. Herndon, A. Hervé, U. Hussain, A. Lanaro, A.
Loeliger, R. Loveless, J. Madhusudanan Sreekala, A. Mallampalli, A. Mohammadi,
D. Pinna, A. Savin, V. Shang, V. Sharma, W.H. Smith, D. Teague, S. Trembath-
reichert, W. Vetens †: Deceased
1: Also at Vienna University of Technology, Vienna, Austria
2: Also at Institute of Basic and Applied Sciences, Faculty of Engineering,
Arab Academy for Science, Technology and Maritime Transport, Alexandria,
Egypt, Alexandria, Egypt
3: Also at Université Libre de Bruxelles, Bruxelles, Belgium
4: Also at IRFU, CEA, Université Paris-Saclay, Gif-sur-Yvette, France
5: Also at Universidade Estadual de Campinas, Campinas, Brazil
6: Also at Federal University of Rio Grande do Sul, Porto Alegre, Brazil
7: Also at UFMS, Nova Andradina, Brazil
8: Also at Nanjing Normal University Department of Physics, Nanjing, China
9: Now at The University of Iowa, Iowa City, USA
10: Also at University of Chinese Academy of Sciences, Beijing, China
11: Also at Institute for Theoretical and Experimental Physics named by A.I.
Alikhanov of NRC ‘Kurchatov Institute’, Moscow, Russia
12: Also at Joint Institute for Nuclear Research, Dubna, Russia
13: Also at Cairo University, Cairo, Egypt
14: Also at Helwan University, Cairo, Egypt
15: Now at Zewail City of Science and Technology, Zewail, Egypt
16: Also at Suez University, Suez, Egypt
17: Now at British University in Egypt, Cairo, Egypt
18: Also at Purdue University, West Lafayette, USA
19: Also at Université de Haute Alsace, Mulhouse, France
20: Also at Ilia State University, Tbilisi, Georgia
21: Also at Erzincan Binali Yildirim University, Erzincan, Turkey
22: Also at CERN, European Organization for Nuclear Research, Geneva,
Switzerland
23: Also at RWTH Aachen University, III. Physikalisches Institut A, Aachen,
Germany
24: Also at University of Hamburg, Hamburg, Germany
25: Also at Department of Physics, Isfahan University of Technology, Isfahan,
Iran, Isfahan, Iran
26: Also at Brandenburg University of Technology, Cottbus, Germany
27: Also at Skobeltsyn Institute of Nuclear Physics, Lomonosov Moscow State
University, Moscow, Russia
28: Also at Physics Department, Faculty of Science, Assiut University, Assiut,
Egypt
29: Also at Eszterhazy Karoly University, Karoly Robert Campus, Gyongyos,
Hungary
30: Also at Institute of Physics, University of Debrecen, Debrecen, Hungary,
Debrecen, Hungary
31: Also at Institute of Nuclear Research ATOMKI, Debrecen, Hungary
32: Also at MTA-ELTE Lendület CMS Particle and Nuclear Physics Group, Eötvös
Loránd University, Budapest, Hungary, Budapest, Hungary
33: Also at Wigner Research Centre for Physics, Budapest, Hungary
34: Also at IIT Bhubaneswar, Bhubaneswar, India, Bhubaneswar, India
35: Also at Institute of Physics, Bhubaneswar, India
36: Also at G.H.G. Khalsa College, Punjab, India
37: Also at Shoolini University, Solan, India
38: Also at University of Hyderabad, Hyderabad, India
39: Also at University of Visva-Bharati, Santiniketan, India
40: Also at Indian Institute of Technology (IIT), Mumbai, India
41: Also at Deutsches Elektronen-Synchrotron, Hamburg, Germany
42: Also at Sharif University of Technology, Tehran, Iran
43: Also at Department of Physics, University of Science and Technology of
Mazandaran, Behshahr, Iran
44: Now at INFN Sezione di Bari a, Università di Bari b, Politecnico di Bari
c, Bari, Italy
45: Also at Italian National Agency for New Technologies, Energy and
Sustainable Economic Development, Bologna, Italy
46: Also at Centro Siciliano di Fisica Nucleare e di Struttura Della Materia,
Catania, Italy
47: Also at Università di Napoli ’Federico II’, NAPOLI, Italy
48: Also at Riga Technical University, Riga, Latvia, Riga, Latvia
49: Also at Consejo Nacional de Ciencia y Tecnología, Mexico City, Mexico
50: Also at Warsaw University of Technology, Institute of Electronic Systems,
Warsaw, Poland
51: Also at Institute for Nuclear Research, Moscow, Russia
52: Now at National Research Nuclear University ’Moscow Engineering Physics
Institute’ (MEPhI), Moscow, Russia
53: Also at St. Petersburg State Polytechnical University, St. Petersburg,
Russia
54: Also at University of Florida, Gainesville, USA
55: Also at Imperial College, London, United Kingdom
56: Also at P.N. Lebedev Physical Institute, Moscow, Russia
57: Also at California Institute of Technology, Pasadena, USA
58: Also at Budker Institute of Nuclear Physics, Novosibirsk, Russia
59: Also at Faculty of Physics, University of Belgrade, Belgrade, Serbia
60: Also at Trincomalee Campus, Eastern University, Sri Lanka, Nilaveli, Sri
Lanka
61: Also at INFN Sezione di Pavia a, Università di Pavia b, Pavia, Italy,
Pavia, Italy
62: Also at National and Kapodistrian University of Athens, Athens, Greece
63: Also at Universität Zürich, Zurich, Switzerland
64: Also at Ecole Polytechnique Fédérale Lausanne, Lausanne, Switzerland
65: Also at Stefan Meyer Institute for Subatomic Physics, Vienna, Austria,
Vienna, Austria
66: Also at Laboratoire d’Annecy-le-Vieux de Physique des Particules,
IN2P3-CNRS, Annecy-le-Vieux, France
67: Also at Şırnak University, Sirnak, Turkey
68: Also at Department of Physics, Tsinghua University, Beijing, China,
Beijing, China
69: Also at Near East University, Research Center of Experimental Health
Science, Nicosia, Turkey
70: Also at Beykent University, Istanbul, Turkey, Istanbul, Turkey
71: Also at Istanbul Aydin University, Application and Research Center for
Advanced Studies (App. & Res. Cent. for Advanced Studies), Istanbul, Turkey
72: Also at Mersin University, Mersin, Turkey
73: Also at Piri Reis University, Istanbul, Turkey
74: Also at Adiyaman University, Adiyaman, Turkey
75: Also at Ozyegin University, Istanbul, Turkey
76: Also at Izmir Institute of Technology, Izmir, Turkey
77: Also at Necmettin Erbakan University, Konya, Turkey
78: Also at Bozok Universitetesi Rektörlügü, Yozgat, Turkey, Yozgat, Turkey
79: Also at Marmara University, Istanbul, Turkey
80: Also at Milli Savunma University, Istanbul, Turkey
81: Also at Kafkas University, Kars, Turkey
82: Also at Istanbul Bilgi University, Istanbul, Turkey
83: Also at Hacettepe University, Ankara, Turkey
84: Also at Vrije Universiteit Brussel, Brussel, Belgium
85: Also at School of Physics and Astronomy, University of Southampton,
Southampton, United Kingdom
86: Also at IPPP Durham University, Durham, United Kingdom
87: Also at Monash University, Faculty of Science, Clayton, Australia
88: Also at Bethel University, St. Paul, Minneapolis, USA, St. Paul, USA
89: Also at Karamanoğlu Mehmetbey University, Karaman, Turkey
90: Also at Ain Shams University, Cairo, Egypt
91: Also at Bingol University, Bingol, Turkey
92: Also at Georgian Technical University, Tbilisi, Georgia
93: Also at Sinop University, Sinop, Turkey
94: Also at Mimar Sinan University, Istanbul, Istanbul, Turkey
95: Also at Erciyes University, KAYSERI, Turkey
96: Also at Texas A&M University at Qatar, Doha, Qatar
97: Also at Kyungpook National University, Daegu, Korea, Daegu, Korea