# Positive Approximation and Interpolation Using Compactly Supported Radial Basis Functions

Authors: Jinming Wu; Xiaolei Zhang; Lihui Peng
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

We discuss the problem of constrained approximation and interpolation of scattered data by using compactly supported radial basis functions, subjected to the constraint of preserving positivity. The approaches are presented to compute positive approximation and interpolation by solving the two corresponding optimization problems. Numerical experiments are provided to illustrate that the proposed method is flexible.


---

## Body

## 1. Introduction

The problem of scattered data interpolation consists of constructing a function that interpolates data values which are known at some scattered points. However, we often have some additional information that we wish to confine to interpolation. For example, we know the quantity from which the data is sampled, positive, monotonic, or convex. Thus, it is important to construct a function which satisfies the underlying constraints.In the past twenty years, the problem of positivity-preserving scattered data interpolation has been considered by many researchers. One class of methods for scattered data interpolation require the points to be triangulated mainly by using piecewise (rational) cubic interpolation and derived the conditions for preserving the shape of positive data. For related literature, we refer to the papers [1–6] and the references therein.Another major class of methods for scattered data interpolation does not involve any prior triangulation, and can be viewed as meshless method. The two main types are radial basis functions (RBFs), which include multiquadrics and thin-plate splines, and so forth, and Shepard-type methods, which include the modified quadratic Shepard approach. Both types, RBF and Shepard, are widely used in practical fields.However, there has been relatively little work done on the imposition of constraints for these meshless methods. For RBF, Utreras [7] considered how positivity can be imposed as a constraint in case of thin plate spline interpolation for two-dimensional data. For Shepard, Asim and  Brodlie [8, 9] discussed the modified quadratic Shepard method, which interpolates scattered data of any dimensionality and can be constrained to preserve positivity and more general constraint.In this paper, we show how radial basis functions method, which interpolates or approximates scattered data, can be constrained to preserve positivity.


## 2. Radial Basis Functions

A radial basis function (RBF) is a relatively simple multivariate function generated by a univariate function. Due to its simple form and good approximation behavior, the radial basis function approach has become an effective tool for multivariate scattered data interpolation during the last two decades [10–14].For any given scattered data(xj,fj)∈ℝs×ℝ,j=1,…,m, where points x1,…,xm∈ℝs are pairwise distinct, the so-called radial basis function interpolation is to use a function ϕ:ℝ+→ℝ to construct the interpolant in the form of (2.1)s(x)=∑j=1mλjϕ(∥x-xj∥),
satisfying(2.2)s(xi)=∑j=1mλjϕ(∥xi-xj∥)=fi,i=1,…,m.The positive definiteness ofϕ guarantees that the above interpolation problem (2.2) possesses a unique solution and refers to ϕ as a classical radial basis function. If ϕ has compact support, then the positive definite linear system is sparse and reduces computational cost greatly. Thus, we bypass this problem by restricting ϕ to have compact support.Compactly supported radial basis functions (CSRBFs) have only recently been constructed. Wu first constructed a broad variety of CSRBF [15]. Shortly after this, Wendland constructed these functions such that they possess the lowest degree among all CSRBFs which are positive definiteness for given space dimension and prescribed order of smoothness [16]. They are radial basis functions which are positive definite on ℝs for a given space dimension s (PDs), belong to a prescribed smoothness class (C2k), are compactly supported and easy to evaluate. Some examples of such radial basis functions are given in Table 1.Table 1
Some of Wendland's CSRBFϕs,k∈PDs∩C2k.
ϕ1,0=(1-r)+,PD1∩C0ϕ3,0=(1-r)+2,PD3∩C0ϕ3,1=(1-r)+4(4r+1),PD3∩C2It is a useful property and provides a good selection of Wendland's functions with respect to the order of continuity and the dimension of space. Thus, CSRBFs have become a popular tool for multivariate interpolation of large scattered data [17, 18].In order to adapt the interpolation to scattered data of different densities, it is necessary to be able to scale the support ofϕ. So from now on we assume that the radius α of support of ϕ is one and replace ϕ by (2.3)ϕα(·)=ϕ(·α),forα>0.Meanwhile, in order to achieve both the best possible approximation behavior and best possible stability with respect to the support of CSRBF, we adopt the strategy to choose the radiusα as done in paper [17] throughout this paper.


## 3. Positive Approximation for Positive Data

The problem we are addressing is the following. Given a set ofm scattered data xi,xi∈ℝs with associated data values fi,i=1,2,…,m, where fi≥0, we seek an optimal approximating function F(x) such that F(x)≥0 in least-squares sense.we first construct the functionF(x) as follows:(3.1)F(x)=∑i=1Nλiϕα(∥x-ci∥),
where ϕα(∥x-ci∥) is a compactly supported radial basis function centered on ci with radius α of support. Usually, the number of N is less than m greatly and centers ci are different from data points xi.Thus, the so-called positive approximation for positive data is reduced to solve the following optimization problem(3.2)min∑j=1m(F(xj)-fj)2,subjecttoF(x)≥0.Note that allϕα(∥x-ci∥) are positive and F(x) is a linear combination of ϕα(∥x-ci∥). So, we can restrict each λi to be positive in order to guarantee the function to be everywhere positive. This sufficient condition is the kernel idea of our proposed method.Therefore, the problem of positive approximation is transformed into a quadratic optimization problem subjected to linear constraints(3.3)min∑j=1m(F(xj)-fj)2,subjecttoλ1≥0,…,λN≥0.Without loss of generality, we illustrate it with a very simple example in 1D.Example 3.1.
The set of 7 data points in Table2 shows the velocity of wind. The velocity is inherently positive, and we therefore require the resulted approximating function to preserve this property.   Here, we choose the Wendland's function as ϕ(r)=(1-r)+4(4r+1). Figure 1 shows the positive approximation curve applied to the set of data for the velocity of wind using our proposed method (3.3) when ci are chosen the same as xi.    Table 3 shows the values of Error=∑j=17(F(xj)-fj)2 when the number of centers N is varied. Of course, the total error will become less if the centers ci are chosen properly.Table 2
One dimensional data for the velocity of wind.
Times (min)00.250.511.21.82Velocity (km/min)20.80.50.110.51Table 3
Total error for different parametric values ofN.
N3579Error6.24×10-18.37×10-25.04×10-27.80×10-3Figure 1
Positive approximation curve for data of wind velocity.Remark 3.2.
The proposed method has a good chance to work well if the data are coming from a functionf which is a convolution of the kernel with a positive function g, because then f can be recovered well by an integration formula which has exactly the form of (3.1).


## 4. Positive Interpolation for Positive Data

The problem of positive interpolation we are addressing is the following. Given a set ofm scattered data xi,xi∈ℝs with associated data values fi,i=1,2,…,m, where fi≥0, the so-called positive interpolation is to construct a function F(x) such that F(xi)=fi,i=1,…,m and F(x)≥0, where F(x) is a linear combination of the CSRBF.The basic idea is also to restrict each combination coefficientλi to be positive in order to guarantee that F(x) is positive everywhere. Obviously, classical RBF interpolation (2.2) cannot guarantee that all λi are positive.One feasible way is to choosen new added data yi,i=m+1,…,m+n and then turn to find the following interpolant:(4.1)F(x)=∑i=1mλiϕα(∥x-xi∥)+∑j=m+1m+nλjϕβj(∥x-yj∥)
such that(4.2)F(xi)=fi,i=1,2,…,m,λi≥0,i=1,2,…,m+n.The above interpolant will naturally arise an inevitable problem: what makes the system of linear equations (4.1) have a unique solution F(x) satisfying the linear constraints. In order to solve it in special cases, we require the following lemma.Lemma 4.1 (see [19, Gordan's Theorem]).
LetA1,A2,…,Am be n-dimensional vectors; there does not exist a vector P such that AiTP<0 if and only if there exist nonnegative real numbers λ1,λ2,…,λm such that ∑i=1mλiAi=0.Undoubtedly, it is hard to give a general result which can determine whether there exists a solution when the added centersyj and the radius βj are chosen randomly. Thus, we discuss the following special case to choose centers yj and the radius βj.For each dataxi,i=1,…,m, if we choose the new added data yi in the neighborhood of xi randomly and choose the radius βi such that the influence domain of ϕβi(∥x-yi∥) only contains the data xi, then for this case we have the following.Theorem 4.2.
If the new added datayj and radius βj are chosen as above, then there exists a solution subjected to the constraints (4.2).Proof.
Let(4.3)AjT=-{ϕβj(∥xi-yj∥)}i=1m=(0,…,0,-bj,0,…,0),j=m+1,…,2m,AjT=-{ϕα(∥xi-xj∥)}i=1m,j=1,2,…,m,A2m+1T=(f1,…,fm),∀fi≥0,
where bj,j=m+1,…,2m, are positive real numbers.
It is easy to see that there does not exist a vectorP such that AiTP<0,i=m+1…,2m+1. According to Gordon lemma, we know that there exist nonnegative real numbers λ1,λ2,…,λ2m+1 such that ∑i=12m+1λiAi=0 and λ2m+1>0.
We naturally wish that there are many zero coefficientsλj,j=m+1,…,m+n, in the formulas (4.1). That is to say, we add as few data as possible. For example, if the original interpolation function is positive, then we certainly need not add any new data. So from now on we hope to minimize the objective function sgn(λm+1)+⋯+sgn(λ2m), where sgn(·) denotes the sign function.
Therefore, an approach is presented to compute the positive interpolation by solving the following optimization problem:(4.4)min(sgn(λm+1)+⋯+sgn(λ2m)),subjectto{F(xi)=fi,i=1,2,…,m,λi≥0,i=1,2,…,2m.
We illustrate it with an example using the same data given in Table2 and make comparisons with several existing methods.Example 4.3 (Example3.1 is continued).
In Figure2, we show the original interpolation curve by using CSRBF without the constraint of positivity. Generally, the curve has good approximation behavior, but the curve goes beyond the range of the data values which makes physical nonsense and indeed the positivity is violated.Figure 2
One-dimensional data for the velocity of wind—CSRBF interpolation loses positivity.In Figure3, the positive curve applied to the same set of positive data using piecewise cubic method [8] is shown. Meanwhile, we reveal the positive curve using constrained modified quadratic Shepard method (CMQS) [9] in Figure 4.Figure 3
Positive interpolation curve for data of wind velocity using piecewise cubic.Figure 4
Positive interpolation curve for data of wind velocity using CMQS.By contrast, in Figure5, we show the positive interpolation curve applied to the same data of wind velocity using our proposed approach (4.1). From the experiment, the constructed curve possesses relatively good approximation behavior in contrast to piecewise cubic method and constrained modified quadratic Shepard method.Figure 5
Positive interpolation curve for positive data.Remark 4.4.
It is pointed out that we generally add corresponding new dataym+k if fk is the minimal data among all value fi,i=1,…,m instead of adding m new data directly to solve the positive interpolation in practical use.


## 5. Numerical Example

The strong and sufficient condition that allλi are positive may degrade the quality of the interpolating function, in comparison with the original unconstrained CSRBF interpolation. We evaluate the quality of the new interpolant by calculating the variances between the exact and calculated values on a set of test points by the following experiment in 2D.Example 5.1.
We illustrate it with the following functionS(x,y) [9] which is defined as:
(5.1)S(x,y)={1,if(y-x)≥0.5,2(y-x),if0.5≥(y-x)≥0,cos(4πr)+12,ifr≤14,0,otherwise,
where r=(x-1.5)2+(y-0.5)2.
The interpolated functionS(x,y) is shown in Figure 6. Meanwhile, we show the positive surface generated by our proposed method at a random set of 100 points in Figure 7.
In order to measure the quality of new interpolant, we carry out the following experiment. Firstly, we construct two interpolants by constrained modified quadratic Shepard method and our proposed method, based on a series of data sets where the number of randomly chosen points increases. Secondly, we evaluate the interpolants on a grid of25×25 points and calculate the variances between the exact and calculated values. The results are shown in Table 4.Table 4
Variances for two interpolants forS(x,y).
Number of data points3060100150250CMQS1.541.200.970.540.11Our proposed method2.321.971.550.970.24Figure 6
Interpolated functionS(x,y).Figure 7
Positive interpolating surface forS(x,y).


## 6. Conclusion

Positivity preserving interpolation is an interesting work. In this paper, we discuss the approximation and interpolation problem of scattered data by using CSRBF under the constraint of positivity. The approaches are presented to compute positive approximation and interpolation by solving the two corresponding optimization problems.However, we have not discussed how to select the optimal number and position of the new added datayi in order to both achieve the existence and better possible approximation behavior of interpolation. These problems would be attractive and remain to be our future work.



---

*Source: 964528-2010-05-10.xml*