An error analysis for radial basis function interpolation

Summary. Radial basis function interpolation refers to a method of interpolation which writes the interpolant to some given data as a linear combination of the translates of a single function and a low degree polynomial. We develop an error analysis which works well when the Fourier transform of has a pole of order 2m at the origin and a zero at of order 2. In case 0m, we derive error estimates which fill in some gaps in the known theory; while in case m> we obtain previously unknown error estimates. In this latter case, we employ dilates of the function , where the dilation factor corresponds to the fill distance between the data points and the domain.Mathematics Subject Classification (1991): 41A05, 41A25, 65D05, 41A63Revised version received December 17, 2003     

Error estimates for matrix-valued radial basis function interpolation

We introduce a class of matrix-valued radial basis functions (RBFs) of compact support that can be customized, e.g. chosen to be divergence-free. We then derive and discuss error estimates for interpolants and derivatives based on these matrix-valued RBFs.     

Better bases for radial basis function interpolation problems

Radial basis function interpolation involves two stages. The first is fitting, solving a linear system corresponding to the interpolation conditions. The second is evaluation. The systems occurring in fitting problems are often very ill-conditioned. Changing the basis in which the radial basis function space is expressed can greatly improve the conditioning of these systems resulting in improved accuracy, and in the case of iterative methods, improved speed, of solution. The change of basis can also improve the accuracy of evaluation by reducing loss of significance errors. In this paper new bases for the relevant space of approximants, and associated preconditioning schemes are developed which are based on Floater’s mean value coordinates. Positivity results and scale independence results are shown for schemes of a general type. Numerical results show that the given preconditioning scheme usually improves conditioning of polyharmonic spline and multiquadric interpolation problems in R² and R³ by several orders of magnitude. The theory indicates that using the new basis elements (evaluated indirectly) for both fitting and evaluation will reduce loss of significance errors on evaluation. Numerical experiments confirm this showing that such an approach can improve overall accuracy by several significant figures.     

A discrete adapted hierarchical basis solver for radial basis function interpolation

In this paper we develop a discrete Hierarchical Basis (HB) to efficiently solve the Radial Basis Function (RBF) interpolation problem with variable polynomial degree. The HB forms an orthogonal set and is adapted to the kernel seed function and the placement of the interpolation nodes. Moreover, this basis is orthogonal to a set of polynomials up to a given degree defined on the interpolating nodes. We are thus able to decouple the RBF interpolation problem for any degree of the polynomial interpolation and solve it in two steps: (1) The polynomial orthogonal RBF interpolation problem is efficiently solved in the transformed HB basis with a GMRES iteration and a diagonal (or block SSOR) preconditioner. (2) The residual is then projected onto an orthonormal polynomial basis. We apply our approach on several test cases to study its effectiveness.     

Inverse and saturation theorems for radial basis function interpolation

While direct theorems for interpolation with radial basis functions are intensively investigated, little is known about inverse theorems so far. This paper deals with both inverse and saturation theorems. For an inverse theorem we especially show that a function that can be approximated sufficiently fast must belong to the native space of the basis function in use. In case of thin plate spline interpolation we also give certain saturation theorems.

     

Near-optimal data-independent point locations for radial basis function interpolation

The goal of this paper is to construct data-independent optimal point sets for interpolation by radial basis functions. The interpolation points are chosen to be uniformly good for all functions from the associated native Hilbert space. To this end we collect various results on the power function, which we use to show that good interpolation points are always uniformly distributed in a certain sense. We also prove convergence of two different greedy algorithms for the construction of near-optimal sets which lead to stable interpolation. Finally, we provide several examples. AMS subject classification 41A05, 41063, 41065, 65D05, 65D15This work has been done with the support of the Vigoni CRUI-DAAD programme, for the years 2001/2002, between the Universities of Verona and Göttingen.     

Error estimates and condition numbers for radial basis function interpolation

For interpolation of scattered multivariate data by radial basis functions, an “uncertainty relation” between the attainable error and the condition of the interpolation matrices is proven. It states that the error and the condition number cannot both be kept small. Bounds on the Lebesgue constants are obtained as a byproduct. A variation of the Narcowich-Ward theory of upper bounds on the norm of the inverse of the interpolation matrix is presented in order to handle the whole set of radial basis functions that are currently in use.     

Error estimates and condition numbers for radial basis function interpolation

For interpolation of scattered multivariate data by radial basis functions, an “uncertainty relation” between the attainable error and the condition of the interpolation matrices is proven. It states that the error and the condition number cannot both be kept small. Bounds on the Lebesgue constants are obtained as a byproduct. A variation of the Narcowich-Ward theory of upper bounds on the norm of the inverse of the interpolation matrix is presented in order to handle the whole set of radial basis functions that are currently in use.     

Adaptive radial basis function interpolation using an error indicator

In some approximation problems, sampling from the target function can be both expensive and time-consuming. It would be convenient to have a method for indicating where approximation quality is poor, so that generation of new data provides the user with greater accuracy where needed. In this paper, we propose a new adaptive algorithm for radial basis function (RBF) interpolation which aims to assess the local approximation quality, and add or remove points as required to improve the error in the specified region. For Gaussian and multiquadric approximation, we have the flexibility of a shape parameter which we can use to keep the condition number of interpolation matrix at a moderate size. Numerical results for test functions which appear in the literature are given for dimensions 1 and 2, to show that our method performs well. We also give a three-dimensional example from the finance world, since we would like to advertise RBF techniques as useful tools for approximation in the high-dimensional settings one often meets in finance.     

Stationary binary subdivision schemes using radial basis function interpolation

A new family of interpolatory stationary subdivision schemes is introduced by using radial basis function interpolation. This work extends earlier studies on interpolatory stationary subdivision schemes in two aspects. First, it provides a wider class of interpolatory schemes; each 2L-point interpolatory scheme has the freedom of choosing a degree (say, m) of polynomial reproducing. Depending on the combination (2L,m), the proposed scheme suggests different subdivision rules. Second, the scheme turns out to be a 2L-point interpolatory scheme with a tension parameter. The conditions for convergence and smoothness are also studied. Dedicated to Prof. Charles A. Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 41A05, 41A25, 41A30, 65D10, 65D17. Byung-Gook Lee: This work was done as a part of Information & Communication fundamental Technology Research Program supported by Ministry of the Information & Communication in Republic of Korea. Jungho Yoon: Corresponding author. Supported by the Korea Science and Engineering Foundation grant (KOSEF R06-2002-012-01001).     

Local error estimates for radial basis function interpolation of scattered data

Introducing a suitable variational formulation for the localerror of scattered data interpolation by radial basis functions(r), the error can be bounded by a term depending on the Fouriertransform of the interpolated function f and a certain ‘Krigingfunction’, which allows a formulation as an integral involvingthe Fourier transform of . The explicit construction of locallywell-behaving admissible coefficient vectors makes the Krigingfunction bounded by some power of the local density h of datapoints. This leads to error estimates for interpolation of functionsf whose Fourier transform f is ‘dominated’ by thenonnegative Fourier transform of (x) = (||x||) in the sense . Approximation orders are arbitrarily high for interpolationwith Hardy multiquadrics, inverse multiquadrics and Gaussiankernels. This was also proven in recent papers by Madych andNelson, using a reproducing kernel Hilbert space approach andrequiring the same hypothesis as above on f, which limits thepractical applicability of the results. This work uses a differentand simpler analytic technique and allows to handle the casesof interpolation with (r) = r^s for s R, s > 1, s 2N, and(r) = r^s log r for s 2N, which are shown to have accuracy O(h^s/2)     

Locality properties of radial basis function expansion coefficients for equispaced interpolation

Natasha Flyer ^{Many types of radial basis functions (RBFs) are global in termsof having large magnitude across the entire domain. Yet, incontrast, e.g. with expansions in orthogonal polynomials, RBFexpansions exhibit a strong property of locality with regardto their coefficients. That is, changing a single data valuemainly affects the coefficients of the RBFs which are centredin the immediate vicinity of that data location. This localityfeature can be advantageous in the development of fast and well-conditionediterative RBF algorithms. With this motivation, we employ hereboth analytical and numerical techniques to derive the decayrates of the expansion coefficients for cardinal data, in both1D and 2D. Furthermore, we explore how these rates vary in theinteresting high-accuracy limit of increasingly flat RBFs.}     

Rational radial basis function interpolation with applications to antenna design

Functions with poles occur in many branches of applied mathematics which involve resonance phenomena. Such functions are challenging to interpolate, in particular in higher dimensions. In this paper we develop a technique for interpolation with quotients of two radial basis function (RBF) expansions to approximate such functions as an alternative to rational approximation. Since the quotient is not uniquely determined we introduce an additional constraint, the sum of the RBF-norms of the numerator and denominator squared should be minimal subjected to a norm condition on the function values. The method was designed for antenna design applications and we show by examples that the scattering matrix for a patch antenna as a function of some design parameters can be approximated accurately with the new method. In many cases, e.g. in antenna optimization, the function evaluations are time consuming, and therefore it is important to reduce the number of evaluations but still obtain a good approximation. A sensitivity analysis of the new interpolation technique is carried out and it gives indications how efficient adaptation methods could be devised. A family of such methods are evaluated on antenna data and the results show that much performance can be gained by choosing the right method.     

Rotorcraft parameter estimation using radial basis function neural network

Increased emphasis on rotorcraft performance and operational capabilities has resulted in accurate computation of aerodynamic stability and control parameters. System identification is one such tool in which the model structure and parameters such as aerodynamic stability and control derivatives are derived. In the present work, the rotorcraft aerodynamic parameters are computed using radial basis function neural networks (RBFN) in the presence of both state and measurement noise. The effect of presence of outliers in the data is also considered. RBFN is found to give superior results compared to finite difference derivatives for noisy data.     

Error estimates for interpolation of rough data using the scattered shifts of a radial basis function

The error between appropriately smooth functions and their radial basis function interpolants, as the interpolation points fill out a bounded domain in R^d, is a well studied artifact. In all of these cases, the analysis takes place in a natural function space dictated by the choice of radial basis function – the native space. The native space contains functions possessing a certain amount of smoothness. This paper establishes error estimates when the function being interpolated is conspicuously rough. AMS subject classification 41A05, 41A25, 41A30, 41A63R.A. Brownlee: Supported by a studentship from the Engineering and Physical Sciences Research Council.     

An alternative procedure for selecting a good value for the parameter <Emphasis Type="Italic">c</Emphasis> in RBF-interpolation

The impact of the scaling parameter c on the accuracy of interpolation schemes using radial basis functions (RBFs) has been pointed out by several authors. Rippa (Adv Comput Math 11:193–210, 1999) proposes an algorithm based on the idea of cross validation for selecting a good such parameter value. In this paper we present an alternative procedure, that can be interpreted as a refinement of Rippa’s algorithm for a cost function based on the euclidean norm. We point out how this method is related to the procedure of maximum likelihood estimation, which is used for identifying covariance parameters of stochastic processes in spatial statistics. Using the same test functions as Rippa we show that our algorithm compares favorably with cross validation in many cases and discuss its limitations. Finally we present some computational aspects of our algorithm.     

Analysis of stationary subdivision schemes for curve design based on radial basis function interpolation

This paper provides a large family of interpolatory stationary subdivision schemes based on radial basis functions (RBFs) which are positive definite or conditionally positive definite. A radial basis function considered in this study has a tension parameter λ>0 such that it provides design flexibility. We prove that for a sufficiently large , the proposed 2L-point (L∈N) scheme has the same smoothness as the well-known 2L-point Deslauriers-Dubuc scheme, which is based on 2L-1 degree polynomial interpolation. Some numerical examples are presented to illustrate the performance of the new schemes, adapting subdivision rules on bounded intervals in a way of keeping the same smoothness and accuracy of the pre-existing schemes on R. We observe that, with proper tension parameters, the new scheme can alleviate undesirable artifacts near boundaries, which usually appear to interpolatory schemes with irregularly distributed control points.     

Construction of adapted subdivision schemes for bounded intervals based on radial basis function interpolation

We study stationary subdivision schemes based on radial basis function interpolation. Each scheme has a tension parameter, say λ, which actually belongs to the radial basis function. In particular, adapted subdivision rules on bounded intervals are developed.     

Limit problems for interpolation by analytic radial basis functions

Interpolation problems for analytic radial basis functions like the Gaussian and inverse multiquadrics can degenerate in two ways: the radial basis functions can be scaled to become increasingly flat, or the data points coalesce in the limit while the radial basis functions stay fixed. Both cases call for a careful regularization, which, if carried out explicitly, yields a preconditioning technique for the degenerating linear systems behind these interpolation problems. This paper deals with both cases. For the increasingly flat limit, we recover results by Larsson and Fornberg together with Lee, Yoon, and Yoon concerning convergence of interpolants towards polynomials. With slight modifications, the same technique can also handle scenarios with coalescing data points for fixed radial basis functions. The results show that the degenerating local Lagrange interpolation problems converge towards certain Hermite–Birkhoff problems. This is an important prerequisite for dealing with approximation by radial basis functions adaptively, using freely varying data sites.