Baltzer Journals December 18, 1995

Optimal Recovery in

Translation–invariant Spaces of Functions

R. Schaback

1Institut für Numerische und Angewandte Mathematik

Universität Göttingen Lotzestr. 16–18 D–37083 Göttingen

             E-mail: schaback@namu01.gwdg.de

Dedicated to Ted Rivlin on the occasion of his 70th birthday

Starting from optimal recovery (in the sense of Micchelli, Rivlin, and Winograd) of functions in reproducing kernel Hilbert spaces from function values at scattered data points, we show that any continuously embedded translation–invariant Hilbert subspace H of L_{2}(IR^{d}) that allows continuous point evaluation is necessarily principal, i.e. it is the native space of a positive definite function Φ. If, in addition, H is invariant under orthogonal transformations of IR^{d}, the function Φ necessarily is a positive definite radial basis function. This serves to show that positive definite radial basis functions and their native spaces arise very naturally and are by no means exotic theoretical constructions.

1 Introduction

Let H be a real Hilbert space of real–valued functions on some domain Ω, and assume that point–evaluation functionals are continuous, which is a very reasonable assumption for applications. Then for any x ∈ Ω there is a Riesz representer λ_{x} ∈ H for the point evaluation functional δ_{x} at x, i.e.

δ_{x}f = f(x) = (λ_{x}, f)_{H}  (1.1)

for all f ∈ H, x ∈ Ω. Now the function

K(x, y) := (λ_{x}, λ_{y})_{H} = λ_{y}(x) = K(y, x)  (1.2)

on Ω × Ω is a reproducing kernel for H, because (1.1) can be rewritten as

f(x) = (K(x, ·), f(·))_{H}  (1.3)

for all x ∈ Ω, f ∈ H. There is a well–established theory of reproducing–kernel Hilbert spaces (see e.g. [2],[12] and applications in [3], [5], [6], and [8]), but we concentrate here on its implications for the theory of multivariate interpolation as an optimal recovery process in the sense of Micchelli, Rivlin, and Winograd.

To this end we additionally assume that any number N of different point evaluation functionals is linearly independent in the dual of H. This has several equivalent formulations, where X = {x_{1}, …, x_{N}} ⊆ Ω always denotes an arbitrary set of N distinct points in Ω:

• The functions λ_{x_{1}}, …, λ_{x_{N}} are linearly independent in H.

• Any interpolation problem on X is uniquely solvable by functions from H.

• The matrix A_{X} = (λ_{x_{j}}, λ_{x_{k}})_{1≤j,k≤N} = (K(x_{j}, x_{k}))_{1≤j,k≤N} is positive definite.

The third version allows to forget about reproducing kernel Hilbert spaces by using the following notion:

Definition .1 A real–valued symmetric function K on Ω×Ω is positive definite, if all matrices of the form

A_{X} = (K(x_{j}, x_{k}))_{1≤j,k≤N}  (1.4)

are positive definite where N and X = {x_{1}, …, x_{N}} ⊆ Ω vary.

In section 3 we shall address the inverse question whether any symmetric positive definite function on Ω×Ω is a kernel function on some Hilbert space H of functions on Ω. See Schoenberg [15] for positive definite functions arising in the problem of isometric embedding of metric spaces into Hilbert spaces.

The problem of optimal recovery of a function f ∈ H from data f(x_{1}), …, f(x_{N}) on some set X = {x_{1}, …, x_{N}} can be rephrased as the minimization problem

∥s∥_{H} = Min! .
s|_{X}= f|_{X}
s ∈ H

By standard arguments the solution s_{f,X} of this problem can be shown to exist uniquely, and to be of the form

s_{f,X} = ∑_{j=1}^{N} a_{j}λ_{x_{j}} = ∑_{j=1}^{N} a_{j}K(x_{j}, ·)  (1.5)

where the coefficents a_{j} are obtained by solving the system

∑_{j=1}^{N} K(x_{j}, x_{k})a_{j} = f(x_{k}),  1 ≤ k ≤ N  (1.6)

with the positive definite matrix A_{X} of (1.4).

For completeness, we add some of the well–known additional properties of this optimal recovery scheme (see [3], [5], [6], and [8], for instance). If x is another point of Ω, one can ask for the best reconstruction of f(x) from known information f(x_{1}), …, f(x_{N}) by linear quasi–interpolation formulas of the form

q_{f}(x) := ∑_{j=1}^{N} f(x_{j}) · u_{j}(x).

where, since x is fixed, we can view u_{j}(x) just as real numbers. The error is representable as

f(x) = (λ_{x} − ∑_{j=1}^{N} u_{j}(x)λ_{x_{j}}, f)_{H}

and has the bound

|f(x) − q_{f}(x)| ≤ ∥f∥_{H} · ∥λ_{x} − ∑_{j=1}^{N} u_{j}(x)λ_{x_{j}} ∥_{H}

which can be optimized by a best approximation of λ_{x} by λ_{x_{1}}, …, λ_{x_{N}}. The unique solution is given by u∗ j (x) satisfying

∑_{j=1}^{N} K(x_{j}, x_{k})u∗ j (x) = K(x, x_{k}), 1 ≤ k ≤ N

and it is evident that u∗ 1 , …, u∗ N , now viewed as functions in H, provide the Lagrange reformulation of the interpolant we already know:

s_{f,X} = ∑_{j=1}^{N} f(x_{j})u∗ j .

Thus the norm–minimal recovery process also minimizes the pointwise error.

In addition, s_{f,X} is the best approximation to f from the span S_{X} of K(x_{1}, ·), …, K(x_{N}, ·), since the representation (1.5) implies

(s_{h,X}, g)_{H} = ∑_{j=1}^{N} a_{j}g(x_{j})

for all g, h ∈ H, and we find

(s_{h,X}, f − s_{f,X})_{H} = 0

for all s_{h,X} ∈ S_{X}.

These three simultaneous optimality properties make interpolation via positive definite functions in the sense of (1.5) a very useful tool for recovery of functions, provided that the system (1.6) can be solved at reasonable computational cost. This occurs if the matrix A_{X} of (1.4) is sparse and well–conditioned (see [13], [14] for overviews), or if special techniques like multipole expansions are applied in order to increase computational efficiency (see [1],[11]).

The next section will demonstrate how certain invariance properties of the Hilbert space H affect the kernel function K, while section 3 will show that any positive definite function K arises as a kernel of some Hilbert space. Finally, in section 4 we specialize to the case of translation–invariant Hilbert subspaces S of L_{2}(IR^{d}) and show that any such space S is a reproducing kernel Hilbert space which can alternatively be written as a space of functions whose L_{2} Fourier transforms are in a weighted L_{2} space. The connection to the general setting is that K(x, y) takes the form K(x, y) = Φ(x − y) for Φ : IR^{d} → IR with Φ(−·) = Φ(·) such that Φ̂ is nonnegative and w = 1/Φ̂ is the weight function in the alternative representation

S = {f ∈ L_{2}(IR^{d}) : ∫ |f̂(ω)|^{2}w(ω)dω < ∞}

that arises in the well–established theory of radial basis functions.

2 Invariance properties

We now assert that any invariance property of H carries over to K. More precisely, let us assume that the space H is invariant under a group T of transformations on the domain Ω, i.e.

(f(T ·), g(T ·))_{H} = (f, g)_{H}

for all T ∈ T , f, g ∈ H, where all T ∈ T are mappings Ω → Ω such that f(T ·) ∈ H for all f ∈ H, T ∈ T . Then we have

λ_{x}(T y) = (λ_{x}, λT y)_{H}
= (λ_{y}, λ_{x}(T ·))_{H}
= (λ_{y}(T^{−1}·), λ_{x})_{H}

for all x, y ∈ Ω, T ∈ T , such that

λ_{T y}(T z) = λ_{y}(z) = K(y, z) = K(T y, T z)  (2.1)

for all y, z ∈ Ω, T ∈ T , proving invariance of K with respect to T . We now consider four important examples.

Example 1 If Ω is itself a real vector space, e.g. Ω = IR^{d}, and if T is the group of all translations T_{x}(z) = z − x, then

K(y, z) = K(y − z, 0)

follows from setting T = T_{z} in (2.1). Then the space S_{X} of functions of the form (1.5) necessarily is a space of translates of the function Φ(·) := K(·, 0). Thus interpolation by translates of a fixed function is a very natural (and in a multiple sense optimal) approach to recovery in the sense of Micchelli, Rivlin, and Winograd of functions in translation–invariant spaces.

Example 2 If, more generally, Ω is a topological group with unity 1, the function K takes the form

K(y, z) = K(y · z^{−1}, 1),

and this approach was treated in detail by Gutzmer [7].

Example 3 If we take Ω = IR^{d} and allow Euclidean rigid–body transformations of the form

T_{Q,x}(y) := Qy − x

where Q is an arbitrary orthogonal d by d matrix, then by suitable choice of Q we get

K(y, z) = K(y − z, 0) = K(∥y − z∥_{2} · e_{1}, 0) =: ϕ(∥y − z∥_{2})  (2.2)

for all y, z ∈ IR^{d}, where e_{1} is the first unit vector and ϕ : IR_{≥0} → IR is a scalar function. Thus the space S_{X} now is generated by translates of a “radial basis function” ϕ.

Example 4 If we work on the sphere Ω = S^{d−1} ⊂ IR^{d} and again allow all orthogonal transformations on IR^{d}, we end up with a kernel of the special form

K(y, z) = ϕ(y^{T} z), y, z ∈ S^{d−1} ⊂ IR^{d}

where ϕ : [−1, +1] → IR is a real–valued function. This special case was treated in Schoenberg [16].

Note that the general definition of positive definiteness of K is applicable in all of these cases. The solution of the system (1.6) will uniquely exist if K is positive definite, and there is no need for any Hilbert space interpretation of K, if one just wants to work with functions of the form (1.5). Thus the construction of “nice” positive definite functions can be carried out independently, and this was actually done in a series of recent papers on the radial case [13], [17], [18].

3 Native spaces

But the construction of a symmetric and positive definite function K will always generate a suitable reproducing–kernel Hilbert space H such that (1.3) holds. This was already done in special situations (see the surveys [13], [14] and their references), but the technique works in general.

If K : Ω × Ω → IR is symmetric and positive definite on some domain Ω, we first define the space

S = {∑_{j=1}^{N} a_{j}K(x_{j}, ·) : a_{j} ∈ IR, N ∈ IN, x_{j} ∈ Ω} .

Any function from S has a unique representation

f_{a,X} = ∑_{j=1}^{N} a_{j}K(x_{j}, ·)  (3.1)

where a = (a_{1}, …, a_{N}) ∈ IR^{N} and X = {x_{1}, …, x_{N}} is a set of N distinct points of Ω. If we define λ_{x} = K(x, ·) and

(λ_{x}, λ_{y})_{S} := K(x, y)

for all x, y ∈ Ω, this definition extends to a scalar product on all of S, because K is positive definite. Then (1.3) holds by definition for all functions of the form (3.1), such that S becomes a reproducing–kernel semi–Hilbert space. Its closure H can be abstractly defined, and if i : S → H is the canonical injection, then for all abstract elements f ∈ H and all points x ∈ Ω one can define a value

f(x) := (iλ_{x}, f)_{S}

that turns f into a function on Ω and H into a reproducing–kernel Hilbert space of functions on Ω having K as its kernel. In this sense one can call H the “native” space for the positive definite symmetric function K. Note that this technique applies to all of the special cases described in Section 2. In particular, the positive definite functions on the topological group SO(3) constructed by Gutzmer [7] generate Hilbert spaces of functions on SO(3) that deserve further study.

The functions f in H will have nice localization properties, if the value f(x) at some x ∈ Ω is independent of values of f at points far from x. From (1.1) we can see that this requires the representer λ_{x} to be locally supported around x, and then (1.2) implies that K(x, y) should be small if x and y are far away from each other. In the Hilbert space dual H′ of H the point evaluation functionals δ_{x} and δ_{y} will then be orthogonal. So far we have left open what “near” means in Ω. The standard example is Ω = IR^{d} with Euclidean distance and Euclidean invariance of H. Then K is radial in the sense of (2.2) and ϕ should be compactly supported around the origin. Examples of such functions, consisting of a single polynomial piece each, were given in [13] and by Wu [18] and Wendland [17].

4 Translation Invariant Native Subspaces of L_{2}(IR^{d})

To be able to apply Fourier transform techniques we now specialize to translation– invariant Hilbert subspaces H of L_{2}(IR^{d}). We assume the embedding A : H → L_{2}(IR^{d}) to be continuous and point evaluation functionals to be linearly independent. Since L_{2}(IR^{d}) itself is translation–invariant, the embedding A and its adjoint A^{∗} are translation–invariant, i.e. they commute with the translation operator

(T_{x}f)(y) := f(y − x), x, y ∈ IR^{d}, f ∈ L_{2}(IR^{d})

written as an operator on H or L_{2}(IR^{d}). This is trivial for A and follows for A^{∗} from

(A^{∗}T_{x}f, T_{x}g)_{H} = (T_{x}f, AT_{x}g)_{L_{2}}
= (T_{x}f, T_{x}Ag)_{L_{2}} = (f, Ag)_{L_{2}}
= (A^{∗}f, g)_{H}  = (T_{x}A^{∗}f, T_{x}g)_{H}

for all g ∈ H, f ∈ L_{2}, x ∈ IR^{d}.

Now for all f ∈ L_{2} and x ∈ IR^{d} we get the representation

(A^{∗}f)(x) = (λ_{x}, A^{∗}f)_{H} = (Aλ_{x}, f)_{L_{2}}
= ∫_{IR^{d}} f(y)λ_{x}(y)dy
= ∫_{IR^{d}} f(y)λ_{0}(y − x)dy
= (f ∗ λ_{0}(−·))(x)

of A^{∗} as a convolution with λ_{0}(−·). By the way, symmetry of K implies λ_{0}(−·) = λ_{0}(·) and λ̂_{0}(·) ∈ IR. Taking Fourier transforms we get

Â^{∗}f = f̂· λ̂_{0}  (4.1)

and the scalar product on H can be rewritten on the subspace A^{∗}(L_{2}) ⊆ H as

\begin{aligned}(A^{∗}f, A^{∗}g)_{H} & = & (f, AA^{∗}g)_{L_{2}} = (f̂, ÂA^{∗}g)_{L_{2}} = (f̂, Â^{∗}g)_{L_{2}} \\ & = & ∫_{IR^{d}} f̂· \overline{ĝ} · λ̂_{0} \end{aligned}

for all f, g ∈ L_{2}(IR^{d}). Since any f ∈ A^{∗}(L_{2}) can be written as f = A^{∗}h_{f} with some h_{f} ∈ L_{2}(IR^{d}),

\begin{aligned}(f, g)_{H} & = & (A^{∗}h_{f}, A^{∗}h_{g})_{H} \\ & = & ∫_{IR^{d}} ĥ_{f} · \overline{ĥ_{g}} · λ̂_{0} \end{aligned}

is a representation of the abstract inner product on H when restricted to the subspace A^{∗}(L_{2}) by an integral over L_{2} functions. Since one can admit any L_{2} function for h_{f} and h_{g}, we get positivity of λ̂_{0}, except for (possibly) a set of measure zero in IR^{d}. Thus we can use (4.1) to write

f̂ = ĥ_{f}λ̂_{0}  (4.2)

for all f ∈ A^{∗}(L_{2}) ⊆ H ⊆ L_{2}, and

(f, g)_{H} = ∫_{IR^{d}} \frac{f̂· \overline{ĝ}}{λ̂_{0}}

for all f, g ∈ A^{∗}(L_{2}). This induces an intermediate Hilbert space

\overline{A^{∗}(L_{2})} = H_{1} = \{f ∈ L_{2}(IR^{d}) : |f̂| \ \sqrt{λ̂_{0}} ∈ L_{2}(IR^{d})\}

between A^{∗}(L_{2}) and H, but since (A^{∗}(L_{2}))^{⊥} = {0} in H we can identify H_{1} and H. This finally proves R. Schaback / Translation–Invariant spaces of functions 9

Theorem .2 Any translation–invariant continuously embedded Hilbert subspace H of L_{2}(IR^{d}) which admits continuous and linear independent point evaluation functionals is the native space of a positive definite L_{2} function Φ : IR^{d} → IR^{d} with Φ(−·) = Φ(·) and can be written as the space

H = \{f ∈ L_{2}(IR^{d}) : ∫ \frac{|f̂(ω)|^{2}}{Φ̂(ω)} dω < ∞\} ,

while Φ̂ is positive almost everywhere. If H is invariant under Euclidean transformations on IR^{d}, then Φ is a radial function.

In view of the definition of principal shift–invariant spaces as in [4] we can interpret Theorem .2 as a general sufficient criterion for translation–invariant subspaces of L_{2}(IR^{d}) to be principal and to be generated by a radial basis function.

References

[1] R.K. Beatson and G.N. Newsam, Fast evaluation of radial basis functions: I. Advances in the theory and applications of radial basis functions. Comput. Math. Appl. 24 (1992), no. 12, 7–19

[2] S. Bergman, The kernel function and conformal mapping, Math. Surveys, 5 (1950), Amer. Math. Soc., New York.

[3] C. de Boor and R.E. Lynch, On splines and their minimum properties, J. Math. Mech. 15 (1966), 953–969.

[4] C. de Boor and A. Ron, Fourier analysis of approximation orders from principal shift– invariant spaces, Constructive Approximation, 8 (1992) 427–462.

[5] N. Dyn, Minimal interpolation and approximation in Hilbert spaces, SIAM J. Numer. Anal. 8 (1971) 585–597.

[6] M. Golomb and H.F. Weinberger, Optimal approximation and error bounds, in On Numerical Approximation, R.F. Langer ed., Univ. of Wisconsin Press, Madison, 1959, pp. 117–190.

[7] T. Gutzmer, Interpolation by positive definite functions on locally compact groups with application to SO(3), to appear in Results in Mathematics.

[8] J. Meinguet, Optimal approximation and error bounds in semi–normed spaces, Numer. Math., 10 (1987), 370–388.

[9] C.A. Micchelli and T.J. Rivlin, A survey of optimal recovery, in Optimal Estimation in Approximation Theory, C.A. Micchelli and T.J. Rivlin eds., Plenum Press, 1977, pp. 1–54.

[10] C.A. Micchelli, T.J. Rivlin and S. Winograd, Optimal recovery of smooth functions, Numer. Math., 260 (1976) 191–200.

[11] M.J.D. Powell, Truncated Laurent expansions for the fast evaluation of thin plate splines. Algorithms for Approximation, III (Oxford, 1992). Numer. Algorithms 5 (1993), no. 1–4, 99–120.

[12] S. Saito, Theory of reproducing kernels and its applications, Pitman Research Notes 189, Longman: Harlow 1988

[13] R. Schaback, Creating surfaces from scattered data using radial basis functions, in Mathe-

R. Schaback / Translation–Invariant spaces of functions 10

matical Methods for Curves and Surfaces, M. Daehlen, T. Lyche and L.L. Schumaker eds., Vanderbilt University Press, Nashville, TN, 1995, 477–496.

[14] R. Schaback, Multivariate interpolation and approximation by translates of a basis function, to appear in: Approximation Theory VIII, Charles K. Chui and L.L. Schumaker eds., World Scientific Publishing Co., Inc.

[15] I.J. Schoenberg, Metric spaces and positive definite functions, Trans. Amer. Math. Soc., 44 (1938) 522–536.

[16] I.J. Schoenberg, Positive definite functions on spheres, Duke Math. J., 9 (1942), 96–108.

[17] H. Wendland, Piecewise polynomial, positive definite, and compactly supported radial functions of minimal degree, Preprint, University of Göttingen, 1995.

[18] Z. Wu, Multivariate compactly supported positive definite radial functions, Preprint, University of Göttingen, 1994. To Appear in AICM.