On Compactly Supported, Positive Definite, Radial Basis Functions

S.J. Hales and J. Levesley

September 6, 2000

Abstract The space dimension in which a radial function ϕ is positive definite is characterised by conditions on ϕ̂(\sqrt{w}). These can be seen as a natural generalisation of the result of Schoenburg [4]. A relationship is given between the smoothness of compactly supported radial functions and the space dimension wherein they are positive definite.

1 Introduction

Compactly supported positive definite radial functions have become popular computational tools because the interpolation matrices which arise from their use are sparse. There now exist a number of different families of such functions, see [2, 5, 8], and these functions share some common features. The purpose of this paper is to find ways of identifying the space dimension in which a compactly supported function is positive definite.

To discuss these issues we will need to introduce some notation and terminology. We will assume that all univariate functions referred to in this paper are defined on [0, ∞). Let CS denote the set of compactly supported functions in one dimension. For our purposes we can assume that all such functions are supported in [0, 1]. Let C^{k} denote the set of functions defined on [0, ∞) which have k continuous derivatives, and k zero derivatives at the origin, and C = C^{0} denote the continuous functions.

Let ϕ ∈ C^{l}(x_{0}) mean that ϕ has l continuous derivatives in the neighbourhood of x_{0}. For compactly supported functions we let ϕ^{(j)}(1) denote the limit of ϕ^{(j)}(t) as t tends to 1 from below.

Definition 1 A function ϕ is positive definite in d–dimensions, written PD_{d}, if

F_{d}ϕ = ∫_{IR_{d}} ϕ(∥x∥) exp(iwx)dx > 0 for all w ∈ IR^{d}.

We will denote the one dimensional Fourier transform F_{1}ϕ by ϕ̂.

There exist functions which are positive definite in all space dimensions, for example,

(i) ϕ(r) = exp(−cr^{2}) (Gaussian),
(ii) ϕ(r) = (c^{2} + r^{2})^{− \frac{1}{2}} (inverse multiquadric).

Here c is a positive constant shape parameter.

By virtue of Bochner’s theorem [1], any function ϕ ∈ PD_{∞} has the Fourier–Stieltjes integral representation

ϕ(r) = ∫_{−∞}^{+∞} exp(iru)dα(u),  (1)

where α(u) is a non decreasing, bounded measure.

It has been proved by Schoenberg [4] that the existence of such an integral is equivalent to certain conditions on the behaviour of the function f(r) = ϕ(\sqrt{r}).

Definition 2 A function f is completely monotone on [0, a) for a > 0, written f ∈ CM[0, a), if

(i) f ∈ C[0, a),

(ii) f ∈ C^{∞}(0, a),
(iii) (−1)^{k}f^{(k)}(r) ≥ 0 for 0 < r < a and k = 0, 1, 2, . . ..

The Bernstein–Widder Theorem [7] shows that any function f ∈ CM[0, ∞) has the Laplace–Stieltjes integral representation

f(r) = ∫_{0}^{∞} exp(−ru)dβ(u),  (2)

where β(u) is a nondecreasing, bounded measure. In [4] the following result is proved.

Theorem 1 ϕ(\sqrt{r}) ∈CM[0, ∞) if and only if ϕ(r) ∈ PD_{∞}.

It is clear that a compactly supported basis function can not be in PD_{∞}. However there may be in PD_{d} for some d < ∞. There exist numerous methods for generating functions ϕ ∈ CS∩PD_{d}, see Buhmann [2], Wendland [5] & Wu [8].

In order to examine the polynomials of Wendland and Wu, consider the following operators D and I,

Df(r) = −\frac{1}{r} \frac{d}{dr}f(r),
If(r) = ∫_{r}^{∞} rf(r)dr.

Wendland [6] summarises the connections between I, D, and F_{d} nicely and we quote this summary in

Proposition 1

(i) The operators I and D are inverse: If ϕ is continuous and satisfies tϕ(t) ∈ L_{1}, then DIϕ = ϕ. On the other hand, if ϕ ∈ C^{2} is even and satisfies ϕ′ ∈ L_{1}, then IDϕ = ϕ.

(ii) If ϕ(t)t^{d−1} ∈ L_{1} and d ≥ 3, then F_{d}(ϕ) = F_{d−2}(Iϕ).

(iii) If ϕ ∈ C^{2} and ϕ(t)t^{d−1} ∈ L_{1}, then F_{d}(ϕ) = F_{d+2}(Dϕ).

To prove our results we require the following

Proposition 2 If ϕ ∈ C and t^{2}ϕ(t) ∈ L_{1} then (Iϕ)^{∧} = Dϕ̂.

Proof: If ϕ ∈ C and t^{2}ϕ(t) ∈ L_{1} then

∫_{0}^{∞} |Iϕ(r)| dr = ∫_{0}^{∞} |∫_{r}^{∞} tϕ(t) dt| dr
= lim_{M→∞} ∫_{0}^{M} |∫_{r}^{M} tϕ(t) dt| dr

+ lim_{M→∞} ∫_{0}^{M} |∫_{M}^{∞} tϕ(t) dt| dr

≤ lim_{M→∞} ∫_{0}^{M} {∫_{0}^{t} dr} t|ϕ(t)| dt

+ lim_{M→∞} ∫_{0}^{M} |∫_{M}^{∞} t|ϕ(t)| dt| dr

= lim_{M→∞} ∫_{0}^{M} t^{2}|ϕ(t)| dt

+ lim_{M→∞} M ∫_{M}^{∞} t|ϕ(t)| dt

≤ lim_{M→∞} {∫_{0}^{M} t^{2}|ϕ(t)| dt + ∫_{M}^{∞} t^{2}|ϕ(t)| dt}
= ∫_{0}^{∞} t^{2}|ϕ(t)| dt < ∞,

so that Iϕ ∈ L_{1}. Taking the Fourier transform of Iϕ we have

(Iϕ)^{∧}(w) = ∫_{0}^{∞} {∫_{r}^{∞} tϕ(t) dt} cos(wr) dr
= ∫_{0}^{∞} tϕ(t) {∫_{0}^{t} cos(wr) dr} dt
= \frac{1}{w} ∫_{0}^{∞} tϕ(t) sin(wt) dt
= −\frac{1}{w} \frac{d}{dw} ∫_{0}^{∞} ϕ(t) cos(wt) dt
= Dϕ̂(w).

The change of order of integration is justified by using exactly the same style of argument as in proving that Iϕ ∈ L_{1}.

Remarks 1 We comment here that under more restrictive conditions (Dϕ)^{∧} = Iϕ̂. However, we do not require this result in this paper.

In [5] Wendland starts with C ∩ PD_{2l−1} polynomials created by the product of PD_{1} polynomials thus,

ϕWe_{l} = (1 − r)_{+}^{l},

where

(t)_{+} = \{ \begin{matrix}0, & t < 0, \\ t, & t ≥ 0. \end{matrix}

Using Proposition 1 (ii), dimensions of positive definiteness are traded for increased smoothness by the I operator,

ϕWe_{l,k} = I^{k}(1 − r)_{+}^{l}.  (3)

In [8] Wu starts with smooth PD_{1} polynomials created by the convolution of (1 − r^{2})_{+}^{l} with itself,

ϕWu_{l} = (1 − r^{2})_{+}^{l} ∗ (1 − r^{2})_{+}^{l}.

Continuous derivatives of ϕ_{l}^{W u} are exchanged for higher dimensions of positive definiteness by using the D operator (see Proposition 1 (iii)),

ϕ_{l,k}^{W u} = D^{k}ϕ_{l}^{W u}.

In [2] Buhmann seeks to find functions of the form

ϕ^{Bu} = p(r) + q(r^{2}) log(r),

where p and q are polynomials. Positive definiteness is guaranteed by the Fourier transform [ϕ^{Bu}]^{∧} reducing to an integral of a Bessel function which is known to be positive.

Examination of ϕ^{We}, ϕ^{Wu}, and ϕ^{Bu} reveals that they all have the property that ϕ(\sqrt{r}) ∈ CM[0, 1). An interesting problem is whether or not all PD_{d} functions have a monotonicity condition reminiscent of the Schoenberg result for PD_{∞}. We will answer this question in the negative in the next section by showing that there are non positive positive definite functions. We will, however, recast Schoenberg’s characterisation of positive definite functions in terms of Fourier transforms and show that the dimension in which a function is positive definite may be characterised using Fourier transforms.

We also see with some inspection that for ϕ = We, ϕ = Wu, or ϕ = Bu, if ϕ ∈ CS ∩ C^{2k}(0) ∩ C^{l}(1) then ϕ ∈ PD_{2(l−2k)+1}. In [6] Wendland shows that this is the maximum dimension in which ϕ can be positive definite, if ϕ is a polynomial. In Section 3 we reproduce the result of Wendland without the polynomial restriction, and, using a counterexample, show that there are functions in ϕ ∈ CS ∩ C^{0}(0) ∩ C^{1}(1) which are in PD_{1} but not in PD_{3}.

2 Fourier transform characterisation of dimension of positive definiteness

We begin the section by showing that there are non positive positive definite functions in all space dimensions. To do this we will use Green’s theorem in the form Proposition 3 Let S be the boundary of the bounded set B. Let f, g ∈ C^{2}(IR^{d}).Then

∫_{B}(fΔg − gΔf) dx = ∫_{S} (f \frac{dg}{dn} − g \frac{df}{dn}) dS,

where d/ dn denotes differentiation in the direction of the normal pointing out of the surface S.

Theorem 2 Let f ∈ C^{2} be compactly supported and positive definite. Then −Δf is also positive definite and compactly supported.

Proof: Assume without loss of generality that f has support strictly contained inside the unit ball. We will use Green’s theorem with g(x) = e^{−iyx}, B the unit ball in IR^{d} and S the unit sphere in IR^{d}. Then, \frac{dg}{dn} and g are zero on S, and we see that

F_{d}[Δf](y) = ∫_{IR_{d}} Δf(x)e^{−ixy} dx
= ∫_{B} Δf(x)e^{−ixy} dx
= ∫_{B} f(x)Δ_{x}e^{−ixy} dx
= −∥y∥^{2}F_{d}f(y) < 0.

Example 1

In one dimension it is now easy to construct a non positive positive definite function by differentiating twice. Because ϕ^{Wu} and ϕ^{We} have a zero derivative at the origin (unless they are in C^{0}(0)) and a zero derivative at 1 it must be that these functions have negative second derivative at the origin and positive second derivative at 1. Thus, the second derivative of both these families of functions are neither positive or negative, but their negatives are positive definite.

Example 2

In d dimensions, for radial functions, the Laplacian has the form

Δϕ = \frac{d^{2}ϕ}{dr^{2}} + \frac{d − 1}{r} \frac{dϕ}{dr}.

In [5] we see that ϕ(r) = (1 − r)^{d}(dr + 1) ∈ PD_{d} if d ≥ 3 is odd. For this choice of ϕ,

\frac{d^{2}ϕ}{dr^{2}} + \frac{d − 1}{r} \frac{dϕ}{dr} = (1 − r)^{d−2}d(d + 1)(2dr − d − r),

which is positive if d/(2d − 1) < r < 1 and negative if 0 ≤ r < d/(2d − 1), giving examples of non positive positive definite functions in arbitrary space dimension.

The two previous examples tell us that there is no analogue to Theorem 1 characterising positive definiteness by the bahaviour of the function and its derivatives. However, as we see in the rest of this section, the dimension in which a function is positive definite can be characterised by the behaviour of its univariate Fourier transform.

In [8] Wu notes that if ψ(r^{2}) = ϕ(r) then

\frac{dψ}{dr} = \frac{1}{2r} \frac{dϕ}{dr}
= −\frac{Dϕ}{2}.

Therefore, ψ is completely monotone if and only if ϕ > 0 and D^{k}ϕ > 0 for all k ∈ IN.

We now characterise the dimension of positive definiteness in terms of the Fourier transform:

Theorem 3 Fix k ∈ IN and suppose t^{l}ϕ(t) ∈ L_{1} for all 0 ≤ l ≤ 2k. Then ϕ ∈ PD_{2k+1} if and only if D^{j}ϕ̂ > 0 for all 0 ≤ j ≤ k.

Proof: Using Proposition 1 (ii) we have ϕ ∈ PD_{2k+1} if and only if I^{k}ϕ ∈ PD_{1}. Now applying Proposition 2 k times we have ϕ ∈ PD_{2k+1} if and only if D^{j}ϕ̂ > 0 for all 0 ≤ j ≤ k.

It is now simple to recast Theorem 1 in terms of Fourier transforms:

Corollary 1 Suppose t^{l}ϕ(t) ∈ L_{1} for all l ∈ IN ∪ {0}. Then ϕ ∈ PD_{∞} if and only if D^{j}ϕ̂ > 0 for all j ∈ IN ∪ {0}. Alternatively ϕ ∈ PD_{∞} if and only if, if ψ(r^{2}) = ϕ̂(r), ψ ∈ CM[0, ∞).

3 Smoothness of compactly supported basis functions

In this section we extend the results of Wendland [6] to include non polynomials. We will show that if for some d, ϕ ∈ CS∩C^{2k}(0)∩C^{l}(1)∩PD_{d} then d ≤ 2(l − 2k) + 1. The functions ϕ^{We}, ϕ^{Wu}, and ϕ^{Bu} all satisfy ϕ ∈ PD_{2(l−2k)+1}. We also show that the smoothness conditions at the origin and cut off do not determine the dimension of positive definiteness of compactly supported functions, i.e. there exist functions such that ϕ ∈ CS ∩ C^{2k}(0) ∩ C^{l}(1) ∩ PD_{d} then d < 2(l − 2k) + 1.

The following lemmas are required.

Lemma 1 If a CS function ϕ(r) has a simple jump–discontinuity at r = 1, then ϕ(r) is not positive definite in any dimension.

Proof It is only necessary to show that that ϕ ∉ PD_{1}, that is ϕ̂(w) < 0 for some w. Assume ϕ ∈ PD_{1}, and seek a contradiction. Due to the jump– discontinuity, ϕ can be written as

ϕ(r) = a(r) + f(r),

where a(r) is a step function of value ϕ(1), and f is a continuous CS function. Then

ϕ̂(w) = \frac{ϕ(1)}{w} sin(w) + f̂(w).

Now f̂ exists because ϕ is assumed to be in PD_{1}, so there exists a constant c such that |f̂| ≤ c/w^{2}, see Morrison [3]. Therefore ϕ̂ cannot be one–signed, leading to a contradiction. Since ϕ ∉ PD_{1}, then ϕ cannot be positive definite in any dimension.

Lemma 2 If ϕ ∈ CS ∩ C^{2k}(0) ∩ C^{l}(1) ∩ C^{l+1}(0, 1) with 2k > l ≥ 1 and l is odd, then ϕ cannot be positive definite in any dimension.

Proof: As in Lemma 1 it is only necessary to show that that ϕ ∉ PD_{1}, that is ϕ̂ is not one–signed. Since ϕ is a compactly supported radial function,

ϕ̂(w) = ∫_{0}^{1} cos(wr)ϕ(r)dr.

Integration by parts twice gives

ϕ̂(w) = \frac{sin(w)ϕ(1)}{w} + \frac{cos(w)ϕ′(1)}{w^{2}} − \frac{ϕ′(0)}{w^{2}} − \frac{[ϕ′′(r)]^{∧}}{w^{2}} .

But ϕ is at least twice continuously differentiable, so ϕ(1) = 0, ϕ′(1) = 0, ϕ′′(1) = 0, and ϕ′(0) = 0. Therefore

ϕ̂(w) = −\frac{1}{w^{2}} [ϕ′′]^{∧},

and ϕ′′ is continuous. Repeating this process yields,

ϕ̂(w) = \frac{(−1)^{j}}{w^{2j}} [ϕ^{(2j)}]^{∧},

for j = 1, 2, …, \frac{l−1}{2}, where ϕ^{(2j)} is a continuous function on [0, 1]. When j = \frac{l+1}{2} for odd l , ϕ^{(2j)}(r) is discontinuous at r = 1, and so from Lemma 1, ϕ̂ cannot be one–signed. Therefore ϕ is not positive definite in any dimension.

It is necessary to see how the action of D on ϕ affects the smoothness of the function around zero and the cut–off.

Lemma 3 If ϕ ∈ CS ∩ C^{2k}(0) ∩ C^{l}(1) ∩ PD_{d}, then Dϕ ∈ CS ∩ C^{2k−2}(0) ∩ C^{l−1}(1) ∩ PD_{d+2}.

Proof: The increase in dimension of positive definiteness comes directly from Proposition 1 (iii). Now let ψ = Dϕ which implies that

rψ(r) = −\frac{d}{dr}ϕ(r).

So using Leibnitz rule,

−ϕ^{(j)} = (j − 1)ψ^{(j−2)}(r) + rψ^{(j−1)}(r) for j = 1, 2, 3, ….

Thus

ϕ^{(j)}(0) = 0 ⇔ ψ^{(j−2)}(0) = 0.

So if ϕ ∈ C^{2k}(0), then ψ = Dϕ ∈ C^{2k−2}(0).

Now ϕ ∈ C^{l}(1) so

ϕ^{(j)}(1) = (j − 1)ψ^{(j−2)}(1) + ψ^{(j−1)}(1) = 0 for j = 1, 2, …, l,

and ϕ^{(l+1)}(1) = lψ^{(l−1)}(1) + ψ^{(l)}(1) ≠ 0.

Therefore ψ^{(j)}(1) = 0 for j = 1, 2, …, l − 1, and ψ^{(l)}(1) ≠ 0, which implies that

ψ = Dϕ ∈ C^{l−1}(1).

Lemma 3 can be easily rewritten for the I operator given that if ϕ ∈ C^{2k} then D^{k}I^{k}ϕ = I^{k}D^{k}ϕ = ϕ.

Lemma 4 If ψ ∈ C^{2k}(0) ∩ C^{2k}(1) then ψ can be at most in PD_{1}. Further, if φ ∈ C^{0}(0) ∩ C^{k}(1) then φ can be at most in PD_{2k+1}.

Proof: Assume ψ ∈ CS ∩ C^{2k}(0) ∩ C^{2k}(1) ∩ PD_{d} for d ≥ 3, and seek a contradiction. From Proposition 1 (iii), there exists a function ϕ ∈ PD_{d−2} such that ψ = Dϕ. This means that ϕ ∈ C^{2k+2}(0) ∩ C^{2k+1}(1) and must be at least |P D_{1}; see Lemma 3. A contradiction arises from Lemma 2 which states that such a function which is smoother around the origin than at the cut–off cannot be positive definite in any dimension. Proof of the second assertion follows by defining φ = D^{k}ψ in conjunction with Lemma 3.

Theorem 4 (main) If ψ ∈ CS∩C^{2k}(0)∩C^{l}(1)∩PD_{d} then d ≤ 2(l−2k)+1.

Proof: Consider ψ ∈ C^{2k}(0) ∩ C^{l}(1), then φ = D^{k}ψ ∈ C^{0}(0) ∩ C^{l−k}(1), which Lemma 4 states is at most PD_{2(l−k)+1}. From Proposition 1 (ii) ψ is at most PD_{2(l−2k)+1}.

We complete this section with an example of a function ψ ∈ C^{0}(0) ∩ C^{1}(1)∩PD_{1} which is not in PD_{3}, the dimension predicted by the smoothness at the origin and the cut-off.

Example 3

Let ϕ = (1 − r)^{2}(1 + r). Then,

ϕ̂(w) = \frac{6(1 − cos w) + w^{2} − 4w sin w}{w^{4}}.

Now, for all w > 0, 1−cos w > w^{2}/2−w^{4}/24, and sin w < w−w^{3}/6+w^{5}/120. Thus,

6(1 − cos w) + w^{2} − 4w sin w ≥ 6 (\frac{w^{2}}{2} − \frac{w^{4}}{24} ) + w^{2} − 4w (w − \frac{w^{3}}{6} − \frac{w^{5}}{120})
= \frac{5w^{4}}{12} − \frac{w^{6}}{30} > 0,

as long as w^{2} < 25/2. This is satisfied if w ≤ π. For π < w < 2π, 6(1 − cos w) + w^{2} − 4w sin w > 0 as sin w is negative in this range. Since w^{2} > 4w sin w for w > 4 we have 6(1 − cos w) + w^{2} − 4w sin w > 0 for all w > 0. Thus, since ϕ is positive, ϕ̂ > 0 for all w ≥ 0 and ϕ ∈ PD_{1}.

For ϕ ∈ PD_{3} we require, due to Proposition 2, Dϕ̂ > 0. Now,

Dϕ̂(w) = −\frac{1}{w} \frac{d}{dw} \frac{6(1 − cos w) + w^{2} − 4w sin w}{w^{4}}
= 2 (\frac{12(1 − cos w) + w^{2} + 2w^{2} cos w − 9w sin w}{w^{6}} ) .

Now, when w = 9, Dϕ̂(w) ≈ −0.0003 so that Dϕ̂ ≯ 0 and ϕ ∉ PD_{3}.

References

[1] S. Bochner, Monotone Funktionen, Stieltjessche Integrale und harmonische Analyse, Math. Annalen 108 (1933), 378–410.

[2] Radial functions on compact support, Proc. Edin. Math. Soc. II 41 (1998), 33–46.

[3] N. Morrison, Introduction to Fourier Analysis, Wiley, 1995.

[4] I. J. Schoenberg, Metric spaces and completely monotone functions, Ann. Math. 39 (1938), 811–841.

[5] H. Wendland, Piecewise polynomial, positive definite and compactly supported radial basis functions of minimal degree, Adv. in Comp. Math. 4 (1995), 389–396.

[6] H. Wendland, On the smoothness of positive definite and radial functions, J. Comp. and App. Math. 101 (1999), 177–188.

[7] D. V. Widder, The Laplace Transform, Princeton, 1966.

[8] Z. Wu, Compactly supported positive definite radial functions, Adv. in Comp. Math. 4 (1995), 283–292.