Characterization of Function Spaces associated to Conditionally Positive Definite Functions

Armin Iske

Abstract. We give a unified theory that yields three characterizations for the native function spaces associated to conditionally positive definite functions on an open subset Ω of the d dimensional Euclidean space. As a byproduct, we completely describe the dependence of the spaces on Ω.

§1. Introduction

Let Ω ⊂ IR^{d} be an open subset of the d–dimensional Euclidean space. We assert to interpolate function values f(x_{j}) ∈ IR of a function f ∈ C(Ω) at scattered data locations x_{j} ∈ X ⊂ Ω by an interpolant s_{f} : Ω → IR of the form

s_{f}(x) = ∑_{j∈J} c_{j}ψ(x − x_{j}) + p(x)  (1)

where p is in the space P_{m}^{d} of all polynomials with d variables of order m or less and ψ : IR^{d} → IR with ψ(· − x_{j}) ∈ C(Ω) for all j ∈ J, is called basis function. Due to C. A. Micchelli’s fundamental paper [7], for a finite set X = {x_{1}, …, x_{N}} ⊂ Ω of pairwise distinct points with

p(x_{j}) = 0 (1 ≤ j ≤ N)  ⟹  p ≡ 0 for all p ∈ P_{m}^{d}

the above interpolation problem has a unique solution under the constraints

∑_{j=1}^{N} c_{j}p(x_{j}) = 0  for all p ∈ P_{m}^{d}  (2)

provided that ψ is conditionally positive definite of order m on Ω:

Mathematical Methods in CAGD III 1 M. Dæhlen, T. Lyche, and L. L. Schumaker (eds.), pp. 1–6. Copyright o^{c} 1995 by xxx ISBN xxx. All rights of reproduction in any form reserved.

Definition 1.1. A function ψ ∈ C(IR^{d}) is conditionally positive definite of order m on Ω if the quadratic form

∑_{j,k=1}^{N} c_{j}c_{k}ψ(x_{j} − x_{k})  (3)

is positive for all sets X = {x_{1}, …, x_{N}} ⊂ Ω of N pairwise distinct points and for all vectors c = (c_{1}, …, c_{N})^{T} ∈ IR^{N} \{0} satisfying (2).

For scattered data interpolation on Ω as defined above, the conditional positive definiteness of ψ is sufficient for existence of a solution. From now on we assume ψ to be conditionally positive definite of order m on Ω. The interpolants of the form (1) subject to the condition (2) certainly form a linear space F_{ψ}(Ω) depending on ψ and Ω. This space so far has no topology. If it is contained in some larger normed space F of d-variate functions, for example Sobolew space W_{ℓ}^{n}(Ω), it would be interesting to calculate the F-closure of F_{ψ}(Ω). This would help to find error bounds for interpolants or approximants to functions f from F by functions in F_{ψ}(Ω).

However, there is no such theory so far. Instead of imposing an “artificial” topology from a larger space F to F_{ψ}(Ω), one can ask for more natural topologies on F_{ψ}(Ω) that are directly related to the representation (1). Such a topology actually exists for Ω = IR^{d}, dating back to early papers of Madych and Nelson [4,5,6] and conveniently described in [8]. In short, it uses (3) to define

|s_{f}|^{2} := ∑_{j,k=1}^{N} c_{j}c_{k}ψ(x_{j} − x_{k})  (4)

as a seminorm on functions of the form (1). Such a seminorm arises straightforwardly from a bilinear form, and one can take a Hilbert space closure to generate an appropriate function space F_{ψ}(Ω). This has been done by various authors [1,2,4,5,6,8,9] in different ways, using three basic techniques:

1. variational inequalities,

2. generalized convolutions,

3. generalized Fourier transforms. This paper serves to give a unified theory and to show that these approaches are equivalent.

Up to now, the dependence of the spaces F_{ψ}(Ω) on Ω is not fully understood. Most authors use Ω = IR^{d} throughout, but we strictly assume a general nonempty bounded set Ω ⊆ IR^{d}, having bounded domains in mind. However, our characterization results will reveal that

F_{ψ}(Ω) = F_{ψ}(IR^{d}) |_{Ω},  (5)

proving that each function f ∈ F_{ψ}(Ω) can be extended to a function in F_{ψ}(IR^{d}).

§2. Test Functions

We now add some more notation. To each function s_{f} of (1) there can be associated a linear functional

λ(h) := ∑_{j=1}^{N} c_{j}h(x_{j})

on C(Ω) which is finitely supported and annihilates P_{m}^{d} due to (2). Then

< λ, μ >:= μ^{x}λ^{y}ψ(x − y),  (6)

where μ^{x} denotes action of μ with respect to x, is a scalar product on all such functionals, and for f_{λ}(x) := λ^{y}ψ(x − y) we see that < f_{λ}, f_{μ} >:= < λ, μ > is the bilinear form behind (4). Let

S := {v ∈ C^{∞}(IR^{d}) : lim_{∥x∥→∞} |x^{α}D^{β}v(x)| = 0 for all α, β ∈ IN_{0}^{d}}

be the Schwartz space of tempered test functions. We now introduce a topology on its subset S(Ω) := {v ∈ S : supp v ⊂ Ω} ⊂ S that corresponds to the one we have been considering up to now. By λ_{v}(f) := (f, v)_{L_{2}(Ω)} each v ∈ S(Ω) induces a functional on the space

K(Ω) := {f : Ω → IR : ∃M ∈ IN_{0} with f(x)/(1 + ∥x∥)^{M} ∈ L_{1}(Ω)}

of all locally integrable functions that have at most polynomial growth on Ω. Based on (6) we define the bilinear form

(v, w)_{ψ} := λ_{w}^{x}λ_{v}^{y}ψ(x − y)  (7)

for all v, w from

S_{m}^{⊥}(Ω) := {v ∈ S(Ω) : λ_{v}(p) = 0 for all p ∈ P_{m}^{d}} ⊂ S(Ω).

To be able to do this, we only require ψ(x − ·), ψ(· − y) ∈ K(Ω) for each x, y ∈ Ω. But in order to prove that ∥ · ∥_{ψ} := \sqrt{(·, ·)_{ψ}} provides a norm on S_{m}^{⊥}(Ω) we need some additional assumption on ψ. Following Madych and Nelson [4] and other authors using generalized Fourier transforms, we assume a continuous and positive function φ : IR^{d} \{0} → IR to exist such that the representation

(v, w)_{ψ} = (2π)^{−d} ∫_{IR_{d}} φ(ω)v̂(ω)\overline{ŵ(ω)} dω =: (v̂, ŵ)_{φ}  (8)

holds for all v, w ∈ S_{m}^{⊥}(Ω). Here,

v̂(ω) := ∫_{Ω} e^{−ix^{T} ω}v(x) dx

denotes the classical Fourier transform of v.

For the special case Ω = IR^{d}, many standard basis functions ψ allow such a φ, but there are some examples (for instance even-order tensor-product Bsplines) that induce unwanted zeros of φ. But if we assume φ to be positive, the bilinear form (7) will clearly be positive definite. This is a slightly stronger assumption than conditional positive definiteness of ψ on IR^{d}, because in his dissertation [3] the author proves that conditionally positive definite functions ψ on IR^{d} possess a nonnegative but nonvanishing generalized Fourier transform φ in the sense of (8).

§3. Characterizations of F_{ψ}(Ω)

In this section we establish characterizations of the function space

F_{ψ}(Ω) := {f ∈ K(Ω) : ∃C_{f} ∈ IR_{≥0} with|λ_{v}(f)| ≤ C_{f}∥v∥_{ψ} for all v ∈ S_{m}^{⊥}(Ω)} .

Note that this definition of F_{ψ}(Ω), which occurs in [1], [4–6] in similar form, is nothing but a characterization of functions via a variational inequality:

Theorem 3.1. A function f : Ω → IR which is locally integrable and of at most polynomial growth on Ω, is in F_{ψ}(Ω) iff it satisfies

| ∫_{Ω} f(x)v(x) dx| ≤ C_{f} ∫_{Ω} ∫_{Ω} ψ(x − y)v(x)v(y) dx dy for all v ∈ S_{m}^{⊥}(Ω)

for some C_{f} ≥ 0.

Remarks: It is allowed to replace S_{m}^{⊥}(Ω) in the definition of F_{ψ}(Ω) by \overline{S_{m}^{⊥}(Ω)} because of continuity with respect to the norm ∥ · ∥_{ψ}. Doing this in Theorem 3.1 would imply a distributional interpretation of the variational inequality. Since K(IR^{d}) |_{Ω}= K(Ω) and S_{m}^{⊥}(Ω) ⊆ S_{m}^{⊥}(IR^{d}) we get F_{ψ}(IR^{d}) |_{Ω}⊆ F_{ψ}(Ω) as part of (5).

For all f ∈ F_{ψ}(Ω) we can define a linear functional v ↦ λ_{v}(f) on \overline{S_{m}^{⊥}(Ω)}. By the theorem of Fischer-Riesz there is a unique v_{f} ∈ \overline{S_{m}^{⊥}(Ω)} such that λ_{v}(f) = (v_{f}, v)_{ψ} for all v ∈ \overline{S_{m}^{⊥}(Ω)}. Now Λ : F_{ψ}(Ω) → \overline{S_{m}^{⊥}(Ω)} with Λ(f) = v_{f} is a linear mapping with

P_{m}^{d}(Ω) := {f : Ω → IR : ∃p ∈ P_{m}^{d} with f ≡ p|_{Ω}} ⊂ kerΛ.

The other inclusion follows from [5], Lemma 3.2. We now show surjectivity of Λ. Choosing an arbitrary w ∈ S_{m}^{⊥}(Ω) we consider the function f_{w} := ψ ∗ w. Using

|λ_{v}(f_{w})| = |λ_{v}(ψ ∗ w)| = |λ_{v}^{x}λ_{w}^{y}ψ(x − y)| = | (w, v)_{ψ} | ≤ ∥w∥_{ψ} · ∥v∥_{ψ} (9)

for all v, w ∈ S_{m}^{⊥}(Ω) we realize that f_{w} coincides on Ω with a function f_{w,Ω} which is in F_{ψ}(Ω) by definition. We have a linear map V : S_{m}^{⊥}(Ω) → F_{ψ}(Ω) with V (w) = f_{w,Ω} and λ_{v}(V (w)) = λ_{v}^{x}λ_{w}^{y}ψ(x − y) = (w, v)_{ψ} for all v, w ∈ S_{m}^{⊥}(Ω), and this generalizes to \overline{S_{m}^{⊥}(Ω)} by (9) and continuity. Note that both V and Λ are isometric, if a suitable norm is defined in F_{ψ}(Ω).

Checking Λ ∘ V we find that

((Λ ∘ V)(w), v)_{ψ} = λ_{v}(V (w)) = (w, v)_{ψ}

for all v, w ∈ \overline{S_{m}^{⊥}(Ω)}, implying that Λ ∘ V is the identity on \overline{S_{m}^{⊥}(Ω)} and Λ is surjective. This yields \overline{S_{m}^{⊥}(Ω)} ≅ F_{ψ}(Ω)/kerΛ = F_{ψ}(Ω)/P_{m}^{d}(Ω) and a characterization of F_{ψ}(Ω) via generalized convolution:

Theorem 3.2. (cf. [2])

F_{ψ}(Ω) = P_{m}^{d}(Ω) ⨁ V (\overline{S_{m}^{⊥}(Ω)}).  (10)

In particular, F_{ψ}(Ω) consists of P_{m}^{d}(Ω) plus all functions f_{w,Ω} generated by limits of convolutions

(ψ ∗ w_{n})(x) = ∫_{Ω} ψ(x − y)w_{n}(y) dy

for w_{n} ∈ S_{m}^{⊥}(Ω) under convergence in ∥ · ∥_{ψ}.

Note that (10) immediately implies F_{ψ}(Ω) ⊆ F_{ψ}(IR^{d}) |_{Ω′} proving (5). Except for our motivation of the introduction of φ, we did not use Fourier transforms so far. But from (10) we can write any f_{Ω} ∈ F_{ψ}(Ω) as f_{Ω} = p_{Ω} + f_{w,Ω} with p_{Ω} ∈ P_{m}^{d}(Ω) and f_{w,Ω} = V (w) for w ∈ \overline{S_{m}^{⊥}(Ω)}, and extend it canonically to a function f = p + ψ ∗ w : IR^{d} → IR. Now we can take distributional Fourier transforms of both p and f_{w} = ψ ∗ w. The latter is treated by

F (f_{w}) = F (ψ ∗ w) = F (ψ) · ŵ = φ · ŵ

for w ∈ S_{m}^{⊥}(Ω), where F denotes the distributional Fourier transform. For w ∈ \overline{S_{m}^{⊥}(Ω)} we can only resort to the distributional interpretation

λv̂(F (f_{w})) := λ_{v}(f_{w}) = λ_{v}^{x}λ_{w}^{y}ψ(x − y) = (w, v)_{ψ} = (ŵ, v̂)_{φ}

for all v ∈ \overline{S_{m}^{⊥}(Ω)}. Here, we tacitly extended the Fourier transform to \overline{S_{m}^{⊥}(Ω)} by continuity. If we interpret this in L_{2}(IR^{d}), we find that by

(φ · ŵ)(v̂) := (ŵ, v̂)_{φ} for all v ∈ \overline{S_{m}^{⊥}(Ω)}

the identity F (f_{w}) = φ·ŵ holds as an identity of functionals. If understood in a generalized sense, we have the third characterization of functions in F_{ψ}(Ω):

Theorem 3.3. (cf. [1,4,6]) The space F_{ψ}(Ω) consists of polynomials from P_{m}^{d}(Ω) plus functions from K(Ω) which are restrictions to Ω of functions defined on IR^{d} whose generalized Fourier transforms are a product of φ with a function in the weighted L_{2} space

L_{φ}^{2} := {f : IR^{d} → IR : ∫_{IR_{d}} |f(ω)|^{2}φ(ω) dω < ∞} .

Acknowledgements. The author is greatly indebted to Prof. R. Schaback for several fruitful discussions and his help with the presentation of this paper.

References

1. Dyn, N., Interpolation of Scattered Data by Radial Functions, in Topics in Multivariate Approximation, C. K. Chui, L. L. Schumaker and F. I. Utreras (eds.), Academic Press, New York, 1987, 47–61.

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

3. Iske, A., Charakterisierung bedingt positiv definiter Funktionen für multivariate Interpolationsmethoden mit radialen Basisfunktionen, Dissertation, Universität Göttingen, 1994.

4. Madych, W. R. and S. A. Nelson, Multivariate interpolation: a variational theory, preprint, 1983.

5. Madych, W. R. and S. A. Nelson, Multivariate Interpolation and Conditionally Positive definite Functions, Approx. Th. Appl. 4.4, 1988, 77–89.

6. Madych, W. R. and S. A. Nelson, Multivariate Interpolation and Conditionally Positive definite Functions II, Math. Comp. 54, 1990, 211–230.

7. Micchelli, C. A., Interpolation of Scattered Data: Distance Matrices and Conditionally positive definite Functions, Constr. Approx. 2, 1986, 11–22.

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

9. Wu, Z. and R. Schaback, Local error estimates for radial basis function interpolation, IMA Journal of Numerical Analysis 13, 1993, 13–27.

Armin Iske Institut für Numerische und Angewandte Mathematik Universität Göttingen Lotzestraße 16-18 D-37083 Göttingen Germany iske@namu01.gwdg.de