HOME

TheInfoList



OR:

Radial basis function (RBF) interpolation is an advanced method in
approximation theory In mathematics, approximation theory is concerned with how function (mathematics), functions can best be approximation, approximated with simpler functions, and with quantitative property, quantitatively characterization (mathematics), characteri ...
for constructing high-order accurate interpolants of unstructured data, possibly in high-dimensional spaces. The interpolant takes the form of a weighted sum of
radial basis function In mathematics a radial basis function (RBF) is a real-valued function \varphi whose value depends only on the distance between the input and some fixed point, either the origin, so that \varphi(\mathbf) = \hat\varphi(\left\, \mathbf\right\, ), o ...
s. RBF interpolation is a mesh-free method, meaning the nodes (points in the domain) need not lie on a structured grid, and does not require the formation of a
mesh Medical Subject Headings (MeSH) is a comprehensive controlled vocabulary for the purpose of indexing journal articles and books in the life sciences. It serves as a thesaurus of index terms that facilitates searching. Created and updated by th ...
. It is often spectrally accurate and stable for large numbers of nodes even in high dimensions. Many interpolation methods can be used as the theoretical foundation of algorithms for approximating
linear operator In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pr ...
s, and RBF interpolation is no exception. RBF interpolation has been used to approximate
differential operator In mathematics, a differential operator is an operator defined as a function of the differentiation operator. It is helpful, as a matter of notation first, to consider differentiation as an abstract operation that accepts a function and retur ...
s, integral operators, and surface differential operators.


Examples

Let f(x) = \exp(x \cos(3 \pi x)) and let x_k = \frac, k=0, 1, \dots, 14 be 15 equally spaced points on the interval
, 1 The comma is a punctuation mark that appears in several variants in different languages. Some typefaces render it as a small line, slightly curved or straight, but inclined from the vertical; others give it the appearance of a miniature fille ...
/math>. We will form s(x) = \sum\limits_^ w_k \varphi(\, x-x_k\, ) where \varphi is a
radial basis function In mathematics a radial basis function (RBF) is a real-valued function \varphi whose value depends only on the distance between the input and some fixed point, either the origin, so that \varphi(\mathbf) = \hat\varphi(\left\, \mathbf\right\, ), o ...
, and choose w_k, k=0, 1, \dots, 14 such that s(x_k)=f(x_k), k=0, 1, \dots, 14 (s interpolates f at the chosen points). In matrix notation this can be written as : \begin \varphi(\, x_0 - x_0\, ) & \varphi(\, x_1 - x_0\, ) & \dots & \varphi(\, x_ - x_0\, ) \\ \varphi(\, x_0 - x_1\, ) & \varphi(\, x_1 - x_1\, ) & \dots & \varphi(\, x_ - x_\, ) \\ \vdots & \vdots & \ddots & \vdots \\ \varphi(\, x_0 - x_\, ) & \varphi(\, x_1 - x_\, ) & \dots & \varphi(\, x_ - x_\, ) \\ \end \beginw_0 \\ w_1 \\ \vdots \\ w_\end = \beginf(x_0) \\ f(x_1) \\ \vdots \\ f(x_)\end. Choosing \varphi(r) = \exp(-(\varepsilon r)^2), the Gaussian, with a shape parameter of \varepsilon = 3, we can then solve the matrix equation for the weights and plot the interpolant. Plotting the interpolating function below, we see that it is visually the same everywhere except near the left boundary (an example of
Runge's phenomenon In the mathematical field of numerical analysis, Runge's phenomenon () is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree over a set of equispaced interpolation ...
), where it is still a very close approximation. More precisely the maximum error is roughly \, f - s\, _\infty \approx 0.0267414 at x = 0.0220012.


Motivation

The Mairhuber–Curtis theorem says that for any open set V in \mathbb^n with n \geq 2, and f_1, f_2, \dots, f_n linearly independent functions on V, there exists a set of n points in the domain such that the interpolation matrix : \begin f_1(x_1) & f_2(x_1) & \dots & f_n(x_1) \\ f_1(x_2) & f_2(x_2) & \dots & f_n(x_2) \\ \vdots & \vdots & \ddots & \vdots \\ f_1(x_n) & f_2(x_n) & \dots & f_n(x_n) \end is
singular Singular may refer to: * Singular, the grammatical number that denotes a unit quantity, as opposed to the plural and other forms * Singular or sounder, a group of boar, see List of animal names * Singular (band), a Thai jazz pop duo *'' Singula ...
. This means that if one wishes to have a general interpolation algorithm, one must choose the basis functions to depend on the interpolation points. In 1971, Rolland Hardy developed a method of interpolating scattered data using interpolants of the form s(\mathbf) = \sum\limits_^N \sqrt. This is interpolation using a basis of shifted multiquadric functions, now more commonly written as \varphi(r) = \sqrt, and is the first instance of radial basis function interpolation. It has been shown that the resulting interpolation matrix will always be non-singular. This does not violate the Mairhuber–Curtis theorem since the basis functions depend on the points of interpolation. Choosing a radial kernel such that the interpolation matrix is non-singular is exactly the definition of a strictly positive definite function. Such functions, including the Gaussian, inverse quadratic, and inverse multiquadric are often used as radial basis functions for this reason.


Shape-parameter tuning

Many radial basis functions have a parameter that controls their relative flatness or peakedness. This parameter is usually represented by the symbol \varepsilon with the function becoming increasingly flat as \varepsilon \to 0. For example, Rolland Hardy used the formula \varphi(r) = \sqrt for the multiquadric, however nowadays the formula \varphi(r) = \sqrt is used instead. These formulas are equivalent up to a scale factor. This factor is inconsequential since the
basis vectors In mathematics, a set of elements of a vector space is called a basis (: bases) if every element of can be written in a unique way as a finite linear combination of elements of . The coefficients of this linear combination are referred to as ...
have the same span and the interpolation weights will compensate. By convention, the basis function is scaled such that \varphi(0) = 1 as seen in the plots of the
Gaussian function In mathematics, a Gaussian function, often simply referred to as a Gaussian, is a function (mathematics), function of the base form f(x) = \exp (-x^2) and with parametric extension f(x) = a \exp\left( -\frac \right) for arbitrary real number, rea ...
s and the
bump function In mathematical analysis, a bump function (also called a test function) is a function f : \Reals^n \to \Reals on a Euclidean space \Reals^n which is both smooth (in the sense of having continuous derivatives of all orders) and compactly supp ...
s. File:Gaussian function shape parameter.png, A
Gaussian function In mathematics, a Gaussian function, often simply referred to as a Gaussian, is a function (mathematics), function of the base form f(x) = \exp (-x^2) and with parametric extension f(x) = a \exp\left( -\frac \right) for arbitrary real number, rea ...
for several choices of \varepsilon File:Bump function shape.png, A plot of the scaled
bump function In mathematical analysis, a bump function (also called a test function) is a function f : \Reals^n \to \Reals on a Euclidean space \Reals^n which is both smooth (in the sense of having continuous derivatives of all orders) and compactly supp ...
with several choices of shape parameter
A consequence of this choice is that the interpolation matrix approaches the identity matrix as \varepsilon \to \infty leading to stability when solving the matrix system. The resulting interpolant will in general be a poor approximation to the function since it will be near zero everywhere, except near the interpolation points where it will sharply peakthe so-called "bed-of-nails interpolant" (as seen in the plot to the right). On the opposite side of the spectrum, the
condition number In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the inpu ...
of the interpolation matrix will diverge to infinity as \varepsilon \to 0 leading to ill-conditioning of the system. In practice, one chooses a shape parameter so that the interpolation matrix is "on the edge of ill-conditioning" (eg. with a condition number of roughly 10^ for
double-precision Double-precision floating-point format (sometimes called FP64 or float64) is a floating-point number format, usually occupying 64 bits in computer memory; it represents a wide range of numeric values by using a floating radix point. Double prec ...
floating point). There are sometimes other factors to consider when choosing a shape-parameter. For example the
bump function In mathematical analysis, a bump function (also called a test function) is a function f : \Reals^n \to \Reals on a Euclidean space \Reals^n which is both smooth (in the sense of having continuous derivatives of all orders) and compactly supp ...
\varphi(r) = \begin \exp\left( -\frac\right) & \mbox r<\frac \\ 0 & \mbox \end has a
compact support In mathematics, the support of a real-valued function f is the subset of the function domain of elements that are not mapped to zero. If the domain of f is a topological space, then the support of f is instead defined as the smallest closed ...
(it is zero everywhere except when r< \tfrac) leading to a sparse interpolation matrix. Some radial basis functions such as the
polyharmonic spline In applied mathematics, polyharmonic splines are used for function approximation and data interpolation. They are very useful for interpolating and fitting scattered data in many dimensions. Special cases include thin plate splines and natural c ...
s have no shape-parameter.


See also

*
Kriging In statistics, originally in geostatistics, kriging or Kriging (), also known as Gaussian process regression, is a method of interpolation based on Gaussian process governed by prior covariances. Under suitable assumptions of the prior, kriging g ...


References

{{reflist Numerical analysis Approximation theory Interpolation