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 cubic splines in one dimension.
Definition
A polyharmonic spline is a linear combination of polyharmonic radial basis functions (RBFs) denoted by plus a polynomial term:
where
( denotes matrix transpose, meaning is a column vector) is a real-valued vector of independent variables, are vectors of the same size as (often called centers) that the curve or surface must interpolate, are the weights of the RBFs, are the weights of the polynomial.
The polynomial with the coefficients improves fitting accuracy for polyharmonic smoothing splines and also improves extrapolation away from the centers See figure below for comparison of splines with polynomial term and without polynomial term.
The polyharmonic RBFs are of the form:
Other values of the exponent are not useful (such as ), because a solution of the interpolation problem might not exist. To avoid problems at (since ), the polyharmonic RBFs with the natural logarithm might be implemented as:
or, more simply adding a continuity extension in
The weights and are determined such that the function interpolates given points (for ) and fulfills the orthogonality conditions
All together, these constraints are equivalent to the symmetric linear system of equations
where
In order for this system of equations to have a unique solution, must be full rank. is full rank for very mild conditions on the input data. For example, in two dimensions, three centers forming a non-degenerate triangle ensure that is full rank, and in three dimensions, four centers forming a non-degenerate tetrahedron ensure that B is full rank. As explained later, the linear transformation resulting from the restriction of the domain of the linear transformation to the null space of is positive definite. This means that if is full rank, the system of equations () always has a unique solution and it can be solved using a linear solver specialised for symmetric matrices. The computed weights allow evaluation of the spline for any using equation (). Many practical details of implementing and using polyharmonic splines are explained in Fasshauer. In Iske polyharmonic splines are treated as special cases of other multiresolution methods in scattered data modelling.
Discussion
The main advantage of polyharmonic spline interpolation is that usually very good interpolation results are obtained for scattered data without performing any "tuning", so automatic interpolation is feasible. This is not the case for other radial basis functions. For example, the Gaussian function needs to be tuned, so that is selected according to the underlying grid of the independent variables. If this grid is non-uniform, a proper selection of to achieve a good interpolation result is difficult or impossible.
Main disadvantages are:
To determine the weights, a dense linear system of equations must be solved. Solving a dense linear system becomes impractical if the dimension is large, since the memory required is and the number of operations required is Evaluating the computed polyharmonic spline function at data points requires operations. In many applications (image processing is an example), is much larger than and if both numbers are large, this is not practical.
Fast construction and evaluation methods
One straightforward approach to speeding up model construction and evaluation is to use a subset of nearest interpolation nodes to build a local model every time we evaluate the spline. As a result, the total time needed for model construction and evaluation at points changes from to . This can yield better timings if is much less than . Such an approach is advocated by some software libraries, the most notable being scipy.interpolate.RBFInterpolator. The main drawback is that it introduces small discontinuities in the spline and requires problem-specific tuning: a proper choice of the neighbors count, . Recently, methods have been developed to overcome the aforementioned difficulties without sacrificing main advantages of polyharmonic splines.
First, a bunch of methods for fast evaluation were proposed:
Beatson et al. present a method to interpolate polyharmonic splines with being a basis function at one point in 3 dimensions or less Cherrie et al. present a method to interpolate polyharmonic splines with as a basis function at one point in 4 dimensions or less