| ’ xk )| ¤

max M (x j M (0)

2

1¤ j¤N k=1

k= j

for the chosen M. To this end we can assume that the maximum is taken for x1 = 0, i.e. that

N N

| M (x j ’ x k )| = |

max M (x k )|.

1¤ j¤N

k=2

k=1

k= j

Now the trick is to count the points in a different way. If we de¬ne

E n = {x ∈ Rd : nq X ¤ x < (n + 1)q X }

2

then we see that every x j , 2 ¤ j ¤ N , is contained in exactly one of the E n , n ≥ 1. Moreover,

since every ball B(x j , q X ) around x j with radius q X is essentially disjoint from a ball around

xk = x j with the same radius and since all these balls with center in E n are contained in

{x ∈ Rd : (n ’ 1)q X ¤ x ¤ (n + 2)q X },

2

we can estimate the number of centers in E n by comparing the volumes to get

#{x j ∈ E n } ¤ (n + 2)d ’ (n ’ 1)d ¤ 3d n d’1 ,

212 Stability

where the last inequality is easily shown by induction on d. From Proposition 5.6 we ¬nd

•0 (M) (d/2 + 1)2d/2+2 ’(d+1)

| M (x)| ¤ x 2

Mπ

d+1

(d/2 + 1)

2

4

= M (0) ,

π Mx 2

which allows us to bound M (x) on E n :

d+1

(d/2 + 1)

2

4

|ψ M (x)| ¤ , x ∈ En .

M (0)

π Mnq X

∞

n ’2 = π 2 /6 we get the bound

Thus if we use n=1

∞

N

| ¤ #{x j ∈ E n } sup |

M (x k )| M (x)|

x∈E n

k=2 n=1

∞

d+1

(d/2 + 1)

2

4

n ’2

¤ d

M (0) 3

π Mq X n=1

d+1

(d/2 + 1)π

2

12

= M (0)

18 Mq X

1

¤ M (0),

2

where the last inequality obviously holds for all M satisfying (12.2). To see that (12.3)

implies (12.2), remember Stirling™s formula from Proposition 5.2, which gives us here

π π 2 d+1

d (2e)’d e1/(3d)

(d/2 + 1) ¤

2

9 9

and

1/(d+1)

π π2

1/(d+1)

(2e)’d/(d+1) e1/[3d(d+1)]

(d/2 + 1) ¤d

2

9 9

π

¤ d √ e1/6 ¤ 0.531d,

3 2e

so that (12.3) is indeed suf¬cient.

Our next step is to apply this result to our collection of different basis functions. To this

end let us introduce the constants

1/(d+1) d

π (d/2 + 1)

2

1 Md

Md = 12 Cd =

and

2 (d/2 + 1) 23/2

9

so that the bound becomes

’d

»min (A ≥ Cd •0 (Md /q X )q X .

,X )

12.2 Lower bounds for »min 213

Of course, instead of using the exact bound for M in the de¬nition above we could also

de¬ne Md = 6.38d.

Our ¬rst example will be the Gaussian (x) = e’± x 2 , ± > 0. From Theorems 5.18 and

2

5.16 we know that the Fourier transform of the Gaussian is given by

(ω) = (2±)’d/2 e’ 2 /(4±)

2

,

x

which is clearly decreasing. Thus the in¬mum takes the value

•0 (M) = (2±)’d/2 e’M /±

2

,

giving

(x) = e’±

2

x

Corollary 12.4 For interpolation with , the minimal eigenvalue of the in-

2

terpolation matrix can be bounded by

’d

≥ Cd (2±)’d/2 e’Md /(q X ±) q X

2 2

»min (A ,X )

/(q X ±) ’d

≥ Cd (2±)’d/2 e’40.71d

2

2