Namespaces
Variants
Actions

Difference between revisions of "Radial basis function"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX encoding is done)
 
Line 1: Line 1:
The radial basis function method is a multi-variable scheme for function interpolation, i.e. the goal is to approximate a [[Continuous function|continuous function]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r1300201.png" /> by a relatively simple interpolant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r1300202.png" /> which meets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r1300203.png" /> at a certain number (usually finite) of prescribed points (cf. also [[Approximation of functions|Approximation of functions]]; [[Interpolation|Interpolation]]). In the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r1300204.png" />-dimensional real space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r1300205.png" />, given a continuous function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r1300206.png" /> and so-called centres <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r1300207.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r1300208.png" /> the interpolant to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r1300209.png" /> at the centres reads
+
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002010.png" /></td> </tr></table>
+
The radial basis function method is a multi-variable scheme for function interpolation, i.e. the goal is to approximate a [[Continuous function|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|Approximation of functions]]; [[Interpolation|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}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002011.png" /> is the radial basis function, the norm is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002012.png" />-dimensional Euclidean norm and the real coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002013.png" /> are fixed through the interpolation conditions
+
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.  
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002014.png" /></td> </tr></table>
+
Examples of radial basis functions are the multi-quadric function $\phi(r)=\sqrt{r^2+c^2}$, $c$ a positive parameter [[#References|[a7]]], which is known to be particularly useful in applications, the thin-plate spline $\phi(r)=r^2\log(r)$ [[#References|[a6]]], the Gaussian function $\phi(r)=\exp(-c^2r^2)$, and the linear radial basis function $\phi(r)=r$.  
  
Norms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002015.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002017.png" /> a positive parameter [[#References|[a7]]], which is known to be particularly useful in applications, the thin-plate spline <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002018.png" /> [[#References|[a6]]], the Gaussian function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002019.png" />, and the linear radial basis function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002020.png" />. For the thin-plate spline and several other radial basis functions, a linear (generally, low-order) polynomial has to be added to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002021.png" /> with side conditions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002022.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002024.png" /> if the centres are distinct [[#References|[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) [[#References|[a9]]], which means that it is positive (negative) definite on a subspace of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002025.png" /> with small co-dimension.
+
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 [[#References|[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) [[#References|[a9]]], which means that it is positive (negative) definite on a subspace of $\mathbb R^m$ with small co-dimension.
  
 
See, for instance, [[#References|[a10]]] or [[#References|[a5]]] for reviews of this method. For the history of the method see [[#References|[a7]]].
 
See, for instance, [[#References|[a10]]] or [[#References|[a5]]] for reviews of this method. For the history of the method see [[#References|[a7]]].
  
Besides the question of existence and uniqueness outlined above, the question of (uniform) convergence (cf. also [[Uniform convergence|Uniform convergence]]) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002026.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002027.png" /> when the centres become dense in a domain or on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002028.png" /> is of central importance. J. Duchon [[#References|[a6]]] has studied this issue for scattered centres <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002029.png" /> in a Lipschitz domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002030.png" /> for thin-plate splines and proved uniform convergence provided <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002031.png" /> satisfies a cone condition, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002032.png" /> become dense in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002034.png" /> is sufficiently smooth. His work was generalized to multi-quadrics, Gaussians and others (see, for instance [[#References|[a13]]], [[#References|[a8]]]), while the question of uniform convergence and approximation order on infinite square grids of spacing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002035.png" /> was settled in [[#References|[a2]]]. Estimates for the interpolation error when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002036.png" /> have been given (see [[#References|[a2]]]) and provide error bounds of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002037.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002038.png" /> dimensions for the linear radial basis function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002039.png" />, for example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002040.png" /> is sufficiently smooth.
+
Besides the question of existence and uniqueness outlined above, the question of (uniform) convergence (cf. also [[Uniform convergence|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 [[#References|[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 [[#References|[a13]]], [[#References|[a8]]]), while the question of uniform convergence and approximation order on infinite square grids of spacing $h>0$ was settled in [[#References|[a2]]]. Estimates for the interpolation error when $h\to 0$ have been given (see [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002041.png" /> 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|Algebraic polynomial of best approximation]]), are often ruled out.
+
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|Algebraic polynomial of best approximation]]), are often ruled out.
  
Since most of the radial basis functions are globally supported (however, see [[#References|[a12]]] or [[#References|[a4]]] for compactly supported ones), special attention is needed in the computation of the approximants, in particular if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002042.png" /> is large. Major contributions to this aspect can be found in [[#References|[a11]]] and [[#References|[a1]]], which include working software admitting efficient computation of the desired coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002043.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002044.png" /> and larger. Thin-plate splines and multi-quadrics for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002045.png" /> have also received consideration in implementations.
+
Since most of the radial basis functions are globally supported (however, see [[#References|[a12]]] or [[#References|[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 [[#References|[a11]]] and [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002046.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r130/r130020/r13002047.png" />, other approximation schemes (not interpolation) such as wavelet schemes [[#References|[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 [[#References|[a7]]] to optimization problems and applications in the numerical solutions of partial differential equations in high dimensions.
+
Given the accuracy and availability of the methods for arbitrary $n$ and $m$, other approximation schemes (not interpolation) such as wavelet schemes [[#References|[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 [[#References|[a7]]] to optimization problems and applications in the numerical solutions of partial differential equations in high dimensions.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.D. Buhmann,  "Multivariate cardinal-interpolation with radial-basis functions"  ''Constructive Approx.'' , '''6'''  (1990)  pp. 225–255</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  M.D. Buhmann,  "Multiquadric pre-wavelets on non-equally spaced knots in one dimension"  ''Math. Comput.'' , '''64'''  (1995)  pp. 1611–1625</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  M.D. Buhmann,  "Radial functions on compact support"  ''Proc. Edinburgh Math. Soc.'' , '''41'''  (1998)  pp. 33–46</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M.D. Buhmann,  "Radial basis functions"  ''Acta Numerica'' , '''9'''  (2000)  pp. 1–38</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  R.L. Hardy,  "Theory and applications of the multiquadric-biharmonic method"  ''Computers Math. Appl.'' , '''19'''  (1990)  pp. 163–208</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  C.A. Micchelli,  "Interpolation of scattered data: distance matrices and conditionally positive definite functions"  ''Constructive Approx.'' , '''1'''  (1986)  pp. 11–22</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  M.J.D. Powell,  "A new iterative method for thin plate spline interpolation in two dimensions"  ''Ann. Numer. Math.'' , '''4'''  (1997)  pp. 519–527</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  H. Wendland,  "Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree"  ''Adv. Comput. Math.'' , '''4''' :  10  (1995)  pp. 389–396</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  Z. Wu,  R. Schaback,  "Local error estimates for radial basis function interpolation of scattered data"  ''IMA J. Numer. Anal.'' , '''13'''  (1993)  pp. 13–27</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.D. Buhmann,  "Multivariate cardinal-interpolation with radial-basis functions"  ''Constructive Approx.'' , '''6'''  (1990)  pp. 225–255</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  M.D. Buhmann,  "Multiquadric pre-wavelets on non-equally spaced knots in one dimension"  ''Math. Comput.'' , '''64'''  (1995)  pp. 1611–1625</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  M.D. Buhmann,  "Radial functions on compact support"  ''Proc. Edinburgh Math. Soc.'' , '''41'''  (1998)  pp. 33–46</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M.D. Buhmann,  "Radial basis functions"  ''Acta Numerica'' , '''9'''  (2000)  pp. 1–38</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  R.L. Hardy,  "Theory and applications of the multiquadric-biharmonic method"  ''Computers Math. Appl.'' , '''19'''  (1990)  pp. 163–208</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  C.A. Micchelli,  "Interpolation of scattered data: distance matrices and conditionally positive definite functions"  ''Constructive Approx.'' , '''1'''  (1986)  pp. 11–22</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  M.J.D. Powell,  "A new iterative method for thin plate spline interpolation in two dimensions"  ''Ann. Numer. Math.'' , '''4'''  (1997)  pp. 519–527</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  H. Wendland,  "Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree"  ''Adv. Comput. Math.'' , '''4''' :  10  (1995)  pp. 389–396</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  Z. Wu,  R. Schaback,  "Local error estimates for radial basis function interpolation of scattered data"  ''IMA J. Numer. Anal.'' , '''13'''  (1993)  pp. 13–27</TD></TR></table>

Latest revision as of 15:13, 18 February 2013


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
How to Cite This Entry:
Radial basis function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Radial_basis_function&oldid=11997
This article was adapted from an original article by Martin Buhmann (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article