Radial basis and kernel interpolation — Examples

For every row index $i$, the equal sites give $K_{i1}=\varphi (\mathrm{\mid }{x}_i-x_1\mathrm{\mid })=\varphi (\mathrm{\mid }{x}_i-x_2\mathrm{\mid })=K_{i2}$. Thus the first two columns, and by symmetry the first two rows, coincide.

The nonzero vector $e_1-e_2$ is therefore in the nullspace of the Gram matrix, so the matrix is singular. This example violates the distinct-site hypothesis in [F1] and is not a counterexample to the interpolation theorem.

The cube is bounded and Lipschitz. At a boundary point $p$, let $I$ be the nonempty set of active coordinates ($p_j=0$ or $1$), with inward signs ${\sigma }_j=1$ at $0$ and $-1$ at $1$. Put $u_j={\sigma }_j\mathrm{/}\sqrt{\mathrm{\mid }I\mathrm{\mid }}$ for $j\in I$ and $u_j=0$ otherwise. In the orthogonal coordinates $x=p+y+tu$ with $y\perp u$, a sufficiently small neighborhood has no constraints from inactive coordinates, and the active inequalities reduce to $t>{\max }_{j\in I}(-\sqrt{\mathrm{\mid }I\mathrm{\mid }}{\sigma }_j{y}_j)\mathrm{.}$ This is the epigraph of a finite maximum of linear functions, hence a local Lipschitz graph with the cube on one side. The cube also satisfies the uniform cone condition. For $x\in [0,1{]}^d$, choose signs ${\sigma }_j=1$ if $x_j\le 1\mathrm{/}2$ and $-1$ otherwise, and put $u=({\sigma }_1,\dots ,{\sigma }_d)\mathrm{/}\sqrt{d}$. If $u=e_1$ take $Q_x=I$; otherwise put $v=(e_1-u)\mathrm{/}\mathrm{\mid }{e}_1-u\mathrm{\mid }$ and $Q_x=I-2v{v}^{\mathsf{T}}$, which is orthogonal and sends $e_1$ to $u$. Choose $0<\theta <\pi \mathrm{/}2$ with $\cos \theta \mathrm{/}\sqrt{d}-\sin \theta >0$, and set $r_0=1\mathrm{/}2$. For any cone vector $z$, $z_1>\mathrm{\mid }z\mathrm{\mid }\cos \theta$ and $\mathrm{\mid }z-z_1{e}_1\mathrm{\mid }<\mathrm{\mid }z\mathrm{\mid }\sin \theta$. Hence ${\sigma }_j(Q_{x}z{)}_j\ge z_1\mathrm{/}\sqrt{d}-\mathrm{\mid }z-z_1{e}_1\mathrm{\mid }>\mathrm{\mid }z\mathrm{\mid }(\cos \theta \mathrm{/}\sqrt{d}-\sin \theta )>0$ for each coordinate. Each coordinate moves toward the cube's interior by less than $r_0$, so $x+Q_{x}z\in (0,1{)}^d$.

Distinct midpoint sites have fill distance at most $\sqrt{d}\mathrm{/}(2m)$. Since $m$ is odd, $x_0\in X_m$. By continuity in [F2], choose ${ϵ}_m>0$ so that $\mathrm{\mid }1-k(\delta e_1)\mathrm{\mid }<1\mathrm{/}m$ whenever $0<\delta <{ϵ}_m$, then choose $0<{\delta }_m<\min \{{ϵ}_m,1\mathrm{/}(4m^2)\}$. Strict positive definiteness for $x_0$ and $x_0+{\delta }_m{e}_1$ makes $1-k({\delta }_m{e}_1)>0$, so $0<1-k({\delta }_m{e}_1)<1\mathrm{/}m$. Put $Z_m=X_m\cup \{x_0+{\delta }_m{e}_1\}$. The new site is inside the cube because ${\delta }_m<1\mathrm{/}(4m^2)<1\mathrm{/}2$. Every other grid site is at distance at least $1\mathrm{/}m$ from $x_0$, while ${\delta }_m<1\mathrm{/}(4m^2)<1\mathrm{/}(2m)$, so the new site is distinct from all grid sites. At the boundary corner $0$, the nearest grid point is $(1\mathrm{/}(2m),\dots ,1\mathrm{/}(2m))$, at distance $\sqrt{d}\mathrm{/}(2m)$; the new site has squared distance $d\mathrm{/}4+{\delta }_m+{\delta }_m^2>d\mathrm{/}(4m^2)$, so ${\min }_{z\in Z_m}\mathrm{\mid }z\mathrm{\mid }=\sqrt{d}\mathrm{/}(2m)$. For $D_m(x)={\min }_{z\in Z_m}\mathrm{\mid }x-z\mathrm{\mid }$, the triangle inequality gives $\mathrm{\mid }{D}_m(x)-D_m(y)\mathrm{\mid }\le \mathrm{\mid }x-y\mathrm{\mid }$. Since $x_n=(1\mathrm{/}n,\dots ,1\mathrm{/}n)\in \mathrm{\Omega }$ for $n\ge 2$ and $x_n\to 0$, $D_m(x_n)\to D_m(0)$; the fill-distance supremum therefore satisfies $h_{Z_m}\ge \sqrt{d}\mathrm{/}(2m)\ge 1\mathrm{/}(2m)$. Adding a site cannot increase fill distance, so also $h_{Z_m}\le \sqrt{d}\mathrm{/}(2m)\to 0$. The separation radius satisfies $0<q_{Z_m}\le {\delta }_m\mathrm{/}2<1\mathrm{/}(8m^2)$; consequently ${\rho }_{Z_m}=h_{Z_m}\mathrm{/}{q}_{Z_m}>4m\to \mathrm{\infty }$.

Let $u$ be the unit vector with entries $1\mathrm{/}\sqrt{2}$ and $-1\mathrm{/}\sqrt{2}$ at the new site and $x_0$, and zero elsewhere. The corresponding Rayleigh quotient is $u^{\mathsf{T}}{K}_{Z_m}u=\frac{1}{2}(1+1-2k({\delta }_m{e}_1))=1-k({\delta }_m{e}_1)\mathrm{.}$ Hence [F3] gives $0<{\lambda }_{\min }(K_{Z_m})\le 1-k({\delta }_m{e}_1)<1\mathrm{/}m$. By [F3] choose an orthonormal eigenbasis $Q$ and write $K_{Z_m}=Q\mathrm{\Lambda }{Q}^{\mathsf{T}}$. Since every diagonal entry is $1$, $\mathrm{tr}{K}_{Z_m}=\mathrm{\mid }{Z}_m\mathrm{\mid }={\sum }_{i,j}{q}_{ij}^2{\lambda }_j={\sum }_j{\lambda }_j,$ so ${\lambda }_{\max }(K_{Z_m})$ is at least the average eigenvalue, namely $1$. For a unit vector $v=Qc$, orthogonality gives $\mathrm{\parallel }{K}_{Z_m}v{\mathrm{\parallel }}_2^2={\sum }_j{\lambda }_j^2{c}_j^2\le {\lambda }_{\max }(K_{Z_m}{)}^2$, with equality at a top eigenvector; the same calculation for $K_{Z_m}^{-1}$ gives induced 2-norm $1\mathrm{/}{\lambda }_{\min }(K_{Z_m})$. Thus [F4] gives ${\kappa }_2(K_{Z_m})={\lambda }_{\max }(K_{Z_m})\mathrm{/}{\lambda }_{\min }(K_{Z_m})>m$. Together with step 1.2, this gives $h_{Z_m}\to 0$, ${\rho }_{Z_m}\to \mathrm{\infty }$, and condition number tending to infinity.

The cube is bounded and Lipschitz. At a boundary point $p$, let $I$ be the nonempty set of active coordinates ($p_j=0$ or $1$), with inward signs ${\sigma }_j=1$ at $0$ and $-1$ at $1$. Put $u_j={\sigma }_j\mathrm{/}\sqrt{\mathrm{\mid }I\mathrm{\mid }}$ for $j\in I$ and $u_j=0$ otherwise. In the orthogonal coordinates $x=p+y+tu$ with $y\perp u$, a sufficiently small neighborhood has no constraints from inactive coordinates, and the active inequalities reduce to $t>{\max }_{j\in I}(-\sqrt{\mathrm{\mid }I\mathrm{\mid }}{\sigma }_j{y}_j)\mathrm{.}$ This is the epigraph of a finite maximum of linear functions, hence a local Lipschitz graph with the cube on one side. The cube also satisfies the uniform cone condition: for $x\in [0,1{]}^d$, let ${\sigma }_j=1$ if $x_j\le 1\mathrm{/}2$ and ${\sigma }_j=-1$ otherwise, and put $u=({\sigma }_1,\dots ,{\sigma }_d)\mathrm{/}\sqrt{d}$. If $u=e_1$ let $Q_x=I$; otherwise put $v=(e_1-u)\mathrm{/}\mathrm{\mid }{e}_1-u\mathrm{\mid }$ and $Q_x=I-2v{v}^{\mathsf{T}}$, which is orthogonal and sends $e_1$ to $u$. Choose $0<\theta <\pi \mathrm{/}2$ with $\cos \theta \mathrm{/}\sqrt{d}-\sin \theta >0$, and set $r_0=1\mathrm{/}2$. For any cone vector $z$, $z_1>\mathrm{\mid }z\mathrm{\mid }\cos \theta$ and $\mathrm{\mid }z-z_1{e}_1\mathrm{\mid }<\mathrm{\mid }z\mathrm{\mid }\sin \theta$. Hence for every coordinate, ${\sigma }_j(Q_{x}z{)}_j\ge z_1\mathrm{/}\sqrt{d}-\mathrm{\mid }z-z_1{e}_1\mathrm{\mid }>\mathrm{\mid }z\mathrm{\mid }(\cos \theta \mathrm{/}\sqrt{d}-\sin \theta )>0$. Each coordinate moves toward the cube's interior by less than $r_0$, so $x+Q_{x}z\in (0,1{)}^d$.

The sites in $X_m$ are distinct. Each $x\in (0,1{)}^d$ is at coordinatewise distance at most $1\mathrm{/}(2m)$ from a midpoint in each grid interval, so $h_{X_m}\le \sqrt{d}\mathrm{/}(2m)\to 0$. By [F3], every partial derivative of $f$ is a finite sum of polynomial multiples of $e^{-\pi \mathrm{\mid }x{\mathrm{\mid }}^2}$; [F4] makes every polynomially weighted derivative bounded, so $f$ is Schwartz. Then [F2] gives $f{\mathrm{\mid }}_{\mathrm{\Omega }}\in H^s(\mathrm{\Omega })$ for $s=\nu +d\mathrm{/}2$.

For all sufficiently large $m$, step 2.1 gives $h_{X_m}\le h_0$ from [F5]. The Matérn interpolation theorem therefore yields $\mathrm{\parallel }f-s_{X_m}f{\mathrm{\parallel }}_{L^{\mathrm{\infty }}(\mathrm{\Omega })}\le C{h}_{X_m}^{\nu }\mathrm{\parallel }f{\mathrm{\parallel }}_{H^s(\mathrm{\Omega })}\le C{\left(\frac{\sqrt{d}}{2m}\right)}^{\nu }\mathrm{\parallel }f{\mathrm{\parallel }}_{H^s(\mathrm{\Omega })},{\sup }_{x\in \mathrm{\Omega }}{P}_{X_m}(x)\le C{\left(\frac{\sqrt{d}}{2m}\right)}^{\nu }\mathrm{.}$ The graph samples are the scattered surface data, and the bound uses fill distance alone; no mesh-ratio condition is needed.