β’2|±|

=: p±,β (x) x .

2

The polynomial p±,β is indeed a homogenous polynomial of degree |±|, because the deriva-

tive of a homogenous polynomial of degree is a homogenous polynomial of degree ’ 1,

and the product of two homogenous polynomials of degree and k is a homogenous poly-

nomial of degree + k.

The following theorem is an immediate consequence.

⊆ Rd is bounded and satis¬es an interior cone con-

Theorem 11.16 Suppose that

β

dition. Let (x) = (’1) β/2 x 2 , β > 0, β ∈ 2N. Denote the interpolant of a function

f ∈ N ( ) based on this basis function and the set of centers X = {x1 , . . . , x N } ⊆ by

s f,X . Then there exist constants h 0 , C > 0 such that

β/2’|±|

|D ± f (x) ’ D ± s f,X (x)| ¤ Ch X, | f |N ( ), x∈ ,

for all ± with |±| ¤ ( β ’ 1)/2 provided that h X, ¤ h 0 .

The next family of functions at which we want to look are the compactly supported functions

d,k = φd,k ( · 2 ) constructed in Chapter 9.

Theorem 11.17 Let d,k = φd,k ( · 2 ) be the functions from Theorem 9.13. Suppose that

⊆ Rd is bounded and satis¬es an interior cone condition. Denote the radial basis function

interpolant of f ∈ N d,k ( ) based on d,k and X = {x1 , . . . , x N } ⊆ by s f,X . Then there

exist constants C, h 0 > 0 such that

|D ± f (x) ’ D ± s f,X (x)| ¤ Ch X,

k+1/2’|±|

f N()

for every ± ∈ Nd with |±| ¤ k and every x ∈ , provided that h X, ¤ h 0 .

0

11.3 Estimates for popular basis functions 185

Proof From the estimates on the Fourier transform of d,k we already know that d,k ∈

C 2k (Rd ). Moreover, we know that φd,k ∈ C 2k (R) by construction. Hence, since φd,k is also

a polynomial on 0 ¤ r ¤ 1 of degree := d/2 + 3k + 1, this means that exactly the ¬rst

k odd coef¬cients of this polynomial must vanish. Thus we have

φd,k (r ) = a0 + a2r 2 + · · · + a2k r 2k + a2k+1r 2k+1 + · · · + a r

for 0 ¤ r ¤ 1 with certain coef¬cients a j . Taking p(k) = a0 + a2 x 2 + · · · + a2k x 2k

2 2

shows |D β ( d,k ’ p)(x)| ¤ Cβ x 2

2k+1’|β|

for |β| ¤ 2k by Lemma 11.15. Thus Theo-

rem 11.9 gives the stated result.

Once again, we point out that convergence for the compactly supported basis functions is

gained by keeping the support radius ¬xed while the ¬ll distance tends to zero. This means

in particular that the advantage of the compact support gets more and more lost. In the

end, the compactly supported basis functions act like globally supported ones. In contrast

with this nonstationary setting, one could be tempted to use a stationary approach, i.e. to

choose the support radius proportional to the ¬ll distance. In this setting the bandwidth of

the interpolation matrices is approximately constant, at least for quasi-uniform data sets.

The price for this stationary setting is that we cannot conclude convergence from estimates

on the power function. To be more precise, suppose we scale a basis function with support

in the unit ball B(0, 1) by δ = (·/δ). Then it is easy to see that the power function scales

as P δ ,X (x) = P ,X/δ (x/δ) with X/δ = {x1 /δ, . . . , x N /δ}. Since obviously we also have

h X/δ, = h X,δ /δ we can see that

k+1/2

h X,δ

(x) ¤ C ,

P δ ,X

δ

which will not tend to zero if δ is chosen proportional to h. Of course, we have to take

into account that the native space norm to δ varies also with δ. But numerical examples

show that the interpolation error does not tend to zero for h ’ 0. Nonetheless, the error

goes down to a certain threshold and remains constant afterwards. This effect is sometimes

called approximate approximation (see for example Maz™ya and Schmidt [119]) and needs

further investigation in this context.

The distinction between stationary and nonstationary settings plays a particularly impor-

tant role for interpolation on a grid. For example, in [155] Powell takes the stationary point of

view and shows that the “Gaussian fares badly”, since Gaussian interpolation does not even

provide uniform convergence. However, in [156] Ron makes a more general investigation,

which covers the nonstationary setting also, and he concludes that spectral convergence

holds for Gaussian interpolation. Hence when reading articles on approximation on a grid

one should always keep this distinction in mind.

If only one interpolant has to be computed, which in general will be the case in applications

(in contrast with numerical testing), the choice of the right support radius of a compactly

supported basis function is thus a delicate question. In a later chapter we will introduce

numerical methods that try to take advantage of the compact support and yield convergence

nonetheless.

186 Error estimates for radial basis function interpolation

Our ¬nal example deals with the approximation power of thin-plate splines.

Lemma 11.18 Let (x) = x 2k log x 2 with k ∈ N. For every ± ∈ Nd there exist ho-

2 0

mogenous polynomials p±,k , q±,k ∈ π|±| (Rd ) such that

D ± (x) = ( p±,k (x) + q±,k (x) log x 2 ) x

2k’2|±|

2

for every x = 0. In particular, there exists a constant c± such that |D ± (x)|

2k’|±|

¤ c± (1 + log x 2 ) x 2 for every x = 0, showing that ∈ C 2k’1 (Rd ).

Proof The proof is again by induction on the length of ±. For |±| = 0 there is nothing

to show. Now assume |±| ≥ 1. Without restriction we assume again ±1 ≥ 1. De¬ne γ =

(±1 ’ 1, ±2 , . . . , ±d )T . Then there exist homogeneous polynomials pγ ,k , qγ ,k of degree |γ |

such that

‚

D ± (x) = D γ (x)

‚x1

‚ 2k’2|γ |

= pγ ,k (x) + qγ ,k (x) log x 2 x 2

‚x1

‚ pγ ,k

= (x) x 2 + qγ ,k (x)x1 + 2(k ’ |γ |) pγ ,k (x)x1

‚x1 2

‚qγ ,k 2(k’|±|)

+ (x) x 2 + 2(k ’ |γ |)x1 qγ ,k (x) log x 2 x 2

‚x1 2

2k’2|±|

=: p±,k (x) + q±,k (x) log x .

x

2 2

The polynomials p±,k , q±,k are homogenous by the same arguments as those given in the

proof of Lemma 11.15.

If we proceed as in the case φ(r ) = r β to get estimates for thin-plate splines, we could

bound the derivatives of order 2k ’ 1 by

C

|D ± (x)| ¤ C(1 + log x 2 ) x ¤ 1’

x

2 2

> 0. This gives the bound

for every

C±

2

’2|±|

P (±) (x) ¤ ,

h 2k’

,X

which is not the full order we have in mind. Hence the obvious application of Theorem

11.11 is not appropriate in this case. The reason for this is mainly the use of the Taylor

polynomials. Instead, we have to use Theorem 11.9 directly.

Theorem 11.19 Suppose that ⊆ Rd is bounded and satis¬es an interior cone condition.

Let (x) = (’1)k+1 x 2k log x 2 . Denote the interpolant of a function f ∈ N ( ) based

2

on this basis function and the set of centers X = {x1 , . . . , x N } ⊆ by s f,X . Then there exist

constants h 0 , C > 0 such that

|D ± f (x) ’ D ± s f,X (x)| ¤ Ch X,

k’|±|

| f |N ()