Polyharmonic Spline - Discussion

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 k is selected according to the underlying grid of the independent variables. If this grid is non-uniform, a proper selection of k to achieve a good interpolation result is difficult or impossible.

Main disadvantages are:

• To determine the weights, a linear system of equations must be solved, which is non-sparse. The solution of a non-sparse linear system becomes no longer practical if the dimension n is larger as about 1000 (since the storage requirements are O(n2) and the number of operations to solve the linear system is O(n3). For example n=10000 requires about 100 Mbyte of storage and 1000 Gflops of operations).

• To perform the interpolation of M data points requires operations in the order of O(M*N). In many applications, like image processing, M is much larger than N, and if both numbers are large, this is no longer practical.

Recently, methods have been developed to overcome the aforementioned difficulties. For example Beatson et.al. present a method to interpolate polyharmonic splines at one point in 3 dimensions in O(log(N)) instead of O(N).