Characterization of Positive Definite Radial Functions

Zongmin Wu

Abstract. Positive definite multivariate radial functions with existing multivariate Fourier transforms are characterized by multiple monotonicity of their univariate Fourier transforms, when written as functions of r^{2} instead of r. This result allows to prove that uniform B–splines are not positive definite when used as radial multivariate functions. Furthermore, there is a general construction scheme that allows to generate all positive definite radial functions via multiply monotone functions by purely univariate operations.

§1. Introduction

Multivariate functions Φ : IR^{n} → IR can be efficiently evaluated if they are expressible as univariate radial functions Φ(·) = ϕ(|| · ||_{2}) of the Euclidean norm || · ||_{2} in IR^{n}. A typical application is the construction of interpolants

S_{f}(x) = ∑_{j=1}^{N} λ_{j}ϕ(||x − x_{j}||_{2})  (1)

for scattered data {x_{j}, f_{j}} ∈ IR^{n} × IR, 1 ≤ j ≤ N on a set X = {x_{1}, …, x_{N}} of pairwise distinct centers (see surveys [3], [4], [6], [8], [9]). A major feature of interpolants of the form (1) is their independence from Euclidean transformations of the data set.

It is easy to see that the interpolation problem is uniquely solvable if the coefficient matrix

A = (ϕ(||x_{j} − x_{k}||))_{1≤j,k≤N}  (2)

is positive definite for any set X = {x_{1}, …, x_{N}} ⊂ IR^{n}, |X| = N. Then the univariate function ϕ : IR_{≥0} → IR is called positive definite on IR^{n}. Note that this definition depends on the space dimension n, while the function ϕ is fixed. Clearly, a function that is positive definite on IR^{n} will also be positive definite in spaces of smaller dimension, but there may be a largest dimension in which the function is positive definite. We shall address this issue and related questions in the rest of the paper, since we are characterizing an important subclass of positive definite functions on IR^{n}.

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.

§2. Basic Results

If a function ϕ : IR_{≥0} → IR satisfies for some n ≥ 1 the decay condition

ϕ(r)r^{n−1} ∈ L_{1}(0, ∞) ∩ C^{0}[0, ∞),  (3)

which we abbreviate by ϕ ∈ DC_{n}, then it has an n-dimensional Fourier transform

\begin{aligned}(F_{n}ϕ)(t) & = (2π)^{−n/2} ∫_{IR_{n}} e^{i<ω,x>}ϕ(||x||_{2})dx \\ & = ∫_{0}^{∞} ϕ(r)r^{n−1}(rt)^{− \frac{n−2}{2}} J_{\frac{n−2}{2}} (rt)dr, \end{aligned}  (4)

where t = ||ω||_{2} holds and J_{\frac{n−2}{2}} is Bessel’s function of the first kind. With a slightly different normalization, equation (4) can be found in Stein & Weiss [11]. Our normalization makes sure that F_{n}^{−1} = F_{n} holds wherever both operators are defined. Note that we write F_{n} as an operator on univariate functions that are interpreted as radial multivariate functions.

By a famous theorem of Bochner (see Stewart [12]), positive definiteness of Φ(·) = ϕ(∥ · ∥_{2}) on IR^{n} is equivalent to nonnegativity of F_{n}ϕ and positivity on at least an open interval. We shall abbreviate this fact by F_{n}ϕ ˙≥ 0. A generalization of Bochner’s theorem for conditionally positive definite functions in the sense of Micchelli [7] was recently given by Iske [5].

To avoid complications arising from nonexisting Fourier transforms, we are going to characterize the set PD_{n} := {ϕ ∈ DC_{n}, F_{n}ϕ ˙≥ 0} of positive definite functions on IR^{n} with the decay condition (3) that ensures existence of the n-variate Fourier transform.

Bessel’s functions of the first kind satisfy the recursive formula

(z^{−μ}J_{μ}(z))′ = −z^{μ}J_{μ+1}(z)

for μ ∈ IR (see Abramowitz and Stegun [1], p. 361, 9.1.30). Then an easy differentiation of (4) yields

Theorem 1. For all functions ϕ : IR_{≥0} → IR with (3) and n > 2 we have

(F_{n}ϕ)(r) = (DF_{n−2}ϕ)(r), r > 0  (5)

with the differential operator (Df)(r) := −\frac{1}{r} \frac{df(r)}{dr}.

Equation (5) was used in [13] to construct certain positive definite functions of compact support. Here, we apply (5) recursively in spaces of odd dimension n = 2k + 1 to get

(F_{2ℓ+1}ϕ)(r) = (D^{ℓ}F_{1}ϕ)(r), r > 0, 0 ≤ ℓ ≤ k.

Then we rewrite everything in terms of r^{2}/2 using the operator Q defined by ϕ(r) =: (Qϕ)(r^{2}/2). The differential operator now simplifies to a derivative, i.e.: QDϕ = −(Qϕ)′, and we find that the functions

(QF_{2ℓ+1}ϕ)(r) = (−1)^{ℓ} \frac{d^{ℓ}}{dr^{ℓ}} (QF_{1}ϕ)(r), 0 ≤ ℓ ≤ k

must be nonnegative for all ϕ ∈ PD_{2k+1}. We call

MM_{k} := {f ∈ C^{k}[0, ∞) a.e. : (−1)^{ℓ}f^{ℓ} ˙≥ 0, 0 ≤ ℓ ≤ k}

the set of multiply monotone radial functions of order k (see Buhmann [2]). Thus we have proven

Theorem 2. Positive definite radial functions with existing Fourier transforms can be characterized by

PD_{2k+1} = DC_{2k+1} ∩ {ϕ : IR_{≥0} → IR, QF_{1}ϕ ∈ MM_{k}} .

Note that this characterization involves only univariate ingredients. The case of even dimensions can be handled by a similar approach that will be published elsewhere.

§3. Applications

Theorem 2 yields a simple algorithm to check whether a specific function ϕ on IR_{≥0} is positive definite on some R^{n}. One simply forms the function f := QF_{1}ϕ and checks the property f ∈ MM_{k} for increasing values of k by testing f for positivity, monotonic decay, convexity, and so on.

Example 1. Natural candidates for this check are polynomial B–splines. Schaback & Wendland [10] have shown numerically that the symmetric uniform B–splines of order 4 and 6 are not positive definite in any IR^{n} for n ≥ 2. The above algorithm answers this question in general. The uniform B-splines of even order 2k ≥ 2 are in PD_{1} but not in PD_{3}, since their univariate Fourier transforms are even powers of the sinc-function, which are nonnegative, but not monotone decreasing for positive arguments.

The above algorithm can be used to prove or disprove positive definiteness of certain given functions ϕ on spaces of large dimensions. Besides this a–posteriori technique there is a very easy way to construct new positive definite functions. Due to Theorem 2, it has to start by constructing multiply monotone functions. If f_{k} is in MM_{k} ∩ DC_{m} with m > 1 and k ≥ 0, then

f_{k+1}(r) := ∫_{r}^{∞} f_{k}(s)ds, r > 0  (6)

is in MM_{k+1} ∩ DC_{m−1}. If we rewrite this for functions of r^{2}/2 instead of r, we get an integral operator

(If)(r) := ∫_{r}^{∞} sf(s)ds, r ≥ 0

that is inverse to the differential operator D and satisfies

QIϕ ∈ MM_{k+1} ∩ DC_{m−1} for ϕ with Qϕ ∈ MM_{k} ∩ DC_{m}, m > 1.

For functions defined by Qg_{k} := f_{k} we then have g_{k+1} = Ig_{k}. Together with Theorem 1 this technique now allows recursive construction of positive definite functions on odd-dimensional spaces. We start with a function f_{0} ˙≥ 0 with sufficient decay, i.e. f ∈ DC_{ℓ}, and generate multiply monotone functions f_{k} ∈ MM_{k}∩DC_{ℓ−k} for 0 ≤ k ≤ ℓ via (6). This is an easy integration that preserves piecewise polynomials and compactly supported functions. Reparametrization leads to functions g_{k} ∈ DC_{2ℓ−2k} with Qg_{k} := f_{k} or f_{k}(r^{2}/2) = g_{k}(r). These functions satisfy

I^{m}g_{k} = g_{m+k}, 0 ≤ m, k ≤ m + k ≤ ℓ, g_{k} = D^{m}g_{m+k}, 0 ≤ m, k ≤ m + k ≤ ℓ

and we finally define

ϕ_{k} := F_{1}g_{k} = F_{1}I^{k}g_{0} = D^{k}F_{1}g_{0} = D^{k}ϕ_{0}

and calculate these functions either from g_{k} via univariate Fourier transforms or by application of D^{k} to the function ϕ_{0} = F_{1}g_{0}. Then we have ϕ_{k} ∈ PD_{2k+1} because of F_{2k+1}ϕ_{k} = D^{k}F_{1}F_{1}g_{k} = D^{k}g_{k} = g_{0} ˙≥ 0. Note that for increasing k the functions f_{k} and g_{k} gain smoothness, while the functions ϕ_{k} = F_{1}g_{k} gain decay at infinity. Furthermore, Theorem 2 implies that any positive definite function ϕ with enough decay to guarantee existence of the n-variate Fourier transform can be generated this way, provided that the function f_{0} := QF_{1}ϕ is explicitly known.

Example 2. The truncated power function f_{ℓ}(x) := (1 − 2x)_{+}^{ℓ} is in MM_{ℓ} for any ℓ ≥ 0. Thus the function

ϕ_{ℓ}(r) = F_{1}f_{ℓ}(·^{2}/2)(r) = F_{1}g_{ℓ}(·)(r) = \sqrt{\frac{2}{π}} ∫_{0}^{∞}(1 − t^{2})_{+}^{ℓ} cos(rt)dt

is in PD_{2ℓ+1} and satisfies

(QF_{2k+1}ϕ_{ℓ})(r) = (−1)^{k} \frac{d^{k}}{dr^{k}} (QF_{1}ϕ_{ℓ})(r) = \frac{2^{ℓ−k}ℓ!}{(ℓ − k)!} f_{ℓ−k}(r)

for 0 ≤ k ≤ ℓ. In general, the above equation leads to

ϕ_{ℓ}(r) = \frac{2^{ℓ−k}ℓ!}{(ℓ − k)!} F_{2k+1}g_{ℓ−k}(·)(r) for 0 ≤ k ≤ ℓ.

Using Theorem 4.15 of Stein and Weiss [11] this can be evaluated directly as

ϕ_{ℓ}(r) = 2^{ℓ} · Γ(ℓ + 1)r^{−ℓ−1/2}J_{ℓ+1/2}(r).

Since Bessel functions of half–integer order are easily expressible by elementary functions, we finally have a series of positive definite elementary functions on spaces of increasing dimension and with compactly supported Fourier transform. Of course, this series starts with

ϕ_{0}(r) = J_{\frac{1}{2}} (r)/\sqrt{r} = \sqrt{\frac{2}{π}} sinc(r)

and generalizes the sinc function used in classical univariate sampling theory.

The above example started with compactly supported multiply monotone functions in the “frequency” domain, leading to analytic functions of exponential type in the “time” domain. The next example will turn this upside down, but one has to make sure that the resulting Fourier transforms are nonnegative. This is done by using convolutions of smooth compactly supported functions ψ in the “time” domain. Then the general construction starts with the nonnegative function f_{0} := F_{1}(ψ)^{2} ∈ MM_{0} whose decay is large enough to cope with sufficiently many space dimensions if ψ is smooth enough. Here is a specific case of this construction, taken from [13].

Example 3. Fixing a parameter ℓ > 0 one starts with ψ_{ℓ}(x) := (1 − x^{2})_{+}^{ℓ} and forms ϕ_{ℓ,k} := D^{k}(ψ_{ℓ} ∗ψ_{ℓ}) for 0 ≤ k ≤ ℓ. These functions can be explicitly calculated as piecewise rational functions with compact support. In fact, they consist of only one polynomial piece on their support in IR_{≥0}. Their positive definiteness properties are not directly visible from the definitions. But from

\begin{aligned}ϕ_{ℓ,k} & = D^{k}F_{1}F_{1}ϕ_{ℓ,0} = D^{k}F_{1}(F_{1}ψ_{ℓ})^{2} = F_{1}I^{k}F_{1}ϕ_{ℓ,0} = F_{1}g_{ℓ,k}, \\ g_{ℓ,k} & = F_{1}ϕ_{ℓ,k} = I^{k}(F_{1}ψ_{ℓ})^{2} = I^{k}g_{ℓ,0} \end{aligned}

we see that the functions f_{ℓ,k} := Qg_{ℓ,k} = QF_{1}ϕ_{ℓ,k} are in MM_{k}. Or, more directly, we can look at

F_{2k+1}ϕ_{ℓ,k} = D^{k}F_{1}D^{k}ϕ_{ℓ,0} = F_{1}ϕ_{ℓ,0} ˙≥ 0

to see that ϕ_{ℓ,k} ∈ PD_{2k+1}. Our general construction principle, as described above, could start with f_{0} := f_{ℓ,0}, but we took a shortcut by calculating ϕ_{ℓ,k} directly from ψ_{ℓ} by taking derivatives of a convolution. A table of the functions ϕ_{ℓ,k}, rescaled to [0, 1], is in [13].

Acknowledgements. It is a pleasure to acknowledge that R. Schaback helped greatly to bring this paper into shape. This work was done during the author’s visit to Göttingen under support of a DAAD-Wong fellowship Germany–Hongkong and National Science Foundation of China.

References

1. Abramowitz, M., and I. A. Stegun, Handbook of Mathematical Functions, Dover, New York, 1970.

2. Buhmann, M., Micchelli, C. A., Multiply monotone functions for cardinal interpolation, Advances in Appl. Math. 12 (1991), 359–386.

3. Buhmann, M., New Developments in the Theory of Radial Basis Function Interpolation, in: Multivariate Approximation and Wavelets, K. Jetter, F. I. Utreras (eds.), World Scientific, Singapore, 1992, 35–75.

4. 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, 1987, 47–61.

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

6. W. A. Light, Some aspects of Radial Basis Function Approximation. Approximation Theory, Spline Functions and Applications, S.P.Singh (ed.) NATO ASI Series 356 (1992), 163–190.

7. Micchelli, C. A., Interpolation of scattered data: distance matrix and conditionally positive definite functions. Constructive Approximation 2 (1986), 11–22.

8. 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.

9. Schaback, R. Creating Surfaces from Scattered Data, this volume.

10. Schaback, R. Wendland, H., Special Cases of Compactly Supported Radial Basis Functions, preprint, Göttingen, 1993.

11. Stein, E., M., Weiss, G,. Introduction to Fourier Analysis on Euclidean Spaces., Princeton University Press, 1971.

12. Stewart, J., Positive definite functions and generalizations, an historical survey, Rocky Mountain J. Math 6, 409–434.

13. Wu, Z., Multivariate compactly supported positive definite radial functions, preprint, Göttingen, 1994.

Zongmin Wu Department of Mathematics Fudan University 200433 Shanghai China