CONVERGENCE OF INCREASINGLY FLAT RADIAL BASIS INTERPOLANTS TO POLYNOMIAL INTERPOLANTS∗
YEON JU LEE†, GANG JOON YOON‡, AND JUNGHO YOON†
Abstract. In this paper, we study the convergence behavior of interpolants by smooth radial basis functions to polynomial interpolants inRd as the radial basis functions are scaled to be in- creasingly flat. Larsson and Fornberg [Comput. Math. Appl., 49 (2005), pp. 103–130] conjectured a sufficient property for this convergence, and they also conjectured that Bessel radial functions do not satisfy this property. First, in the case of positive definite radial functions, we prove both conjectures by Larsson and Fornberg for the convergence of increasingly flat radial function interpolants. Next, we extend the results to the case of conditionally positive definite radial functions of order m > 0.
Key words. radial basis function, interpolation, polynomial, conditionally positive definite function
AMS subject classifications. 41A05, 41A15, 41A25, 41A30, 41A63 DOI. 10.1137/050642113
1. Introduction. One of the most important issues in many areas of applied mathematics and applications is to construct an approximation to scattered data:
Given a set X of scattered points in Ω ⊂ Rd and values f|X of some underlying function f , the goal is to find a function s : Ω → Rd such that s approximates f in some sense. Radial basis functions (RBFs) provide well-established tools for solving the scattered data approximation or interpolation problem. In addition, they are becoming increasingly popular for the numerical solution of partial differential equations.
A function φ : Rd → R is radial in the sense that φ(x) = Φ(|x|), where |x| :=
(x21 +· · · + x2d)1/2 stands for the usual Euclidean norm. The common choices of φ can be divided into two groups, piecewise smooth such as the thin plate spline φ(x) =|x|2log|x| and infinitely smooth such as multiquadrics φ(x) = (|x|2+ λ2)1/2. In this paper, we are interested in the infinitely smooth basis functions φ so that each function φ can be expanded as
φ(x) = Φ(|x|) =∞
n=0
cn|x|2n,
which actually means φ is analytic. An attractive feature of using an infinitely smooth function is that it can provide spectral approximation order [10, 11, 13, 16, 17]. Typ- ical examples of such basis functions are given as follows: For d∈ N and λ > 0,
• φ(x) := (|x|2+ λ2)m−d/2, d odd, m− d/2 > 0, (multiquadrics),
• φ(x) := (|x|2+ λ2)m−d/2log(|x|2+ λ2)1/2, m > d/2, d even, (‘shifted’ surface splines).
∗Received by the editors October 7, 2005; accepted for publication (in revised form) November 27, 2006; published electronically July 11, 2007.
http://www.siam.org/journals/sima/39-2/64211.html
†Corresponding author: Jungho Yoon. Department of Mathematics, Ewha W. University, Seoul, 120-750, S. Korea (lee08@ewhain.net, yoon@math.ewha.ac.kr). This work has been supported by grant R01-2006-000-10424-0 from Korea Science and Engineering Foundation in Ministry of Science and Technology.
‡School of Mathematics, KIAS, Seoul, 130-722, S. Korea (ykj@kias.re.kr).
537
• φ(x) := (|x|2+ λ2)m−d/2, 0 < m < d/2, (inverse multiquadrics),
• φ(x) := e−|x|2/λ2, (Gaussians),
These functions are considered as tempered distributions and have generalized Fourier transforms of the form
(1.1) | · |2mφ = Fˆ ∈ L∞(Rd), m≥ 0,
where, indeed, the function F is nonnegative onRd and positive at least on an open subset ofRd. We will see in section 3 that it is an important ingredient for the conver- gence of increasingly flat RBF interpolants to multivariate polynomial interpolants.
Further, the condition (1.1) is the major difference from the Bessel radial function φd
[5], which is defined by
(1.2) φd(x) :=
Jd 2−1(|x|)
|x|d2−1 , d = 1, 2, . . . ,
where Jαdenotes the first kind Bessel function of order α. The Fourier transform of φd is proportional to a Dirac distribution, that is, ˆφd≈ δ(| · | − 1) (see [7, p. 364]).
The RBFs can be scaled in such a way to be wider by a shape parameter > 0, i.e., φ(x) := φ(x). It has been observed independently during the last decades that for smooth data, a very small value of gives very accurate results for both interpolation problems and solving elliptic partial differential equations. For this, the reader is referred to the recent papers [4, 8]; unfortunately, we have been unable to locate it in any previous references. In this case, the basis function becomes very flat and the condition number of the interpolation system grows rapidly.
In [3], Driscoll and Fornberg introduced a surprising observation that the limit of an RBF interpolant often exists and takes the form of a polynomial. Later, Forn- berg, Wright, and Larsson [6] and, in parallel, Schaback [14] proved that the limiting RBF interpolant is a (multivariate) finite order polynomial interpolant, if it exists.
In particular, Schaback [14] showed that interpolation with scaled Gaussians always converges to the de Boor–Ron polynomial interpolation when the Gaussian widths increase. Subsequent to carrying out this study, we became aware of another recent paper by Larsson and Fornberg [9]; they generated a matrix in (2.4) (hereafter, de- noted by Bp,K with 0≤ p ≤ d and K ≥ 0) from the Taylor expansion of the given RBF and proved that the nonsingularity of these matrices guarantees the convergence of the RBF interpolation to a multivariate polynomial interpolation, if it exists, as the shape parameter → 0. However, the nonsingularity of Bp,K is just conjectured and yet to be proved. Thus, the first goal of this paper is to prove this conjecture.
Moreover, it is also observed in [9] that this convergence property holds for the com- monly well known RBF interpolants, but some different behavior was seen for the Bessel RBF; we will see it also in section 3. There needs to be a clear discussion on the reason for the deviant behavior of the Bessel RBF interpolant. For this reason, our next aim is to provide a detailed proof and conditions which address this issue.
The specific contribution of this study is given as follows:
• For any 0 ≤ p ≤ d and K ≥ 0, the matrix Bp,Kis proved to be nonsingular for all positive definite RBFs which satisfy the condition (1.1). It implies that a positive definite RBF interpolant converges to a multivariate polynomial interpolant, if it exists, as the shape parameter → 0. In fact, the existence of the limiting interpolant is guaranteed when the set X is unisolvent. However, if the set X is nonunisolvent, it is still an open problem to describe the condition under which the limit exists.
• We provide more detailed discussion on the difference between the commonly used RBFs and the Bessel RBF. It is verified that the matrix Bp,K for the Bessel RBF is singular (as is conjectured by Larsson and Fornberg in [9]) whenever K ≥ p + 2.
• The state-of-the-art studies on the limit of increasing flat RBF have consid- ered the interpolation from the space span{φ(ε(x − xj)) : xj∈ X} [8, 9, 14].
However, usually, when φ is conditionally positive definite of order m, some suitable polynomial of degree m− 1 is added for the construction of inter- polation. Thus, this study is concerned with RBF interpolation from the augmented space span{φ(ε(x − xj)) : xj ∈ X} + Π<m. Specifically, the ma- trix Bp,K is modified for conditionally positive definite RBFs of order m > 0 and proved to be nonsingular. Then, we show that the corresponding RBF interpolant tends to a polynomial interpolant, if it exists, as the shape pa- rameter → 0.
We use the following notation throughout this paper. For α, β∈ Zd+:={(γ1, . . . , γd)∈ Zd : γk ≥ 0}, we set α! := α1!· · · αd!, |α|1 :=d
k=1αk, and αβ := αβ11· · · αβdd. The Fourier transform of f ∈ L1(Rd) is defined as
f (θ) :=ˆ
Rd
f (t) exp(−iθ · t) dt.
Also, for a function f ∈ L1(Rd), we use the notation f∨ for the inverse Fourier transform. The Fourier transform can be uniquely extended to the space of tempered distributions onRd. Let Π<K denote the space of d-variate algebraic polynomials of degree < K onRd and denote
(1.3) Kd:= dim Π<K+1=
K + d d
.
2. Larsson and Fornberg’s conjectures. In this section, we revisit the work of Larsson and Fornberg in [9] and introduce their conjectures. For this, the multi- index definitions from [9] are introduced.
Definition 2.1. Let α =: (α1, . . . , αd) and β =: (β1, . . . , βd) be in Zd+. Then we define the following terminologies:
(a) The multi-indices α, β are said to have the same parity if the components αj and βj with j = 1, . . . , d have the same parity.
(b) The polynomial ordering of a sequence of multi-indices is determined in the way that the index α comes before β if |α|1<|β|1 or if |α|1=|β|1, αj= βj, j = 1, . . . , p, and αp+1< βp+1.
Definition 2.2. Let IK, where K≥ 0, be the polynomially ordered sequence of all multi-indices α = (α1, . . . , αd) such that |α|1≤ K. For n ∈ N, IK(n) denotes the nth multi-index in the sequence.
Definition 2.3. Let Ip,K, where 0 ≤ p ≤ d and K ≥ 0, be the polynomi- ally ordered sequence of all multi-indices α = (α1, . . . , αd) with |α|1 ≤ K such that α1, . . . , αp are odd numbers, the others are even numbers. For n∈ N, Ip,K(n) denotes the nth multi-index in the sequence.
Definition 2.4. Let I2nα be the polynomially ordered set of all multi-indices β such that |α + β|1= 2n, and α and β have the same parity.
Let X = {xj : j = 1, . . . , N} and (K − 1)d < N ≤ Kd with Kd in (1.3). Let p1, . . . , pN be N independent polynomials in Π<K+1. We say X is unisolvent with respect to {pj : j = 1, . . . , N} if there is a unique linear combination
βjpj(x)
such that it interpolates the data over the point set X. If X is nonunisolvent with respect to any choice of N linearly independent basis functions from Π<K+1, there is a smallest integer M > K such that we can form a minimal nondegenerate set {pj: j = 1, . . . , N} chosen from the basis in Π<M +1, that is,
det(pj(x) : j, = 1, . . . , N )= 0.
Then the degree of the minimal nondegenerate basis is said to be M . With this definition in hand, we introduce the relation between polynomial interpolation and the distribution of the set X.
Proposition 2.5 (see [9]). Let X = {x1, . . . , xN} and (K − 1)d < N ≤ Kd
with Kd in (1.3). If X is unisolvent with respect to any set of N linearly independent polynomials in Π<K+1, then
(I) if N = Kd, then there is a unique interpolating polynomial of degree K for any given data on X;
(II) if N < Kd, then there is an interpolating polynomial of degree K for any given data on X, for each choice of N linearly independent basis functions.
If X is nonunisolvent and the degree of the minimal nondegenerate basis is M , then (III) there is an interpolating polynomial of degree M for any given data on X, for
each choice of a minimal nondegenerate basis.
Invoking that the RBFs φ considered in this paper are real analytic, the Taylor expansion of φ(x− xj) = Φ(|x − xj|) with respect to |x − xj| is given as
(2.1) φ(x− xj) =
∞ n=0
cn|x − xj|2n.
Here, the coefficient of xαin the expansion of|x − xj|2n can be written by
|x − xj|2n
xα=
β∈Iα2n
(−1)|α|1 n!
(α+β2 )!
(α + β)!
α!β! xβj.
For the proof of this identity, the reader is referred to [15]. Combining this with (2.1), we see that the coefficient of xαin the expansion of φ(x− xj) is
(2.2) φ(x− xj)|xα =
∞
n=|α+2→−1|1
cn
β∈I2nα
(−1)|α|1 n!
(α+β2 )!
(α + β)!
α!β! xβj,
where−→1 = (1, . . . , 1)∈ Rdand for any γ = (γ1, . . . , γd)∈ Zd+, γ := ( γ1, . . . , γd) with s the greatest integer less than or equal to s. Based on this expansion of φ, we define the symmetric function Bn(α, β) by
(2.3) Bn(α, β) := cn(−1)|α|1 n!
(α+β2 )!
(α + β)!
α!β! , |α + β|1= 2n,
where α, β ∈ Zd+ × Zd+ with the same parity. Then the conjectures suggested by Larsson and Fornberg are given as follows.
Larsson–Fornberg’s Conjecture I. For 0≤ p ≤ d and 0 ≤ K, the matrices Bp,K, defined by
(2.4) Bp,K:=
Bn(α, β) : α, β∈ Ip,K
,
are nonsingular for all commonly known RBFs such as (inverse) multiquadrics and Gaussians.
It is necessary to remark that in the above conjecture, the Bessel RBF is not included. The following theorem is the main result of [9].
Theorem 2.6 (see [9]). Let X = {x1, . . . , xN} and (K − 1)d < N ≤ Kd with Kd in (1.3). Assume that Larsson–Fornberg conjecture I holds. Then, we have the following properties:
(a) If the set X is of type (I), then the limit of the RBF interpolant as the shape parameter ε → 0 is the unique interpolating polynomial of degree K to the given data.
(b) If the set X is of type (II), then the limit of the RBF interpolant as the shape parameter ε→ 0 is a polynomial of degree K that interpolates the given data.
The exact polynomial depends on the choice of RBF.
(c) If the set X is of type (III), then the limit of the RBF interpolant as the shape parameter ε→ 0, if the limit exists, is a polynomial of degree M that interpolates the given data.
Remark. It has been proved by Schaback [14] that interpolation by scaled Gauss- ians always converges to the de Boor–Ron polynomial interpolant when the Gaussian widths increase. However, in the cases of multiquadrics and inverse multiquadrics, there occur some cases where the interpolants diverge in the limit; for examples, see [3] and [9]. Also, for the case of type (II), the reader is referred to the same papers [3] and [9] for an example of different limit polynomials affected by different RBFs.
In [9, Example 2.4], there occurs a case where all commonly used RBFs except the Bessel RBF have the same limit which is the unique interpolating polynomial; see also section 3. Thus, it is conjectured that the expansion coefficients of the Bessel RBF do not fulfill the nonsingularity condition of Bp,J in (2.4).
Larsson–Fornberg’s Conjecture II. All matrices Bp,K with K > 1 are singular for the expansion coefficients of the Bessel radial basis function.
In the following section, we will prove that the Larsson–Fornberg conjectures are true. Also, the difference between the commonly used RBFs and Bessel RBF will be discussed. Furthermore, we extend Theorem 2.6 up to the case of RBF interpolation from the augmented space span{φ(x − xj) : xj ∈ X} + Π<m, using conditionally positive definite φ of order m≥ 0.
3. The main results.
3.1. Positive definite function. We first prove that Larsson–Fornberg’s con- jecture I is true for all positive definite functions whose Fourier transforms ˆφ satisfy the condition (1.1).
Definition 3.1. Let φ : Rd → R be a continuous function and Ω ⊂ Rd. We say that φ is conditionally positive definite of order m ∈ Z+ := {0, 1, . . . } if for every finite set of pairwise distinct points X = {x1, . . . , xN} ⊂ Ω and for every α = (α1, . . . , αN)∈ RN\ 0 satisfying
(3.1)
N j=1
αjp(xj) = 0, p∈ Π<m,
the quadratic form
N i=1
N j=1
αiαjφ(xi− xj)
is positive definite. A conditionally positive definite function of order 0 is called a positive definite function.
Indeed, the condition (3.1) may seem a bit technical and hard to verify in practice.
However, the positive definiteness of continuous and absolutely integrable functions φ is guaranteed when the Fourier transform ˆφ satisfies the condition (1.1) with m = 0.
We note in passing that this argument is a consequence of the simple identity
(3.2)
N j=1
N k=1
αjαkφ(xj− xk) = 1 (2π)d
Rd
φ(θ)ˆ
N j=1
αjeixj·θ
2
dθ
for any (α1, . . . , αN)∈ RN \ 0 and the fact that the map θ →N
j=1αjeixj·θ, θ∈ Rd, has zeros at most on a set of measure zero. This identity is also generalized to the case of conditionally positive definite functions φ of order m > 0.
Suppose that a continuous function f :Rd→ R is known only at a set of discrete points X := {x1, . . . , xN} in Ω ⊂ Rd. A RBF interpolant to the data (xj, f (xj)), j = 1, . . . , N , with a positive definite function φ(ε·) is given by
(3.3) s(x, ε) :=
N j=1
ajφ(ε(x− xj)),
where the coefficients aj (j = 1, . . . , N ) are obtained by solving the linear system (3.4) s(xj, ε) = f (xj), j = 1, . . . , N.
Lemma 3.2. Let Bn(·, ·) be the symmetric function defined as in (2.3), and let α, β∈ Zd+ with the same parity and |α + β|1= 2n. Then, we have
Bn(α, β) = (−1)|α|1φ(α+β)(0) α!β! .
Proof. Since φ is radially symmetric, φ(· − xj) = φ(xj− ·). Taking the Taylor expansion of φ(xj− ·) around xj yields the expression
φ(xj− x) = ∞
|α|1=0
φ(α)(xj)(−x)α α!
=
∞
|α|1=0
⎛
⎝ ∞
|β|1=0
φ(α+β)(0)xβj β!
⎞
⎠ (−x)α α!
=
∞
|α|1=0
⎛
⎜⎝
∞
n=|α+2−→1|1
β∈Iα2n
φ(α+β)(0)xβj β!
⎞
⎟⎠(−x)α α! ;
where the second identity is a consequence of the Taylor expansion of φ(α)(xj) around the origin. Then the coefficient of xαin this expansion of φ(xj− x) is denoted by
(3.5) φ(x− xj)|xα=
∞
n=|α+2−→1|1
β∈I2nα
(−1)|α|1φ(α+β)(0) α!β! xβj.
Comparing (3.5) with (2.2), we obtain that
Bn(α, β) = (−1)|α|1φ(α+β)(0) α!β! ,
where α, β∈ Zd+ with the same parity and|α + β|1= 2n.
The following lemma is useful for the proof of the nonsingularity of Bp,K. Lemma 3.3. Let φ be a positive definite function, and assume that φ satisfies the condition (1.1) with m = 0, i.e., the Fourier transform ˆφ≥ 0 is positive on an open set in Rd. For any integer K > 0, define the matrix Tφ by
(3.6) Tφ:= Tφ,p,K :=
(−i)|α+β|1φ(α+β)(0)
α!β! : α, β∈ Ip,K
.
Then Tφ is positive definite, and so it is nonsingular.
Proof. Since α, β∈ Ip,K, both have the same parity and|α + β|1 is always even.
It means that each entry of the matrix Tφis real. Now, let γ := (γα: α∈ Ip,K) be an arbitrary nonzero vector. Then, the nonsingularity of Tφ is guaranteed by showing that γTφγT > 0, i.e.,
(3.7) γTφγT =
β∈Ip,K
α∈Ip,K
γαγβ(−i)|α+β|1φ(α+β)(0) α!β! > 0.
It is easy to see the identity
(3.8)
β∈Ip,K
α∈Ip,K
γαγβ(−i)|α+β|1φ(α+β)(0)
α!β! = 1
(2π)d
Rd
φ(θ)ˆ
α∈Ip,K
γαθα α!
2
dθ.
Since the Fourier transform ˆφ≥ 0 is nonnegative on Rd and positive at least on an open subset ofRd, the above term in (3.8) is positive, which completes the proof.
Remark. In fact, it is easy to check from the above proof that any symmetric matrix built from Bn(·, ·) is positive definite and so are all symmetrically chosen submatrices.
We now prove Larsson–Fornberg’s conjecture I.
Theorem 3.4. Let φ be a positive definite function and assume that φ satisfies the condition (1.1) with m = 0, i.e., the Fourier transform ˆφ ≥ 0 is positive on an open set in Rd. Then, for any integers p, K ≥ 0, the matrix Bp,K in (2.4) is nonsingular.
Proof. Using the form of Bp,K in Lemma 3.2, we see that det Tφ = c det Bp,K
with|c| = 1. Thus, by Lemma 3.3, we conclude that Bp,K is nonsingular.
As a conclusion, we can get the following results, which are actually restatements of Theorem 2.6.
Theorem 3.5. Let X = {x1, . . . , xN} and (K − 1)d < N ≤ Kd with Kd in (1.3). Assume that φ is a positive definite function and its Fourier transform ˆφ≥ 0 is positive on an open set in Rd. Then, we have the following properties:
(a) If the set X is of type (I), then the limit of the RBF interpolant s(·, ε) as the shape parameter ε→ 0 is the unique interpolating polynomial of degree K to the given data.
0 0.2 0.4 0.6 0.8 1 0
0.2 0.4 0.6 0.8 1
x y
Fig. 1. Scattered points X.
(b) If the set X is of type (II), then the limit of the RBF interpolant s(·, ε) as the shape parameter ε→ 0 is a polynomial of degree K that interpolates the given data. The exact polynomial depends on the choice of RBFs.
(c) If the set X is of type (III), then the limit of the RBF interpolant s(·, ε) as the shape parameter ε→ 0, if the limit exists, is a polynomial of degree M that interpolates the given data.
An interesting example was observed in [9, Example 2.4] wherein all the well known RBF interpolants except the Bessel RBF (see (1.2)) interpolant have the same limit (as ε→ 0), which is the unique polynomial interpolant. We revisit this example as follows.
Example 3.6. Let X = {(101,45), (15,15), (103, 1), (35,12), (45,35)} be a set of six points as in Figure 1 and f (xj) = δ0,j with j = 1, . . . , 6. These six points do not have any particular pattern. Expanding φ(ε(xi− xj)) in powers of ε2, the RBF interpolant s(x, ε) to the given data (xj, f (xj)) can be written in the form (see [6])
s(x, ε) = ε2rp2r(x) + ε2r+2p2r+2(x) + . . .
ε2qc2q+ ε2q+2c2q+2+ . . . , r, q∈ N,
where c2n, n = q, q + 1, . . . , are some constants and p2(x), = r, r + 1, . . . , are polynomials of degree (at most) 2 . When r = q, the limit exists as ε → 0 and it will be a polynomial of degree at most 2r. Based on this expansion we programmed the limit of RBF interpolants and obtained the following results. For all the known positive definite RBFs (e.g., inverse multiquadrics and Gaussians), the interpolants converge to the same two-variable polynomial of degree 2, that is,
εlim→0s(x, ε) = 1
28274(−7711 − 81420x + 132915y + 82300x2− 55450xy − 91550y2), which is the unique polynomial interpolant to the given data. However, the Bessel function interpolant converges to a third order polynomial
εlim→0s(x, ε) = 1
1017250518(−354545067 − 2047021330x + 4593056085y + 255438330x2− 4166831700xy − 2554383300y2
− 310763000x3+ 1319845500x2y + 932289000xy2− 439948500y3).
It is known that the Bessel radial function φd, d > 1, is positive definite (see [5, Theorem 3.1]). However, its Fourier transform is proportional to a Dirac distribution, i.e., ˆφd ≈ δ(| · | − 1) (see [7, p. 364]), which does not satisfy the condition (1.1). As far as we observed, this is the major difference between φd and the well known RBS.
In the next theorem, we prove Larsson–Fornberg’s conjecture II, that is, the matrix Bp,K of φd is singular whenever p + 2≤ K. It explains the deviant behavior of φd as in Example 3.6.
Theorem 3.7. Let 0≤ p ≤ d and p + 2 ≤ K with p, K ∈ N. Then the matrix Bp,K of the Bessel RBF φd is singular.
Proof. Recall the following Hankel transform onRd (see [2, p. 53]):
(3.9) φd(x) = 1
(2π)d/2
|θ|=1
eix·θdθ, x∈ Rd.
Invoking the definition of Tφd in (3.6), for an arbitrarily given γ = (γα : α∈ Ip,K), we get
γTφdγT =
β∈Ip,K
α∈Ip,K
γαγβ(−i)|α+β|1φ(α+β)d (0) α!β!
= 1
(2π)d/2
|θ|=1
α∈Ip,K
γαθα α!
2
dθ≥ 0,
which implies that all the eigenvalues of Tφd are nonnegative real numbers. In fact, since p + 2≤ K, we can choose γα with α∈ Ip,K such that
α∈Ip,K
γα
θα α!
2
=θIp,K(1)[1− (θ21+· · · + θ2d)]2, θ =: (θ1, . . . , θd),
where Ip,K(1) is the first index in Ip,K. Then γTφdγT becomes zero, which implies that the matrix Tφd is not positive definite but semipositive definite. It leads to the conclusion that Tφd has an eigenvalue of zero such that Tφd is singular. Since det(Tφd) = c det(Bp,K) with|c| = 1, Bp,K is singular.
3.2. Conditionally positive definite function. The RBF interpolant to the data (xj, f (xj)), j = 1, . . . , N , with a conditionally positive definite function φ of order m is given by
(3.10) s(x, ε) :=
N j=1
ajφ(ε(x− xj)) +
(m−1)d
i=1
bipi(x),
where p1, . . . , p(m−1)dis a basis for the space Π<m. The coefficients aj (j = 1, . . . , N ) and bi (i = 1, . . . , (m− 1)d) are obtained by solving the linear system which can be written in a matrix form as
(3.11)
A P
PT 0
a b
=
f 0
,
where A and P are the N × N and N × (m − 1)d matrices that have the elements Aij = φ(ε(xi−xj)) and Pij = pj(xi), respectively. Further, a∈ RN and b∈ R(m−1)d
are the vectors of coefficients of s(·, ε), and the components of f are the data f(xj), j = 1, . . . , N . Here, for m > 0, we require X to have the nondegeneracy property for Π<m, i.e.,
(3.12) q(xj) = 0, 1≤ j ≤ N for q ∈ Π<m implies q = 0.
The unique solution of the previous linear system is guaranteed when the function φ is conditionally positive definite of order m [12].
Definition 3.8. Let Ip,m,K, where 0≤ p ≤ d and m, K ≥ 0, be the polynomially ordered sequence of all multi-indices α = (α1, . . . , αd) with m≤ |α|1 ≤ K such that α1, . . . , αp are odd numbers, and the others are even numbers. For n∈ N, Ip,m,K(n) denotes the nth multi-index in the sequence.
Here and in what follows, assume that φ is conditionally positive definite of order m≥ 0. Recalling the Taylor expansion of φ, that is,
(3.13) φ(x− xj) =
∞ n=0
cn|x − xj|2n,
and using the symmetric function Bn(·, ·) in (2.3), let us define the matrix Bp,m,K
corresponding to the polynomially ordered sequence Ip,m,K by
(3.14) Bp,m,K :=
Bn(α, β) : α, β∈ Ip,m,K
.
Then, we will show that the matrix Bp,m,K is nonsingular.
Theorem 3.9. Let φ satisfy the condition (1.1). Then, the matrix Bp,m,K is nonsingular for any integers p, m, K > 0.
Proof. From Lemma 3.2, we find that
Bp,m,K=
(−1)|α|1φ(α+β)(0)
α!β! : α, β∈ Ip,m,K
.
Thus, as in Theorem 3.4, it suffices to prove the nonsingularity of the matrix T[m]φ defined by
T[m]φ := T[m]φ,p,K :=
(−i)|α+β|1φ(α+β)(0)
α!β! : α, β∈ Ip,m,K
.
For this, we show γT[m]φ γT > 0 for any nonzero vector γ := (γα: α∈ Ip,m,K). Indeed, we note that this is a consequence of the following relation:
γT[m]φ γT =
β∈Ip,m,K
α∈Ip,m,K
γαγβ(−i)|α+β|1φ(α+β)(0) (3.15) α!β!
= 1
(2π)d
Rd
φ(θ)ˆ
α∈Ip,m,K
γαθα α!
2
dθ.
Since| · |2mφ = Fˆ ≥ 0 and φ is real analytic, we deduce that the function F decays faster than any polynomial degree around∞. Thus, the last integral in (3.15) makes sense and is positive (see (1.1)). It completes the proof.
The following theorem treats the case of conditionally positive definiteness RBFs.
The proof will be given in section 4.
Theorem 3.10. Let φ be a conditionally positive definite RBF of order m≥ 0 with the condition (1.1). Let X = {x1, . . . , xN} and (K − 1)d < N ≤ Kd, where Kd= dim Π<K+1 and m < K. Then, we have the following properties:
(a) If the set X is of type (I), then the limit of the RBF interpolant (3.10) as the shape parameter ε→ 0 is the unique interpolating polynomial of degree K to the given data.
(b) If the set X is of type (II), then the limit of the RBF interpolant (3.10) as the shape parameter ε→ 0 is a polynomial of degree K that interpolates the given data. The exact polynomial depends on the choice of RBF.
(c) If the set X is of type (III), then the limit of the RBF interpolant (3.10) as the shape parameter ε→ 0, if the limit exists, is a polynomial of degree 2K − m that interpolates the given data.
Next, we introduce some examples of RBFs which satisfy the condition (1.1).
Example 3.11. Let the RBF φ be chosen to be one of the following:
(a) φ(x) := (|x|2+ λ2)m−d/2, m > d/2, m− d/2 ∈ 2Z (multiquadrics);
(b) φ(x) := (|x|2+ λ2)m−d/2log(|x|2+ λ2)1/2, m > d/2, d even (“shifted” surface splines);
(c) φ(x) := (|x|2+ λ2)m−d/2, 0 < m < d/2 (inverse multiquadrics);
(d) φ(x) := e−|x|2/λ2 (Gaussians);
where d ∈ N and λ > 0. In the sense of tempered distributions, the functions φ in (a), (b), and (c) have generalized Fourier transforms of the form (see [7])
(3.16) φ(θ) = cˆ m,λ,d|θ|−2mK˜m(|λθ|),
where cm,λ,d is a positive constant depending on m, λ and d, and where ˜Kν(|t|) :=
|t|νKν(|t|) with Kν(|t|) the modified Bessel function of order ν. From [1], we find that K˜ν(|t|) ∈ C2ν−1(Rd)∩ C∞(Rd\ {0}),
(3.17)
K˜ν(|t|) > 0, and ˜Kν(|t|) ≈ e−|t|(1 +|t|(ν−1/2)).
In the case of the Gaussian RBF φ in (d), its Fourier transform is of the form
φ(θ) := cˆ 0e−|θ|2/c21, c0, c1> 0.
4. A proof of Theorem 3.10. The general technique for the proofs is similar to the method given in [9], although the interpolant has an additional polynomial term associated with the order of conditionally positive definiteness of φ.
The RBF φ(ε·) can be written in even powers of |x| as follows:
(4.1) φε(x) := φ(εx) =
∞ j=0
cjε2j|x|2j.
Then the entries of the interpolation matrix A = (φ(ε(xi− xj)) : xi, xj ∈ X) can be expanded in even powers of ε as above. The coefficients aj, j = 1, . . . , N , and bi, i = 1, . . . , (m−1)d in (3.10) are obtained by Cramer’s rule, and they must be rational functions of ε2. That is, there exists an integer q such that we can write
(4.2) aj=: ε−2K
∞ n=−q
ε2naj,n, bi=: ε−2K
∞ n=−q
ε2nbi,n,
where at least one of (aj,−q: j = 1, . . . , N ) and (bj,−q: j = 1, . . . , (m−1)d) is a nonzero vector. Now, for each n≥ −q and β ∈ Zd+, the discrete moments of (a1,n, . . . , aN,n)T are defined by
(4.3) σn[β]:=
N j=1
aj,nxβj, n =−q, −q + 1, . . . .
Then, for the moments σn[β] with |β|1 ≤ m − 1 and n ≥ −q, we have the following estimate.
Lemma 4.1. Let β∈ Zd+ with |β|1≤ m − 1. Then, σ[β]n = 0 for any n≥ −q.
Proof. Multiplying by ε2n−2K by both sides of (4.3) and summing over n =
−q, −q + 1, . . . , we obtain from (4.2) that for any ε > 0 ε−2K
∞ n=−q
ε2nσ[β]n = ε−2K
N j=1
∞ n=−q
ε2naj,nxβj
=
N j=1
ajxβj = 0,
where the last identity is a simple consequence of (3.11). Thus, from this relation, we deduce the required result σn[β]= 0 with n≥ −q.
Let SN indicate an N -set of polynomially ordered multi-indices, i.e., #SN = N . Define the matrix V by
V = (xβj : j = 1, . . . , N, β∈ SN).
Then from (4.3), we have
(4.4) sn = V an, n =−q, −q + 1, . . . , where sn:= (σ[β]n : β∈ SN)T and an:= (aj,n: j = 1, . . . , N )T.
Recall that the RBF interpolant with a conditionally positive definite function φ of order m is given by
(4.5) s(x, ε) :=
N j=1
ajφ(ε(x− xj)) +
(m−1)d
i=1
bipi(x),
where p1, . . . , p(m−1)d is a basis for Π<m. Due to [9, page 123], we find that
(4.6)
N j=1
ajφ(ε(x− xj)) = ε−2K
∞ s=0
ε2(−q+s)P−q+s(x)
with
(4.7) P−q+s(x) =
α∈I2s
⎛
⎜⎝
s n=|α+2−→1|1
cn
β∈I2nα
(−1)|α| n!
(α+β2 )!
(α + β)!
α!β! σ[β]−q+s−n
⎞
⎟⎠ xα.
Applying Lemma 4.1, we note that all the coefficients of xαwith 2s−m+1 ≤ |α|1≤ 2s become zero. It follows that
(4.8) deg(P−q+s)≤ 2s − m.
Further, inserting (4.2) into (4.5), we obtain that (4.9) s(x, ε) = ε−2K
∞ s=0
ε2(−q+s)(P−q+s(x) + Q−q+s(x)),
where
(4.10) Q−q+s(x) =
(m−1)d
i=1
bi,−q+spi(x).
Let C1:={1, . . . , p} and Ci ={i1, . . . , ip: i <· · · < ip}, i = 2, . . . ,d
p
, be distinct subsets of{1, . . . , d}. Let τi be a permutation on{1, . . . , d} such that if ij ∈ Ci, then τi(ij) = j∈ C1.
Definition 4.2. We define Ip,m,Ki to be the ordered set of all multi-indices α = (ατi(1), . . . , ατi(d))∈ Zd+ with m≤ |α|1≤ K such that Ip,m,Ki (k) is a rearrangement of the components of Ip,m,K1 (k), where Ip,m,K1 = Ip,m,K and Ip,m,Ki (k) indicates the kth element in Ip,m,Ki .
The reader is referred to [9] for an example of such permutation. Now, from this definition, we decompose the set ˜Im,K :={α ∈ Zd+: m≤ |α|1≤ K} into the disjoint union of Ip,m,Ki ’s as follows:
I˜m,K =
p,i
Ip,m,Ki : p = 0, . . . , d and i = 1, . . . ,
d p
.
For J ≥ m and 0 ≤ p ≤ d, let α ∈ Ip,m,Ji be chosen. We investigate the coefficient of xα in P−q+s(x) (hereafter, denoted by P−q+s[α]) with 2s = J +|α|1. For this, using the definition of Bn(·, ·) in (2.3), we rewrite the coefficient P−q+s[α] in (4.7) as follows:
(4.11) P−q+s[α] =
s n=|α+2→−1|1
β∈I2nα
Bn(α, β)σ−q+s−n[β] .
Note that for any given n with| α+2−→1|1≤ n ≤ s, the index β in the second summation of the right-hand side in (4.11) has the same parity as α∈ Ip,m,Ji and satisfies|β|1≤ J because |α + β|1 = 2n≤ 2s. Also, due to Lemma 4.1, we can set |β|1 ≥ m. As a consequence, since |α|1 = 2s− J and |α + β|1 = 2n, the set of all such indices β is exactly the set Ip,m,Ji so that P−q+s[α] can be given as
(4.12) P−q+s[α] =
β∈Iip,m,J
Bn(α, β)σ[β]−q+(J−|β|
1)/2.
Next, in order to continue our argument, let us define the following two vectors:
sip,m,J := (σ[β]−q+n: β∈ Ip,m,Ji , n = (J− |β|1)/2), pip,m,J := (P−q+s[α] : α∈ Ip,m,Ji , s = (J +|α|1)/2).
Moreover, from the definition of B(·, ·) in (2.3), we see that Bn(α, β) is independent of the permutation τi in Definition 4.2, that is,
Bp,m,J =
Bn(α, β) : α, β ∈ Ip,m,Ji
, i = 2, . . . ,
d p
.
With the matrices from Definition 3.14 and the vectors defined above, we have a sequence of systems of equations for the discrete moments,
(4.13) Bp,m,Jsip,m,J = pip,m,J, i = 1, 2, . . . ,
d p
, and J = m, m + 1, . . . , where p and J have the same parity. By the assumption on φ and Theorem 3.9, the systems in (4.13) are nonsingular and we have a complete description of the relation between the discrete moments and the polynomials P−q+s. From the coefficients of the polynomials, the system in (4.13) can be solved directly for determining the moments because Bp,m,J is nonsingular for 0≤ p ≤ d and J ≥ 0.
There is a range of ε-values for which we get a well defined interpolant s(x, ε) in (4.5) to the data. If we relate this to the expansion (4.9), we get the following conditions:
• PK+ QK interpolates the data on the set X ={xj : j = 1, . . . , N}, (4.14)
• Pj+ Qj, j= K interpolates 0 on the set X.
Note that if Pj+ Qj, j= K is of degree < m, then the nondegeneracy property (3.12) of X on Π<mimplies Pj+ Qj= 0.
We now introduce two useful lemmas. First, recall that at least one of (aj,−q : j = 1, . . . , N ) and (bj,−q: j = 1, . . . , (m− 1)d) is a nonzero vector (see the line below (4.2)). In practice, we will see that (aj,−q: j = 1, . . . , N ) should be a nonzero vector.
Lemma 4.3. If aj,−q= 0 for j = 1, . . . , N , then bj,−q = 0 for j = 1, . . . , (m−1)d. Proof. Assume that aj,−q = 0 for j = 1, . . . , N . It is clear from Lemma 4.1 that P−q(x) in (4.7) is a zero polynomial. Since P−q+ Q−q= Q−q interpolates 0 at X, the nondegeneracy property (3.12) induces that the polynomial Q−q = 0. The definition of Q−q in (4.10) leads to the conclusion that bj,−q= 0 with j = 1, . . . , (m− 1)d.
Lemma 4.4. Let {pj(x) : j = 0, . . . , K} be a finite set of polynomials such that p0= 0 and pK= 0, and denote k := max{ ≥ 0 : pj = 0, j = 0, . . . , }. Suppose that
(i) pj= 0 or deg(pj) > K for any j = 0, . . . , K− 1;
(ii) deg(pj)≤ 2j − k − 1 for any j = k + 1, . . . , K.
Then k = K− 1 (i.e., pj = 0∀j = 0, . . . , K − 1) and deg(pK)≤ K.
Proof. Suppose, contrary to our claim, that k < K−1. From (ii), deg(pk+1)≤ k+
1 < K. Also, applying (i), we see that deg(pk+1) > K, which leads to a contradiction.
Thus, we conclude that k = K− 1 and by (ii), deg(pK)≤ K.
Now we are ready to prove Theorem 3.10. We consider the case when the set X is of type (I), i.e., #X = Kd, where Kd = dim Π<K+1 and K > m, and the set X is unisolvent with respect to any basis for Π<K+1. Then, the relation (4.4) holds for the basis{xα: α∈ IK}. Also, due to the unisolvency of X, any polynomial of degree
≤ K that interpolates zero at N points must be identically zero.
Proof (a) of Theorem 3.10. Invoking the fact deg(P−q+s)≤ 2s − m from (4.8), the condition (4.14) shows that at least,
P−q+j+ Q−q+j = 0 ∀j = 0, . . . ,
K + m 2
− 1.
