Multivariate Interpolation and Approximation

by Translates of a Basis Function

Robert Schaback

Abstract. This contribution will touch the following topics:

• Short introduction into the theory of multivariate interpolation and approximation by finitely many (irregular) translates of a (not necessarily radial) basis function, motivated by optimal recovery of functions from discrete samples.

• Native spaces of functions associated to conditionally positive definite functions, and relations between such spaces.

• Error bounds and condition numbers for interpolation of functions from native spaces.

• Uncertainty Relation: Why are good error bounds always tied to bad condition numbers?

• Shift and Scale: How to cope with the Uncertainty Relation?

§1. Introduction and Overview

This contribution contains the author’s view of a certain area of multivariate interpolation and approximation. It is not intended to be a complete survey of a larger area of research, and it will not account for the history of the theory it deals with. Related surveys are [15, 21, 22, 27, 30, 47, 48, 58].

Section 2 will motivate why we are mainly interested in multivariate functions that are linear combinations

f(x) = ∑_{j=1}^{N} a_{j}Φ(x − x_{j}), x ∈ lR^{d}, a_{j} ∈ lR  (1.1)

of translates of a fixed basis function Φ : lR^{d} → lR, where X = {x_{1}, …, x_{N}} is a set of N scattered points in lR^{d}. The space of functions (1.1) often

Approximation Theory VIII 1 Charles K. Chui and Larry L. Schumaker (eds.), pp. 1–8. Copyright o^{c} 1995 by World Scientific Publishing Co., Inc. All rights of reproduction in any form reserved. ISBN 0-12-xxxxxx-x

carries a natural topology induced by an inner product, and its Hilbert space closure (the “native space” for Φ) will be studied in Section 3. Error bounds for interpolation of functions from the native space are intimately connected to upper bounds on A{−1 \atop X,Φ} for the N by N matrix

A_{X,Φ} := (Φ(x_{j} − x_{k}))_{1≤j,k≤N}.  (1.2)

This connection will be dealt with in Sections 4 and 5, where we see that basis functions Φ with good error bounds on their native space will necessarily have bad upper bounds for ∥A{−1 \atop X,Φ}∥. A consequence of this “uncertainty relation” is that one has to introduce scaled versions of Φ in order to cope with the bad condition of A_{X,Φ}. Thus the final section contains refined error bounds for approximation by scales of basis functions.

§2. Optimal Recovery via Discrete Sampling

Sampling theory provides a good reason for considering functions of the form (1.1). The most common example is the reconstruction of a univariate bandlimited function f by its sinc series

f(x) = ∑_{j∈Z Z} f(j) sinc (x − j)

with

sinc (x) = \frac{sin πx}{πx} .

But we do not want to start with (1.1). Instead, we shall pose the reconstruction problem in a general way and find later that (1.1) is the natural solution.

Assume we want to recover a multivariate function f : lR^{d} → lR from a sample of values y_{1} = f(x_{1}), …, y_{N} = f(x_{N}) on a discrete (and “scattered”) set X = {x_{1}, …, x_{N}} in lR^{d}. Besides these values, we only have partial information on the spectrum of f, i.e., on its Fourier transform. More precisely, if we know that

f(x) = (2π)^{−d} ∫_{lR_{d}} f̂(ω)e^{ix·ω}dω, x ∈ lR^{d}  (2.1)

recovers f from its Fourier transform f̂, we shall assume that f̂ lies in a weighted L_{2} space

L_{2}(ρ) := {g ∈ L_{1}(lR^{d}) : ∫_{lR_{d}} |g(ω)|^{2}ρ(ω)dω < ∞} ,

where ρ : lR^{d} → lR_{>0} ∪ {+∞} with ρ(−·) = ρ(·) is a Lebesgue–measurable function that is finite on at least an open subset of lR^{d}. These things can be generalized to a distributional setting, but we want to keep the presentation simple.

The weight ρ determines a norm ∥ ∥_{2,ρ} on the space

F := {f : lR^{d} → lR ∪ {±∞}, f̂ ∈ L_{2}(ρ) and (2.1)}  (2.2)

via the bilinear form

(f, g)_{2,ρ} := (2π)^{−d} ∫_{lR_{d}} \overline{f̂(ω)}ĝ(ω)ρ(ω)dω.

By symmetry of ρ and f̂(−ω) = \overline{f̂(ω)} this form is real–valued. Then we can ask for optimal recovery in the sense of the problem

Find f ∈ F with ∥f∥_{2,ρ} minimal
such that f(x_{j}) = y_{j}, 1 ≤ j ≤ N.

The solution is given by the following theorem whose proof contains some standard arguments that we include to make this paper self–contained.

Theorem 2.1. If \frac{1}{ρ} ∈ L_{1}(lR^{d}) and Φ̂ := \frac{1}{ρ} , then a solution of the above recovery problem exists uniquely and is necessarily of the form (1.1). The coefficients a = (a_{1}, …, a_{N})^{T} can be found by solving the system

A_{X,Φ}a = y  (2.3)

where y = (y_{1}, …, y_{N})^{T}. The matrix A_{X,Φ} comes from (1.2) and is positive definite and symmetric.

Proof. Assume first that a solution f ∈ F to the recovery problem does exist. By the usual perturbation argument for characterization of best approximations in Euclidean spaces we then have

(f, g)_{2,ρ} = 0  (2.4)

for all g ∈ F with g(x_{j}) = 0, 1 ≤ j ≤ N. Then there are a_{1}, …, a_{N} ∈ lR with

(f, g)_{2,ρ} = ∑_{j=1}^{N} a_{j}g(x_{j})

for all g ∈ F, and we introduce Fourier transforms on both sides to get

(2π)^{−d} ∫_{lR_{d}} \overline{f̂(ω)}ĝ(ω)ρ(ω)dω = (2π)^{−d} ∫_{lR_{d}} ĝ(ω) ∑_{j=1}^{N} a_{j} · e^{iω·x_{j}}dω

for all g ∈ F. This is satisfied if and only if

f̂(ω) = \frac{1}{ρ(ω)} ∑_{j=1}^{N} a_{j}e^{−iω·x_{j}} =: Φ̂(ω) · σ_{a,X}(ω)

Φ̂ = \frac{1}{ρ} , σ_{a,X} := ∑_{j=1}^{N} a_{j}e^{−iω·x_{j}}

or iff f is of the form (1.1).

Our argument clearly shows how translates of a basis function come up very naturally, but so far it is no proof of the theorem. To prove existence, we show that A_{X,Φ} is positive definite. Indeed, for any a ∈ lR^{N} we have

a^{T} A_{X,Φ}a = ∑_{j,k=1}^{N} a_{j}a_{k}Φ(x_{j} − x_{k})

= (2π)^{−d} ∫_{lR_{d}} \frac{1}{ρ(ω)} |σ_{a,X}(ω)|^{2}dω  (2.5)

and this nonnegative quantity is zero iff σ_{a,X}(ω) vanishes on the support of 1/ρ. But this support contains an open set and σ_{a,X} is analytic. Thus σ_{a,X}(ω) vanishes on lR^{d} iff (2.5) vanishes. Since the functions e^{−iω·x_{j}} are linearly independent, the positive definiteness of A_{X,Φ} follows.

But then there is a unique f of the form (1.1) that satisfies (ff) and thus minimizes ∥f∥_{2,ρ} under all other interpolants from F.

If f_{1} and f_{2} would both satisfy (2.4) and the interpolation conditions, then ∥f_{1} − f_{2}∥{2 \atop 2,ρ} = 0 follows from (2.4) and this proves unicity in general.

Theorem 2.1 shows that translates of a single basis function naturally arise when solving an optimal recovery problem in spaces F of functions with Fourier transforms in weighted L_{2} spaces. Note that shifts or translates do not directly occur in the problem setting, except that F is a space that is invariant under all shifts of translations in lR^{d}. The notion “shift invariant space”, however, has been extensively used (see e.g., [11, 12, 13]) for spaces invariant under shifts in Z Z^{d} only. We remark in passing that a function space F necessarily is of the form (2.2), provided that it is

(a) a Hilbert space,

(b) continuously imbedded in L_{2}(lR^{d}),

(c) allowing continuous point evaluation functionals δ_{x}f = f(x) for f ∈ F and x ∈ lR^{d}, and

(d) separating points in lR^{d}, and (e) invariant under all shifts in lR^{d}.

The weight function ρ then comes out to be ρ = 1/Φ̂ with Φ(x − y) := (δ_{x}, δ_{y})_{F′} for x, y ∈ lR^{d}. Details of this will be given in a forthcoming paper.

To give the reader an idea of the scope of this approach, we first recall an example with a very small space F of functions, i.e., the bandlimited functions. Here, the weight function is

ρ_{p}(x) = \{ \begin{matrix}1 & x ∈ B_{p} \\ ∞ & x ∉ B_{p} \end{matrix} \}

where B_{p} is the unit ball with respect to the L_{p} norm in lR^{d}. Then 1/ρ_{p} coincides with the characteristic function χ_{B_{p}} of B_{p} and Φ̂ = χ_{B_{p}} holds. If p = ∞, then Φ is a d–fold tensor product of sinc functions. For p = 2 we get the jinc functions

Φ(x) = ∥x∥{−d/2 \atop 2}J_{d/2}(∥x∥_{2})

up to multiplicative constants. This is the simplest instance of a radial basis function Φ, i.e.,

Φ(x) = ϕ(∥x∥_{2}), ϕ : lR_{≥0} → lR.

Adopting the terminology of signal analysis, we note that this case yields very good localization in the frequency domain, because Fourier transforms are compactly supported. In the time domain we have algebraically decaying functions

Φ(x) = ∥x∥{−d/2 \atop 2}J_{d/2}(∥x∥_{2}) = O(∥x∥{−(d+1)/2 \atop 2})

for ∥x∥_{2} → ∞.

A more straightforward example with a small space F is given by the Gaussian Φ(x) = e^{−∥x∥^{2}/2} which is symmetric in time and frequency domain.

Note that the bandlimited case cannot be turned upside down by swapping frequency and time domain, because the jinc functions have sign changes and cannot be used as weight functions. To construct compactly supported functions with nonnegative Fourier transforms, some additional techniques are needed. For instance, convolution in the time domain always produces nonnegative Fourier transforms, but the problem then is to evaluate the result in the time domain. We cite a successful construction due to Wu [64] that proceeds as follows:

Table 1.

Time–Frequency Localization.

Time (∥x∥_{2} → ∞)  Frequency (∥ω∥_{2} → ∞)
Bandlimited  ∥x∥{−(d+1)/2 \atop 2}  comp. supported
W k 2(lR^{d})  ∥x∥{k−(d+1)/2 \atop 2}e^{−∥x∥_{2}}  ∥ω∥{−2k \atop 2}
Gaussian  e^{−∥x∥_{2}^{2}/2}  e^{−∥ω∥_{2}^{2}/2}
inverse  −d < 2β
Multiquadrics  (c^{2} + ∥x∥_{2}^{2})^{β}, β < 0  ∥ω∥{−(β+d+1)/2 \atop 2} · e^{−∥ω∥_{2}}
Φ_{ℓ,k} (Wu)  comp. supported  ∥ω∥{−2(ℓ+1+m−k) \atop 2}

in lR^{2m+1},

0 ≤ m ≤ k ≤ ℓ

\begin{aligned}φ_{ℓ}(r) & := (1 − r^{2})ℓ+ \\ ϕ_{ℓ,0} & := φ_{ℓ} ∗ φ_{ℓ} \\ ϕ_{ℓ,k}(r) & := (− \frac{1}{r} \frac{d}{dr} ) ϕ_{ℓ,k−1}(r) 1 ≤ k ≤ ℓ. \end{aligned}

It generates radial functions

Φ_{ℓ,k}(x) := ϕ_{ℓ,k}(∥x∥_{2})

that are positive definite on lR^{d} for d ≤ 2k + 1. Details of this construction can be found in [64], and a toolbox for handling radial functions is in [59].

A rather large space F is generated by the weight

ρ_{k}(ω) = (1 + ∥ω∥^{2})^{k}, ω ∈ lR^{d}

for 2k > d, and we get Sobolew space

F = W k 2(lR^{d})

and the corresponding optimal basis function

Φ(x) = ∥x∥{−(k−d/2) \atop 2}K_{k−d/2}(∥x∥_{2}),

where K_{ν} is the Bessel function of third kind. Since the K_{ν} functions are nonnegative, this example can be turned upside down and yields “inverse multiquadrics”

Φ(x) = (1 + ∥x∥_{2}^{2})^{β/2}

for 0 > β > −d, where now

ρ(ω) = ∥ω∥{(β+d)/2 \atop 2}K{−1 \atop (β+d)/2}(∥ω∥_{2})

acts as a weight function for the Fourier transforms. Note that this example and the Gaussian force Fourier transforms of functions in F to decay exponentially. Thus the space F consists of C^{∞} functions.

We summarize the known prototypes in Table 1 and remark that something like the “up”–function still is missing: a case with compact support and C^{∞} smoothness in the time domain while having exponential decay and positivity in the Fourier domain.

Historical Remarks

There is a vast literature on optimal recovery starting from Golomb/Weinberger [24] continuing via Sard [52], Micchelli/Rivlin [38], using results on abstract spline theory as recently summarized by Atteia [3] and ending up in Information–based Complexity as defined in Traub/Woźniakowski [63] and Bojanov/Woźniakowski [10]. Sampling theory also is a wide–ranging field (see e.g., the review by Butzer/Stens [16]). We borrowed the ingredients of our presentation from the folklore of both subjects, ignoring (so far) the background of reproducing–kernel Hilbert spaces that will show up in the next section. Spaces of functions that have Fourier transforms in weighted L_{2} spaces occur as examples for complex interpolation theory in the fundamental papers of Calderon [17] and Schechter [60]. See the review of Pisier [46] in this volume for details of complex interpolation. We touch upon another connection to interpolation theory of normed vector spaces at the end of Section 6. Another important link to classical results arises with the theory of Riesz and Bessel potentials, which correspond to thin–plate splines and multiquadrics. See, for instance, Aronszajn [1] and Calderon [18]. Our view on native spaces as “principal translation– invariant spaces” borrows from ideas of de Boor, de Vore and Ron [11, 12, 13] on shift–invariant spaces.

§3. Native Spaces

The preceding section showed that optimal reconstruction of functions in a quite general translation–invariant space F of functions naturally leads to the consideration of functions that are linear combinations of translates of a single basis function Φ. Thus the space F determined a function Φ.

We now go the opposite direction and start with a function Φ to generate a “native” space F. In contrast to the first approach we do not work on all of lR^{d} but rather on a subdomain Ω ⊂ lR^{d}.

Definition 3.1 A function Φ : Ω − Ω → lR with Φ(−·) = Φ(·) is positive definite on Ω, if for all sets X = {x_{1}, …, x_{N}} of N pairwise distinct points in Ω the matrix A_{X,Φ} in (1.2) is positive definite.

Note that there is a slight difference in terminology with [39, 61, 62] and others, but it definitely is bad notation to call Φ positive definite when A_{X,Φ} is positive semidefinite or nonnegative definite for all X.

The space D(Ω) of all finitely supported linear functionals on the space lR^{Ω} of all real–valued functions on Ω can now be equipped with an inner product. Indeed, if functionals

λ = ∑_{i=1}^{M} λ_{i}δ_{x_{i}} ∈ D(Ω),  μ = ∑_{j=1}^{N} μ_{j}δ_{y_{i}} ∈ D(Ω)  (3.1)

with λ_{i}, μ_{j} ∈ lR, x_{i}, y_{j} ∈ Ω are given, then

(λ, μ)_{Φ} := ∑_{i=1}^{M} ∑_{j=1}^{N} λ_{i}μ_{j}Φ(x_{i} − y_{j})

is an inner product on D(Ω), and we can form the Hilbert space \overline{D(Ω)} by taking the closure with respect to (·, ·)_{Φ}. Note that our first definition of a space concerned a space of functionals, but now we can go over to functions of the form (1.1) by

f_{λ}(x) := ∑_{i=1}^{M} λ_{i}Φ(x − x_{i}) = (δ_{x}, λ)_{Φ}  (3.2)

for λ from (3.1) and x ∈ Ω. Allowing all λ ∈ \overline{D(Ω)} we define the native space for Φ to be

F_{Φ,Ω} := \{f_{λ}(x) = (δ_{x}, λ)_{Φ}, x ∈ Ω, λ ∈ \overline{D(Ω)}\}  (3.3)

and this space can easily shown to be isometrically isomorphic to \overline{D(Ω)} because of

μ(f_{λ}) = (λ, μ)_{Φ}

for all λ, μ ∈ \overline{D(Ω)}, if we define

(f_{λ}, f_{μ})_{Φ} := (λ, μ)_{Φ}

on F_{Φ,Ω}. An equivalent definition, as given by Madych and Nelson [31, 32, 33] in case of Ω = lR^{d}, is the space

F_{Φ,Ω} = {f : Ω → lR : |μ(f)| ≤ C(f)∥μ∥_{Φ}, μ ∈ D(Ω)}  (3.4)

of all functions on Ω that allow all elements of D(Ω) as bounded linear functionals with respect to the topology induced by Φ on D(Ω).

If we look at the dependence of F_{Φ,Ω} on Ω, we should consider a subdomain Ω_{1} ⊆ Ω. Since clearly D(Ω_{1}) ⊆ D(Ω), we find

F_{Φ,Ω_{1}} ⊆ F_{Φ,Ω|Ω_{1}} := {f ∈ F_{Φ,Ω} restricted to Ω_{1}}

if we use (3.3), but the equivalent definition (3.4) implies F_{Φ,Ω|Ω_{1}} ⊆ F_{Φ,Ω_{1}}.

This proves Iske’s extension theorem

F_{Φ,Ω|Ω_{1}} = F_{Φ,Ω_{1}} for Ω_{1} ⊂ Ω,

if Φ is positive definite on Ω (see [26]). In case of Ω = lR^{d} it implies that any function in a native space F_{Φ,Ω_{1}} corresponding to a domain Ω_{1} has a (non–unique) extension to all of lR^{d} that preserves all the implicit smoothness assumptions that are hidden in the definition of F_{Φ,Ω}. In case of the Gaussians or the inverse multiquadrics all functions in F_{Φ,Ω_{1}} are restrictions of functions in F_{Φ,Ω} ⊂ C^{∞}(lR^{d}), i.e., they have canonical C^{∞}(lR^{d}) extensions. The construction of an extension is clear from the definition of F_{Φ,Ω_{1}}, since the function

f_{λ}(x) := (δ_{x}, λ)_{Φ}

for λ ∈ \overline{D(Ω_{1})} ⊆ \overline{D(Ω)} can not only be evaluated for x ∈ Ω_{1}, but also for x ∈ Ω, thus providing an extension. It is an interesting question to ask for the maximal domain Ω on which a given function Φ is positive definite; the existence of non–extensible positive definite functions on bounded domains is a hard problem already in the one–dimensional case (see [28, 61]), and there are results of Rudin [50, 51] and Krein [28] in the multivariate case. Another challenge is the full characterization of positive definite functions on lR^{d} under the weakest possible assumptions (see e.g., [19, 25, 62, 65] for this problem).

Historical Remarks

Our presentation mainly follows ideas of Madych-Nelson [31] but confines itself to unconditionally positive definite functions. The work of Madych-Nelson in turn builds mainly on results of the French school, expecially on Duchon’s thin–plate splines [20] and earlier work on abstract spline theory as provided by Atteia [2], Laurent [29], and later also by Meinguet [37].

§4. Error Bounds and Pointwise Optimality

Consider quasi–interpolants of the form

f ↦ s_{f,u,X} = ∑_{j=1}^{N} f(x_{j}) · u_{j}  (4.1)

where X = {x_{1}, …, x_{N}} ⊂ Ω ⊆ lR^{d} is a set of scattered points, and where u_{1}, …, u_{N} : Ω → lR are arbitrary functions. If x ∈ Ω is fixed, the error functional

ε_{x,u,X}(f) := f(x) − s_{f,u,X}(x)

is in D(Ω), and thus there is an error bound of the form

|ε_{x,u,X}(f)| ≤ ∥f∥_{Φ} · ∥ε_{x,u,X}∥_{Φ}  (4.2)

for functions f in the native space F_{Φ,Ω}. The norm of the error functional is explicitly available via

∥ε_{x,u,X}∥2 Φ = Φ(0) − 2∑_{j=1}^{N} u_{j}(x)Φ(x − x_{j})

+ ∑_{k=1}^{N} ∑_{j=1}^{N} u_{k}(x)u_{j}(x)Φ(x_{k} − x_{j}).  (4.3)

This allows comparison of various quasi–interpolants, and one can ask for an optimal choice of u_{1}(x), …, u_{N}(x) that minimizes ∥ε_{x,u,X}∥2 Φ in the above representation as a nonnegative quadratic form. If u^{∗} := (u∗ 1(x), …, u∗ N(x))^{T} denotes the minimizer, then clearly

∑_{j=1}^{N} Φ(x_{k} − x_{j})u∗ j(x) = Φ(x − x_{k}),  1 ≤ k ≤ N.  (4.4)

Thus the functions u∗ j(x) are in the span of the Φ(x − x_{k}), 1 ≤ k ≤ N, and they necessarily satisfy the Lagrange–type interpolation conditions

u∗ j(x_{k}) = δ_{jk}, 1 ≤ j, k ≤ N,

since the system (4.4) is uniquely solvable due to the positive definiteness of the coefficient matrix we already know from Theorem 2.1. This proves Theorem 4.1. The interpolant of the form (1.1) to scattered data is the unique minimizer of the error bound (4.2) under all quasi–interpolants (4.1).

Note that this result indicates that general error bounds in native spaces cannot be improved by choosing the shifts occurring in (1.1) different from the data locations used in (4.1).

It is interesting to plot the pointwise norms ∥ε_{x,u,X}∥_{Φ} of the error functionals as a function of x for u = u^{∗} or for different choices of u. This makes sense even in the classical univariate situation, and it would be worthwhile for applications to see a series of illustrative examples. Minimization with respect to u may lead to unexpected results in other than Hilbert space settings (for instance in W 1 ∞[a, b]). Another possibility is the variation of X while always using the optimal interpolant u^{∗} that will depend on X. Then ∥ε_{x,u^{∗},X}∥2 Φ will be a smooth function that allows minimization with respect to X. This may lead to a future theory that generalizes perfect splines. Numerical results of A. Beyer [8] were encouraging.

At this point it is by no means evident that the interpolant s_{f,u^{∗},X} minimizes ∥s∥2 Φ under s ∈ F_{Φ,Ω} with s(x_{j}) = f(x_{j}) for 1 ≤ j ≤ N, because there is no apparent link between ∥ ∥_{Φ} of this section and ∥ ∥_{2,ρ} of Section 2. To bridge this gap in full generality seems to be an open problem which is related to the full characterization of (strictly) positive definite functions, as posed in the survey of E.W. Cheney [19] in this volume. If Φ can be recovered from its Fourier transform via

Φ(x) = (2π)^{−d} ∫_{lR_{d}} Φ̂(ω)e^{iω·x}dω,

and if λ is a functional of the form (3.1), then

∥f_{λ}∥2 Φ = ∥λ∥2 Φ
= (2π)^{−d}∫_{lR_{d}} Φ̂(ω) |∑_{j=1}^{N} λ_{j}e^{iω·x_{j}} |^{2} dω.  (4.5)

Furthermore, the function f_{λ} of (3.2) will then have a Fourier transform

f̂_{λ}(ω) = Φ̂(ω) ∑_{j=1}^{N} λ_{j}e^{−iω·x_{j}}

such that we can formally write

∥f_{λ}∥2 Φ = (2π)^{−d} ∫_{lR_{d}} |f̂_{λ}(ω)|^{2} · \frac{1}{Φ̂(ω)} dω

to see the similarity between ∥ · ∥_{Φ} and ∥ · ∥_{2,ρ} with ρ = 1/Φ̂.

The aforementioned characterization problem for (strictly) positive definite functions leads to some specific questions in this context:

1) Which conditions guarantee the existence of Φ̂ ∈ L_{1}(lR^{d}) needed for (4.5)?

2) What are the properties of Φ̂ that ensure (4.5) to be an inner product? A partial answer to 1) was given by Iske in this dissertation. If Φ is

locally absolutely integrable and of at most polynomial growth, then it has a generalized Fourier transform Φ̂. For Φ positive definite, Iske proved under mild additional assumptions that Φ̂ is in L_{1}(lR^{d}). The second question is more difficult, because it involves the structure of the possible zeros of limits of exponential sums as occurring in (4.5). In the univariate case this requires tools from almost periodic functions (see Fang [23]).

The optimal error bound (4.2) is rather abstract and needs further elaboration in terms of the density of the data. A bounded domain Ω ⊂ lR^{d} usually is fixed, and for a positive τ ∈ lR one considers a local density

h_{X,τ} (x) := sup_{∥y−x∥_{2}≤τ} min_{1≤j≤N} ∥y − x_{j}∥_{2}, x ∈ Ω  (4.6)

where for technical improvement one can replace the ball {y : ∥y−x∥_{2} ≤ τ} by cones or cubes with vertex x. Then there are three somewhat different techniques for proving error bounds of the form

∥ε_{x,u^{∗},X}∥2 Φ ≤ F_{Φ}(h_{X,τ} (x))  (4.7)

with F : lR_{≥0} → lR_{≥0} monotonic and F (0) = 0. If (4.7) holds, then (4.2) becomes

|f(x) − s_{f,u^{∗},X}(x)| ≤ ∥f∥_{Φ} · F {1/2 \atop Φ}(h_{X,τ} (x))  (4.8)

for all X = {x_{1}, …, x_{N}} ⊂ Ω and all x ∈ Ω with h_{X,τ} (x) ≤ h_{0}, where h_{0} is a positive constant depending only on τ, Φ, and Ω. Table 2 shows the currently known functions F_{Φ} for various choices of Φ. Note, however, that Φ determines both F_{Φ} and ∥.∥_{Φ}, making error bounds hard to compare. In general, F_{Φ} gets smaller with improving smoothness of Φ, but at the same time ∥.∥_{Φ} gets more restrictive, since 1/Φ̂ acts as a penalty weight for Fourier transforms.

We finally give the reader some pointers to the three proof techniques of (4.7). The first is confined to radial functions Φ(x) = ϕ(∥x∥_{2}), but does not involve Fourier transforms. It reduces the problem to quantitative polynomial approximation of ϕ on [0, h] for h → 0, and dates back to Madych-Nelson [32], being refined somewhat in [34]. The other two use Fourier transforms of non–radial functions and can be found in Madych-Nelson [33] and Wu/Schaback [66]. In all three cases it is crucial to have good bounds on Lebesgue constants of polynomial interpolation of perturbed regular data in lR^{d}. By using explicit geometric configurations for few data points, Powell [49] could get small and explicit bounds for thin– plate splines via knowledge of good Lebesgue constants. The problem of optimal bounds for Lebesgue constants of multivariate polynomial interpolation is still open in general and its solution would improve the known error bounds of type (4.8) a lot. To our knowledge, the best general bounds are in [34], and papers by Bloom [9] and Bos [14] show what is possible for regular data.

§5. Condition Numbers and Uncertainty Relation

Numerical experiments show that the condition number of A_{X,Φ} as in (1.2) is terribly large for smooth Φ like Gaussians or Multiquadrics when compared to non–smooth Φ like thin–plate splines. The spectral condition number of A_{X,Φ}, being the quotient of largest and smallest eigenvalue, was observed to be boosted up mainly because of the smallest eigenvalue being extraordinarily small. To understand this phenomenon, a series of papers by Ball, Baxter, Narcowich, Sivakumar, and Ward [4, 5, 6, 7, 40, 41, 42, 43, 44, 45] investigated lower bounds

λ^{T} A_{X,Φ}λ ≥ c(X, Φ)∥λ∥2 2

of the quadratic form associated with A_{X,Φ}. This is equivalent to bounding the smallest eigenvalue of A_{X,Φ} from below.

The basic trick in most of these papers is to construct a “minorant” Ψ such that

λ^{T} A_{X,Φ}λ ≥ λ^{T} A_{X,Ψ}λ ≥ c(X, Ψ)∥λ∥2 2,

where A_{X,Ψ} is diagonally dominant and c(X, Ψ) is readily available. A short and general account of the technique can be found in [56]. The results are always of the form

c(X, Φ) ≥ G_{Φ}(q_{X})

where G_{Φ} : lR_{≥0} → lR_{≥0} is a monotonic function with G(0) = 0, and

q_{X} := \frac{1}{2} min_{1≤j<k≤N} ∥x_{j} − x_{k}∥_{2}

is the separation distance of points in X. Note that the bound does not depend on the number N of data points. Up to multiplicative constants, Table 2 shows the special cases known so far (see [56] for details).

There is a striking similarity between the functions F_{Φ} and G_{Φ}, and it seems to be impossible to find cases where the interpolation error, given by F {1/2 \atop Φ}, is small and the condition, partly given by G{−1 \atop Φ}, is small as well.

This kind of “Uncertainty Relation” can be put on a solid basis by a simple argument from [56] that bridges the gap between upper bounds on errors for interpolants by X–translates of Φ and lower bounds on eigenvalues of A_{X,Φ}. In fact, if we formally add x_{0} := x to the data set X and define

\begin{aligned}A_{x} & := A_{X∪\{x\},Φ} \\ λ∗ x := & (1, −u∗ 1(x), …, −u∗ N(x)) \\ q_{x} & := min_{0≤j<k≤N}∥x_{j} − x_{k}∥ \end{aligned}

then, when interpreted as an error bound,

λ∗ xA_{x}λ∗ x = ∥ε_{x,u^{∗},X}∥2 Φ ≤ F_{Φ}(h_{X,τ} (x)),

and when interpreted as a quadratic form,

\begin{aligned}λ∗ xA_{x}λ∗ x & ≥ G_{Φ}(q_{x}) · ∥λ∗ x∥2 2 \\ & = G_{Φ}(q_{x}) (1 + ∑_{j=1}^{N}|u∗ j(x)|^{2}) . \end{aligned}

Thus

G_{Φ}(q_{x}) ≤ G_{Φ}(q_{x}) (1 + ∑_{j=1}^{N} |u∗ j(x)|^{2}) ≤ F_{Φ}(h_{X,τ} (x))  (5.1)

proves that for comparable small arguments with

h_{X,τ} (x) ≈ h ≈ q_{x}  (5.2)

one cannot have a small error bound F_{Φ}(h) without having a small lower bound G_{Φ}(h) on the smallest eigenvalue. And (5.2) clearly is possible for regular data sets X of spacing h and x placed at distance ≥ h/2 from all points of X.

There are some further consequences of the Uncertainty Relation in the form (5.1). First, it suggests that optimal results are obtained in cases calculated near the limits of machine precision, may these be reached by huge amounts of densely distributed data points for non–smooth Φ, or may these be reached by moderate numbers of data points for smooth functions like e.g., the Gaussians. When reconstructing surfaces from scattered data and varying certain parameters like c for multiquadrics (c^{2} + r^{2})^{β/2} such that the condition of A_{X,Φ} tends towards the limits of machine precision, the nicest picture always is the one that immediately preceded the numerical breakdown.

Table 2.

All entries are modulo factors that are independent of r and h, but possibly dependent on parameters of Φ. Unreferenced cases for G are treated in [56].

Φ(x) = ϕ(r), r = ∥x∥_{2}  F_{Φ}(h)  G_{Φ}(h)
r^{β}, β ∈ lR_{>0} \ 2lN  h^{β}  h^{β}
[4]: d = β = 1
thin–plate splines [66] [5], pg. 419: β ∈ (0, 2)
[45], § VI: β = m − d/2,
d odd
(−1)^{1+β/2}r^{β} log r, β ∈ 2lN  h^{β}  h^{β}
thin–plate splines  [66]  [45], § VI: β = m − d/2,
d even
(γ^{2} + r^{2})^{β/2}, β ∈ lR \ 2lN_{≥0}  e^{− \frac{δ}{h}}  h^{2}e^{− \frac{6}{h}} [42], pg. 90:
γ = 1 = β, d = 2,
Multiquadrics δ > 0 he^{− \frac{2d}{h}} [5], pgs. 422–423:
γ = 1 = β
[34]  h^{β} exp(−12.76γd/h)
e^{−βr^{2}}, β > 0  e^{− \frac{δ}{h^{2}}}  h^{−d}e^{− \frac{γ}{h^{2}}} [45], pg. 90: β = 1
Gaussians  δ > 0 [34] h^{−d} exp(−40.71d^{2}/(βh^{2}))
\frac{2π^{d/2}}{Γ(k)} K_{k−d/2}(r)(r/2)^{k−d/2}  h^{2k−d}  h^{2k−d}
2k > d,  as in [66],

Sobolev splines

Second, one gets both new lower bounds for F_{Φ}, and upper bounds for G_{Φ} exhibiting the leeway for further optimization of both bounds. This improves earlier work by Ball/Sivakumar/Ward [5] and Schaback [53] on upper bounds for G_{Φ}(q_{x}), and it opens the race for closing the gap as much as possible by finding optimal constants.

We now want to compare several basis functions. Since we know that any basis function yields optimal error bounds with respect to its “native” space, the comparison must take place in “alien” spaces. We fix basis functions Φ_{1} and Φ_{2} with native spaces F_{Φ_{1}} and F_{Φ_{2}}, and assume

F_{Φ_{1}} ⊆ F_{Φ_{2}},

so that now F_{Φ_{2}} is alien to Φ_{1} and vice versa. The data set X will be dropped in the notation for the rest of this section, and we denote by s_{f,j} the interpolant to f on some X with respect to Φ_{j}.

We first consider interpolation of functions f ∈ F_{Φ_{2}} by translates of Φ_{1}. These cannot reach the optimal error bounds for interpolation by Φ_{2}–translates, but they can be quasi–optimal in the sense

|f(x) − s_{f,1}(x)| ≤ C · ∥f∥_{Φ_{2}} · F {1/2 \atop Φ_{2}}(h_{X}(x))  (5.3)

with a constant C ≥ 1. Numerical results [53] suggest that quasi–optimality often holds, but so far there is only a proof for slightly perturbed interpolants [57] instead of s_{f,1}. The proof technique first involves an approximation f_{ε} of f up to some ε by chopping off the Fourier transform of f. Then f_{ε} ∈ F_{Φ_{1}} holds and the bounds

\begin{aligned}|f(x) − f_{ε}(x)| & ≤ ε \\ |f_{ε}(x) − s_{f_{ε},1}(x)| & ≤ ∥f_{ε}∥_{Φ_{1}} · F {1/2 \atop Φ_{1}}(h_{X}(x)) \end{aligned}

are used to prove (5.3) by choosing ε as a function of ∥f∥_{Φ_{2}} and F {1/2 \atop Φ_{2}}(h_{X}(x)) in a proper way, roughly by letting ε take the form of the right–hand side of (5.3). Unfortunately, this part of the proof does not work in general. So far, each of the traditional examples required a special analysis.

The fact that slightly perturbed interpolants often work better than exact interpolants is well known from other areas of Approximation Theory. It takes here a very specific form, and it was called “appproximate approximation” in recent papers [35, 36] by Maz’ya and Schmidt, used there in the somewhat different context of quasi–interpolation on gridded data with nonstationary Gaussians. In general, the notion of “approximate” approximation uses a two–parameter family {s_{h,δ}} of approximants (think of a shift parameter h and a scale parameter δ) such that there is no Weierstraß–type density result for h → 0 and δ fixed, but where for each ε > 0 there is some δ > 0 such that

∥f − s_{h,δ}(f)∥ ≤ ε + K(f, h, δ)

with K(f, h, δ) → 0 for h → 0.

To give the reader an idea how this applies in our context, let δ be a parameter that controls chopping the Fourier transform of some general function f ∈ L_{1}(lR^{d}) ∩ L_{2}(lR^{d}) at radius 1/δ, such that

|f(x) − (2π)^{−d} ∫_{∥ω∥≤δ^{−1}} f̂(ω)e^{iω·x}dω|

≤ (2π)^{−d} ∫_{∥ω∥≥δ^{−1}} |f̂(ω)|dω =: E(f, δ) ≤ ε

for δ small enough. The function

f̃(x) := (2π)^{−d} ∫_{∥ω∥≤δ^{−1}} f̂(ω)e^{iω·x}dω

now lies in the native space for any basis function Φ with Φ̂ ∈ L_{1}(lR^{d}) and Φ̂ > 0 on lR^{d}, and has norm

∥f̃∥2 Φ := (2π)^{−d} ∫_{∥ω∥≤δ^{−1}} \frac{|f̂(ω)|^{2}}{Φ̂(ω)} dω

≤ ∥f∥2 2 · (2π)^{−d}∫_{∥ω∥≤δ^{−1}} \frac{1}{Φ̂(ω)} dω

=: ∥f∥2 2 · L^{2}(Φ, δ)

where L(Φ, δ) tends to infinity for δ → 0, depending on the decay properties of Φ̂ at infinity. Now we have

|f(x) − f̃(x)| ≤ E(f, δ)
|f̃(x) − s_{f̃,X}(x)| ≤ ∥f̃∥_{Φ} · F {1/2 \atop Φ}(h_{X}(x))
≤ ∥f∥_{L_{2}} · L(Φ, δ) · F {1/2 \atop Φ}(h_{X}(x))

and by picking a suitably small δ(f, ε) we can get a bound

|f(x) − s_{f̃,X}(x)| ≤ ε + C(f, ε, Φ) · F {1/2 \atop Φ}(h_{X}(x)).

Note that for h_{X}(x) → 0 for sufficiently dense data sets X the second part of this bound behaves precisely like the bound of optimal interpolation in the native space, and this means exponential convergence in case of Gaussians or multiquadrics, for instance.

The above discussion of approximate approximation is related to K– functionals. Indeed, for any f from the space BC(\overline{Ω}) of all bounded and continuous functions on the closure of a bounded domain Ω ⊂ lR^{d} we can write

\begin{aligned}|f(x) − s_{g}(x)| & ≤ |f(x) − g(x)| + |g(x) − s_{g}(x)| \\ & ≤ |f(x) − g(x)| + ∥g∥_{Φ}F {1/2 \atop Φ}(h_{X}(x)) \end{aligned}

if s_{g} is the interpolant to some intermediate function g ∈ F_{Φ} and X = {x_{1}, …, x_{N}} ⊂ Ω. Thus

inf_{s∈S_{X,Φ}} ∥f − s∥_{∞,Ω} ≤ inf_{g∈F_{Φ}}(∥f − g∥_{∞,Ω} + F {1/2 \atop Φ}(h_{X}) · ∥g∥_{Φ})
=: K(f, F {1/2 \atop Φ}(h_{X}), BC(Ω), F_{Φ})

with h_{X} := ∥h_{X}(x)∥_{∞,Ω} and S_{X,Φ} standing for the space of functions of the form (1.1). It would be very interesting to see the classical machinery of K–functionals set to work towards Jackson–Bernstein theorems for approximation of functions from intermediate spaces between BC(Ω) and F_{Φ}.

§6. Shift and Scale

We now allow scaled versions

Φ_{δ}(·) = Φ ( \frac{·}{δ} ) , Φ̂_{δ}(·) = δ^{d}Φ(·δ) δ > 0

of a positive definite function Φ on lR^{d} and consider a fixed bounded domain Ω ⊂ lR^{d}. We first check the behavior of ∥ε_{x,u^{∗},X}∥{2 \atop Φ_{δ}} as a function of δ. Clearly, from the optimality of (4.4) we get

(2π)^{d}∥ε_{x,u^{∗},X}∥{2 \atop Φ_{δ}} = min_{u} ∫_{lR_{d}} Φ̂_{δ}(ω) |1 − ∑_{j=1}^{N} u_{j}(x)e^{iω·(x−x_{j})}|^{2} dω

= δ^{d} min_{u} ∫_{lR_{d}} Φ̂(ωδ) |1 − ∑_{j=1}^{N} u_{j}(x)e^{iω·(x−x_{j})}|^{2} dω

= min_{u} ∫_{lR_{d}} Φ̂(η) |1 − ∑_{j=1}^{N} u_{j}(x)e^{iη·(x−x_{j})/δ}|^{2} dη

= (2π)^{d}∥ε_{x/δ,u^{∗},X/δ}∥2 Φ

as everybody would expect. In view of (4.6) in the bound (4.7) we have

h_{X/δ,τ/δ}(x/δ) = sup_{∥y−x/δ∥≤τ/δ} min_{j} ∥y − x_{j}/δ∥

= \frac{1}{δ} h_{X,τ} (x) = \frac{1}{δ} sup_{∥y−x∥≤τ} min_{j} ∥y − x_{j}∥.

Thus (4.7) in the form

∥ε_{x,u^{∗},X}∥{2 \atop Φ_{δ}} = F_{Φ}(h_{X/δ,τ/δ}(x/δ)) = F_{Φ} ( \frac{1}{δ} h_{X,τ} (x))  (6.1)

shows that this part of the error depends on the relative scaling of Φ and the data, as expected. To make the first inequality of (6.1) fully valid we require a lower bound

τ/δ ≥ τ_{0} > 0

for τ/δ, or an upper bound

δ ≤ τ/τ_{0}

for δ. We introduce

h := h_{X,τ} := ∥h_{X,τ} (·)∥_{∞,Ω}

to keep the notation somewhat simpler. The error bound (4.8) then is

|f(x) − s_{f,Φ_{δ}}(x)| ≤ ∥f∥_{Φ_{δ}} · F {1/2 \atop Φ}(h/δ),

where s_{f,Φ_{δ}} is the interpolant to f with respect to Φ_{δ}. Note that the Uncertainty Relation does (at least for interpolation) not allow to make F_{Φ}(h/δ) arbitrarily small in practical applications. Ignoring the additional factor ∥f∥_{Φ_{δ}}, one would always be able to cope with large h by choosing a large δ to keep errors small. The stationary case of the literature takes δ proportional to h. We see that in this case convergence must come from the factor ∥f∥_{Φ_{δ}} for δ → 0, and this is the second reason why we now look at this quantity.

If we keep f fixed and check the condition ∥f∥_{Φ_{δ}} < ∞, then

(2π)^{d}∥f∥{2 \atop Φ_{δ}} = δ^{−d} ∫_{lR_{d}} \frac{|f̂(ω)|^{2}}{Φ̂(ωδ)} dω.

The first and simplest case is thin–plate splines with

Φ̂(ω) = ∥ω∥^{−d−β}

for some β > 0 and up to a constant factor. Then clearly f ∈ F_{Φ_{δ}} whenever f ∈ F_{Φ}, and

∥f∥{2 \atop Φ_{δ}} = δ^{β}∥f∥2 Φ.

Since in this case F_{Φ}(h) = c^{2}(β, d)·h^{β}, we can write the overall error bound as

|f(x) − s_{f,Φ_{δ}}(x)| ≤ c(β, d)δ^{β/2}(h/δ)^{β/2}∥f∥_{Φ}

and get invariance with respect to scaling, as expected.

Now let us consider functions Φ with monotonic radial decay of Φ̂, i.e.,

Φ̂(ωδ) ≥ Φ̂(ω) > 0 for all δ ≤ 1, ω ∈ lR^{d}.

Then

∥f∥_{Φ_{δ}} ≤ δ^{−d/2}∥f∥_{Φ_{1}}

for all f ∈ F_{Φ_{1}}, δ ≤ 1. The error bound now is

|f(x) − s_{f,Φ_{δ}}(x)| ≤ ∥f∥_{Φ_{1}} · δ^{−d/2}F {1/2 \atop Φ_{1}}(h/δ)

and one cannot use strictly stationary interpolation. Instead, one has to let h/δ tend to zero to let F {1/2 \atop Φ_{1}}(h/δ) outweigh the factor δ^{−d/2}. This is not very restrictive in case of exponential decay of Φ̂, i.e., for Multiquadrics and Gaussians, because then it suffices to let h/δ decrease logarithmically with h → 0, without spoiling exponential convergence for h → 0.

More problematic are cases with algebraic decay of F_{Φ_{1}}, say, of type F_{Φ_{1}}(h) = O(h^{k}). Then the error has the behavior

h^{k/2}δ^{(−k−d)/2}.

To achieve an error of O(h^{β/2}) with 0 < β ≤ k (look at thin–plate splines for comparison) one has to take a scaling like

δ = O (h^{\frac{k−β}{k+d}} ) .

This allows to trade small errors for good condition by a suitable scaling, and this was the goal of this section. However, we have so far left out the most interesting cases, namely the compactly supported positive definite functions. Their Fourier transforms partially have zeros or are not known to be monotonic. Another extension concerns approximation instead of interpolation. In both cases one can use the techniques of the preceding section to generate intermediate functions f_{δ} ∈ F_{Φ_{δ}} by chopping off the Fourier transform of f, and then interpolating f_{δ} by Φ_{δ}. We leave the details to a later presentation.

Acknowledgments. Help in proofreading was provided by A. Iske, and typing was done by P. Trapp.

References

1. Aronszajn, N., Potentiels Besseliens, Ann. Inst. Fourier Grenoble 15 (1965), 43–58.

2. Atteia, M., Analyse Numérique – Généralisation de la définition et des propriétés des spline functions, C.R. Acad. Sc., Paris, 260 (1965), 3550–3553.

3. Atteia, M., Hilbertian Kernels and Spline Functions, in: Studies in Computational Mathematics (4), North-Holland, Amsterdam, 1992.

4. Ball, K., Eigenvalues of Euclidean Distance Matrices, J. Approx. Theory 68 (1992), 74-82.

5. Ball, K., N. Sivakumar, and J.D. Ward, On the Sensitivity of Radial Basis Interpolation to Minimal Distance Separation, J. Approx. Theory 8 (1992), 401-426.

6. Baxter, B.J.C., Norm Estimates for Inverses of Distance Matrices, in Mathematical Methods in Computer Aided Geometric Design, T. Lyche and L.L. Schumaker (eds.), Academic Press, New York, 1989, 13–18.

7. Baxter, B.J.C., N. Sivakumar, J.D. Ward, Regarding the p–Norms of Radial Basis Interpolation Matrices, Techn. Report 281, Department of Mathematics, Texas A & M University, 1992.

8. Beyer, A., Optimale Centerverteilung bei Interpolation mit radialen Basisfunktionen, Diplom Thesis, Universität Göttingen, 1994.

9. Bloom, T., The Lebesgue Constant for Lagrange Interpolation in the Simplex, J. Approx. Theory 54 (1988), 338–353.

10. Bojanov, B., and H. Woźniakowski, Optimal Recovery, Nova Science Publishers, New York, 1992.

11. Boor, C. de, R.A. DeVore, and A. Ron, Approximation from Shift– invariant Subspaces of L_{2}(lR^{d}), Trans. Amer. Math. Soc. 341 (1994), 787–806.

12. Boor, C. de, R.A. DeVore, and A. Ron, The Structure of Finitely Generated Shift–invariant Spaces in L_{2}(lR^{d}) J. Funct. Anal. 119 (1994), 37–78.

13. Boor, C. de, and A. Ron, Fourier Analysis of Approximation Orders from Principal Shift–invariant Spaces, Constr. Approx. 8 (1992), 427– 462.

14. Bos, L.P., Bounding the Lebesgue Function for Lagrange Interpolation in a Simplex, J. Approx. Theory 38 (1983), 43–59.

15. Buhmann, M.D., New Developments in the Theory of Radial Basis Function Interpolation, in Multivariate Approximations: From CAGD to Wavelets, K. Jetter and F.I. Utreras (eds), World Scientific, London, 1993, 35–75.

16. Butzer, P.L., and R.L. Stens, Sampling Theory for Not Necessarily Band–limited Functions: A Historical Overview, SIAM Review 34 (1992), 40–53.

17. Calderón, A.P., Lebesgue Spaces of Functions and Distributions, Proc. Symp. Pure Math. 4, AMS, Providence (1961), 33–49.

18. Calderón, A.P., Intermediate Spaces and Interpolation, the Complex Method, Studia Math. 24 (1964), 113–190.

19. Cheney, E.W., Survey Talk (this volume).

20. Duchon, J., Splines Minimizing Rotation–invariant Semi–norms in Sobolev Spaces, in Constructive Theory of Functions of Several Variables, Springer, Berlin–Heidelberg, W. Schempp and K. Zeller (eds.), 1979, 85–100.

21. Dyn, N., Interpolation of Scattered Data by Radial Functions, in Topics in Multivariate Approximation, C.K. Chui and L.L. Schumaker and Florencio Utreras (eds.), Academic Press, Boston, 1987, 47-61.

22. Dyn, N., Interpolation and Approximation by Radial and Related Functions, in Approximation Theory VI, Vol. 1, C.K. Chui and L.L. Schumaker and J.D. Ward (eds.) Academic Press, Boston, 1989, 211– 234.

23. Fang, C. K., Strictly Positive Definite Functions, Preprint 1994.

24. Golomb, M., and H.F. Weinberger, Optimal Approximation and Error Bounds, in On Numerical Approximation, The University of Wisconsin Press, Madison, R.E. Langer (ed.), 1959.

25. Iske, A., Charakterisierung bedingt positiv definiter Funktionen für multivariate Interpolationsmethoden mit radialen Basisfunktionen, Ph. D. Dissertation, Göttingen, 1994.

26. Iske, A., Characterization of Function Spaces associated to Conditionally Positive Definite Functions, in Mathematical Methods in Computer Aided Geometric Design III, T. Lyche and L.L. Schumaker (ed.), Academic Press, New York, 1995.

27. Jetter, K., Multivariate Approximation from the Cardinal Interpolation Point of View, in Approximation Theory VII, E.W. Cheney and C.K. Chui and L.L. Schumaker (eds.), Academic Press, New York, 1992, 131–161.

28. Krein, M., Sur le problème du prolongement des fonctions hermitiennes positives et continues, Dokl. Akad. Nauk SSSR 26 (1940), 17–22.

29. Laurent, P.J., Construction of Spline Functions in a Convex Set, in Approximation with special emphasis on Spline Functions, I.J. Schoenberg (ed.), Academic Press, New York, 1969, 415–446.

30. Light, W., Using Radial Functions on Compact Domains, in Wavelets, Images, and Surface Fitting, P.–J. Laurent, A. Le Méhauté and L.L. Schumaker, (eds.), AKPeters, Boston, 1994, 351–370.

31. Madych, W.R., and S.A. Nelson, Multivariate Interpolation: a Variational Theory, Manuscript, 1983.

32. Madych, W.R., and S.A. Nelson, Multivariate Interpolation and Conditionally Positive Definite Functions, Approx. Theory Appl. 4 (1988), 77-89.

33. Madych, W.R., and S.A. Nelson, Multivariate Interpolation and Conditionally Positive Definite Functions II, Math. Comp. 54 (1990), 211– 230.

34. Madych, W.R., and S.A. Nelson, Bounds on Multivariate Polynomials and Exponential Error Estimates for Multiquadric Interpolation, J. Approx. Theory 70 (1992), 94–114.

35. Maz’ya, V., and G. Schmidt, On Approximate Approximations, Preprint LITH–MAT–R–94–12, Linköping Univ., Dept. of Math., Linköping 1994.

36. Maz’ya, V., and G. Schmidt, On Approximate Approximations Using Gaussian Kernels, WIAS Preprint 111, Weierstraß–Institut Berlin,

1994.

37. Meinguet, J., An Intrinsic Approach to Multivariate Spline Interpolation at Arbitrary Points, in Polynomial and Spline Approximation, Badri N. Sohnrey (ed.), D. Reidel Publishing Company, 1979, 163–190.

38. Micchelli, C.A., and T.J. Rivlin, Lectures on Optimal Recovery, in Numerical Analysis, Lancaster 1984, P.R. Turner (ed.), Springer Verlag, Lecture Notes in Mathematics 1129, 1984, 12–93.

39. Micchelli, C.A., Interpolation of Scattered Data: Distance Matrices and Conditionally Positive Definite Functions, Constr. Approx. 2 (1986), 11–22.

40. Narcowich, F.J., N. Sivakumar, and J.D. Ward, On Condition Numbers Associated with Radial–Function Interpolation, Techn. Report No. 287, Department of Mathematics, Texas A & M University, 1993.

41. Narcowich, F.J., and J.D. Ward, Norm Estimates for Inverses of Scattered–data Interpolation Matrices Associated with Completely Monotonic Radial Functions, Preprint.

42. Narcowich, F.J., N. Sivakumar, and J.D. Ward, Norm of Inverses and Condition Numbers for Matrices Associated with Scattered Data, J. Approx. Theory 64, 1991, 69–94.

43. Narcowich, F.J., J.D. Ward, Norms of Inverses for Matrices Associated with Scattered Data, in Curves and Surfaces, P.J. Laurent and A. Le Méhauté and L.L. Schumaker (eds.) Academic Press, Boston, 1991, 341–348.

44. Narcowich, F.J., J.D. Ward, Generalized Hermite Interpolation Via Matrix–valued Conditionally Positive Definite Functions, Math. Comp. 63 (1994), 661–687.

45. Narcowich, F.J., J.D. Ward, Norm Estimates for the Inverses of a General Class of Scattered–Data Radial–Function Interpolation Matrices, J. Approx. Theory 69 (1992), 84–109.

46. Pisier, G., Survey Talk on Interpolation (this volume)

47. Powell, M. J. D., Radial Basis Functions for Multivariable Interpolation: a Review, in Numerical Analysis, D. F. Griffiths and G. A. Watson (eds.), Longman Scientific & Technical (Harlow), 1987, 223-241.

48. Powell, M.J.D., The Theory of Radial Basis Function Approximation in 1990, in Advances in Numerical Analysis II: Wavelets, Subdivision Algorithms, and Radial Basis Functions, W.A. Light (ed.), Oxford Univ. Press, Oxford, 1992, 105-210.

49. Powell, M.J.D., The Uniform Convergence of Thin–plate Spline Interpolation in Two Dimensions, DAMTP Report 1993/NA16, Cambridge, U.K.

50. Rudin, W., The Extension Problem for Positive Definite Functions, Illinois J. Math. 7(1963), 532–539.

51. Rudin, W., An Extension Theorem for Positive Definite Functions, Duke Math. J. 37 (1970), 49–53.

52. Sard, A., Linear Approximation, Mathematical Surveys 9, AMS, Providence (1963).

53. Schaback, R., Comparison of Radial Basis Function Interpolants, in Multivariate Approximations: From CAGD to Wavelets, K. Jetter and F. Utreras, (eds), World Scientific, London, 1993, 293–305.

54. Schaback, R., Lower Bounds for Norms of Inverses of Interpolation Matrices for Radial Basis Functions, J. Approx. Theory 79 (1994), 287–306.

55. Schaback, R., Reproduction of Polynomials by Radial Basis Functions, Wavelets, Images, and Surface Fitting, P.–J. Laurent, A. Le Méhauté and L.L. Schumaker (eds.) AKPeters, Boston (1994) 459–466.

56. Schaback, R., Error Estimates and Condition Numbers for Radial Basis Function Interpolation, Advances in Computational Mathematics 3 (1995), 251–264.

57. Schaback, R., Approximation by Radial Basis Functions with Finitely Many Centers, Constructive Approximation, to appear in Constr. Approx. 1995.

58. Schaback, R., Creating Surfaces from Scattered Data Using Radial Basis Functions, in Mathematical Methods in Computer Aided Geometric Design III, T. Lyche and L.L. Schumaker (ed.), Academic Press, New York, 1995.

59. Schaback, R., Z. Wu, Operators on Radial Functions, Preprint Göttingen 1994.

60. Schechter, M., Complex Interpolation, Compositio Math. 18 (1967), 117–147.

61. Stewart, J., Positive Definite Functions and Generalizations, an Historical Survey, Rocky Mountain J. Math. 6 (1976), 409–434.

62. Sun, X., Conditionally Positive Definite Functions and Their Application to Multivariate Interpolations, J. Approx. Theory 74 (1993), 159–180.

63. Traub, J.F., and H. Woźniakowski, A General Theory of Optimal Algorithms, Academic Press, New York, London, Toronto, Sydney, San Francisco, Elsevier, New York, 1980.

64. Wu, Z., Multivariate Compactly Supported Positive Definite Radial Functions, Preprint, Göttingen, 1994. To appear in AICM.

65. Wu, Z., Characterization of Positive Definite Radial Functions, Preprint, Göttingen, 1994.

66. Wu, Zong-min, R. Schaback, Local Error Estimates for Radial Basis Function Interpolation of Scattered Data, IMA J. Numer. Anal. 13 (1993), 13–27.

Robert Schaback Universität Göttingen, Lotzestraße 16-18, D-37083 Göttingen, Germany

schaback@namu01.gwdg.de