Noiseless Gaussian RKHS interpolation error under uniform sampling

By [A1], [F1], and [F2], the Gaussian kernel has the real RKHS used in the Statement, with evaluation property [F3]. Let $X_n=\{x_1,\dots ,x_n\}$ and $V_n=\mathrm{span}\{k_{\sigma }(\cdot ,x_i):1\le i\le n\}$. For any interpolant $h$, put $g=h-h^{\ast }$. Then $g(x_i)=0$, so [F3] gives $⟨g,k_{\sigma }(\cdot ,x_i)⟩=0$ for each $i$ and hence $g\perp V_n$. By [F6] the projection ${\mathrm{\Pi }}_{V_n}$ exists; therefore $g(x)=⟨g,k_{\sigma }(\cdot ,x)⟩=⟨g,k_{\sigma }(\cdot ,x)-{\mathrm{\Pi }}_{V_n}{k}_{\sigma }(\cdot ,x)⟩\mathrm{.}$ The inner-product Cauchy--Schwarz inequality follows by expanding $\mathrm{\parallel }u-tv{\mathrm{\parallel }}^2\ge 0$ and minimizing over real $t$ (with the zero-vector case immediate). Thus $\mathrm{\mid }g(x)\mathrm{\mid }\le \mathrm{\parallel }g{\mathrm{\parallel }}_{{\mathcal{H}}_{\sigma }}{P}_{X_n}(x)$.

The triangle inequality gives $\mathrm{\parallel }g{\mathrm{\parallel }}_{{\mathcal{H}}_{\sigma }}\le \mathrm{\parallel }h{\mathrm{\parallel }}_{{\mathcal{H}}_{\sigma }}+\mathrm{\parallel }{h}^{\ast }{\mathrm{\parallel }}_{{\mathcal{H}}_{\sigma }}$. Taking the supremum in step 1.1 yields ${\sup }_{x\in \mathrm{\Omega }}\mathrm{\mid }h(x)-h^{\ast }(x)\mathrm{\mid }\le (\mathrm{\parallel }h{\mathrm{\parallel }}_{{\mathcal{H}}_{\sigma }}+\mathrm{\parallel }{h}^{\ast }{\mathrm{\parallel }}_{{\mathcal{H}}_{\sigma }}){\sup }_{x\in \mathrm{\Omega }}{P}_{X_n}(x)\mathrm{.}$

Write $\mathrm{\Omega }=v+Q[0,L{]}^d$ using its side length $L>0$ and an orthogonal matrix $Q$, and put $u_i=Q^{\mathsf{T}}(x_i-v)$. The affine map $F(u)=v+Qu$ bijects the product cube $C_0=[0,L{]}^d$ onto $\mathrm{\Omega }$. For every Borel $E\subseteq C_0$, [F7] gives $\mathbb{P}(u_i\in E)={\lambda }_d(F(E))\mathrm{/}{\lambda }_d(\mathrm{\Omega })=\mathrm{\mid }\det Q\mathrm{\mid }{\lambda }_d(E)\mathrm{/}(\mathrm{\mid }\det Q\mathrm{\mid }{\lambda }_d(C_0))={\lambda }_d(E)\mathrm{/}{\lambda }_d(C_0)$. The transformed samples remain independent: for finitely many Borel sets $E_i\subseteq C_0$, their joint event is ${\bigcap }_i\{x_i\in F(E_i)\}$, and independence of the $x_i$ makes its probability the product of the individual probabilities. These events are measurable since $F$ is a homeomorphism. Also $\mathrm{\parallel }F(u)-F(w){\mathrm{\parallel }}_2=\mathrm{\parallel }u-w{\mathrm{\parallel }}_2$, so the fill distance of $\{u_1,\dots ,u_n\}$ in $C_0$ equals $h_{X_n}$ in $\mathrm{\Omega }$. By [F5], on an event of probability at least $1-1\mathrm{/}n$, the fill distance $h_{X_n}$ is at most ${\bar{h}}_n=C_{d}L(\log n\mathrm{/}n{)}^{1\mathrm{/}d}$. For all sufficiently large $n$, ${\bar{h}}_n<\min (h_0,e^{-1})$; the function $u\mapsto \mathrm{\mid }\log u\mathrm{\mid }\mathrm{/}u$ is decreasing on $(0,e^{-1}]$, so [F4] applies and gives ${\sup }_x{P}_{X_n}(x)\le C\exp \text{\hspace{0.17em}⁣}(-c\frac{\mathrm{\mid }\log h_{X_n}\mathrm{\mid }}{h_{X_n}})\le C\exp \text{\hspace{0.17em}⁣}(-\frac{c}{{\bar{h}}_n})=C\exp \text{\hspace{0.17em}⁣}(-\frac{c}{C_{d}L}{\left(\frac{n}{\log n}\right)}^{1\mathrm{/}d})\mathrm{.}$ Using this bound in step 2.1 proves the displayed estimate with $A=C$ and $B=c\mathrm{/}(C_{d}L)$, uniformly for every interpolant on that event.