Radial basis function

The radial basis function method is a multi-variable scheme for function interpolation, i.e. the goal is to approximate a continuous function $f$ by a relatively simple interpolant $s$ which meets $f$ at a certain number (usually finite) of prescribed points (cf. also Approximation of functions; Interpolation). In the $n$-dimensional real space $\mathbb R^n$, given a continuous function $f:\mathbb{R}^n\to\mathbb R$ and so-called centres $x_j\in\mathbb R^n$, $j=1,2,\dots,m$ the interpolant to $f$ at the centres reads \begin{equation} s(x)=\sum\limits_{j=1}^m\lambda_j\phi(\|x-x_j\|),\quad x\in\mathbb R^n, \end{equation} where $\phi:\mathbb R_+\to\mathbb R$ is the radial basis function, the norm is the $n$-dimensional Euclidean norm and the real coefficients $\lambda_j$ are fixed through the interpolation conditions \begin{equation} s(x_j)=f(x_j),\quad j=1,\dots,m. \end{equation}

Norms $\|\cdot\|$ other than Euclidean are possible in principle, but rarely used. In particular, the remarkable existence properties described below are usually no longer guaranteed if the norm is not Euclidean.

Examples of radial basis functions are the multi-quadric function $\phi(r)=\sqrt{r^2+c^2}$, $c$ a positive parameter [a7], which is known to be particularly useful in applications, the thin-plate spline $\phi(r)=r^2\log(r)$ [a6], the Gaussian function $\phi(r)=\exp(-c^2r^2)$, and the linear radial basis function $\phi(r)=r$.

For the thin-plate spline and several other radial basis functions, a linear (generally, low-order) polynomial has to be added to $s$ with side conditions $\sum_{j=1}^m\lambda_j=\sum_{j=1}^m\lambda_jx_j=0$ in order to be able to solve the interpolation equations uniquely. In that case, the centres must not lie on a straight line, but may otherwise be arbitrarily distributed ( "scattered" ). For multi-quadrics, Gaussian and linear radial functions, among others, the extra geometric condition is not needed: the interpolation linear system defined through the above interpolation conditions is uniquely solvable for all $m>1$ and $n$ if the centres are distinct [a9]. This is one of the most striking and useful features of radial basis function interpolation. In fact, for large classes of radial basis functions, which contain all the examples mentioned, the matrix which defines the coefficients through the interpolation conditions is conditionally positive definite (or conditionally negative definite) [a9], which means that it is positive (negative) definite on a subspace of $\mathbb R^m$ with small co-dimension.

See, for instance, [a10] or [a5] for reviews of this method. For the history of the method see [a7].

Besides the question of existence and uniqueness outlined above, the question of (uniform) convergence (cf. also Uniform convergence) of $s$ to $f$ when the centres become dense in a domain or on $\mathbb R^n$ is of central importance. J. Duchon [a6] has studied this issue for scattered centres $x_j$ in a Lipschitz domain $\Omega\subset\mathbb R^n$ for thin-plate splines and proved uniform convergence provided $\partial\Omega$ satisfies a cone condition, the $x_j$ become dense in $\Omega$ and $f$ is sufficiently smooth. His work was generalized to multi-quadrics, Gaussians and others (see, for instance [a13], [a8]), while the question of uniform convergence and approximation order on infinite square grids of spacing $h>0$ was settled in [a2]. Estimates for the interpolation error when $h\to 0$ have been given (see [a2]) and provide error bounds of order $O(h^{n+1})$ in $n$ dimensions for the linear radial basis function $\phi(r)=r$, for example, if $f$ is sufficiently smooth.

The remarkable convergence orders which occur, together with the above existence theorems, make the radial basis function method attractive if $n$ is large, especially when the centres are scattered, because in that case other schemes, such as polynomial interpolation (cf. e.g. Algebraic polynomial of best approximation), are often ruled out.

Since most of the radial basis functions are globally supported (however, see [a12] or [a4] for compactly supported ones), special attention is needed in the computation of the approximants, in particular if $m$ is large. Major contributions to this aspect can be found in [a11] and [a1], which include working software admitting efficient computation of the desired coefficients $\lambda_j$ for $m=50000$ and larger. Thin-plate splines and multi-quadrics for $n=2,3,4$ have also received consideration in implementations.

Given the accuracy and availability of the methods for arbitrary $n$ and $m$, other approximation schemes (not interpolation) such as wavelet schemes [a3], quasi-interpolation or least-squares approaches have been studied and used successfully, but the real advantage of the scheme remains in its availability for multi-variable interpolation to scattered data. The applications range from modelling the Earth's surface [a7] to optimization problems and applications in the numerical solutions of partial differential equations in high dimensions.

References

[a1]	R.K. Beatson, L. Greengard, "A short course on fast multiple methods" M. Ainsworth (ed.) J. Levesley (ed.) M. Marletta (ed.) W. Light (ed.) , Wavelets, Multilevel Methods and Elliptic PDEs , Oxford Univ. Press (1997) pp. 1–37
[a2]	M.D. Buhmann, "Multivariate cardinal-interpolation with radial-basis functions" Constructive Approx. , 6 (1990) pp. 225–255
[a3]	M.D. Buhmann, "Multiquadric pre-wavelets on non-equally spaced knots in one dimension" Math. Comput. , 64 (1995) pp. 1611–1625
[a4]	M.D. Buhmann, "Radial functions on compact support" Proc. Edinburgh Math. Soc. , 41 (1998) pp. 33–46
[a5]	M.D. Buhmann, "Radial basis functions" Acta Numerica , 9 (2000) pp. 1–38
[a6]	J. Duchon, "Splines minimizing rotation-invariante semi-norms in Sobolev spaces" W. Schempp (ed.) K. Zeller (ed.) , Constructive Theory of Functions of Several Variables , Springer (1979) pp. 85–100
[a7]	R.L. Hardy, "Theory and applications of the multiquadric-biharmonic method" Computers Math. Appl. , 19 (1990) pp. 163–208
[a8]	W.R. Madych, S.A. Nelson, "Bounds on multivariate polynomials and exponential error estimates for multiquadric interpolation" J. Approx. Th. , 70 (1992) pp. 94–114
[a9]	C.A. Micchelli, "Interpolation of scattered data: distance matrices and conditionally positive definite functions" Constructive Approx. , 1 (1986) pp. 11–22
[a10]	M.J.D. Powell, "The theory of radial basis function approximation" W.A. Light (ed.) , Advances in Numerical Analysis II. Wavelets, Subdivision, and Radial Functions , Oxford Univ. Press (1992) pp. 105–210
[a11]	M.J.D. Powell, "A new iterative method for thin plate spline interpolation in two dimensions" Ann. Numer. Math. , 4 (1997) pp. 519–527
[a12]	H. Wendland, "Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree" Adv. Comput. Math. , 4 : 10 (1995) pp. 389–396
[a13]	Z. Wu, R. Schaback, "Local error estimates for radial basis function interpolation of scattered data" IMA J. Numer. Anal. , 13 (1993) pp. 13–27