Multilevel scattered data approximation by adaptive domain decomposition

A new multilevel approximation scheme for scattered data is proposed. The scheme relies on an adaptive domain decomposition strategy using quadtree techniques (and their higher-dimensional generalizations). It is shown in the numerical examples that the new method achieves an improvement on the approximation quality of previous well-established multilevel interpolation schemes. AMS subject classification 65D15, 65D05, 65D07, 65D17     

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.     

Approximating scattered data with discontinuities

A method is presented for approximating scattered data by a function defined on a regular two-dimensional grid. It is required that the approximation is discontinuous across given curves in the parameter domain known as faults. The method has three phases: regularisation, local approximation and extrapolation. The main emphasis is put on the extrapolation which is based on a matrix equation which minimises second order differences. By approximating each fault by a set of line segments parallel with one of the axes, it is simple to introduce natural boundary conditions across the faults. The resulting approximation has, as expected, discontinuities across faults and is smooth elsewhere. The method is stable even for large data sets.This research was supported by the Royal Norwegian Council for Scientific and Industrial Research.     

Polynomial approximation on the sphere using scattered data

We consider the problem of approximately reconstructing a function f defined on the surface of the unit sphere in the Euclidean space ℝ^{q +1} by using samples of f at scattered sites. A central role is played by the construction of a new operator for polynomial approximation, which is a uniformly bounded quasi‐projection in the de la Vallée Poussin style, i.e. it reproduces spherical polynomials up to a certain degree and has uniformly bounded L^p operator norm for 1 ≤ p ≤ ∞. Using certain positive quadrature rules for scattered sites due to Mhaskar, Narcowich and Ward, we discretize this operator obtaining a polynomial approximation of the target function which can be computed from scattered data and provides the same approximation degree of the best polynomial approximation. To establish the error estimates we use Marcinkiewicz–Zygmund inequalities, which we derive from our continuous approximating operator. We give concrete bounds for all constants in the Marcinkiewicz–Zygmund inequalities as well as in the error estimates. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Generalized Strang–Fix condition for scattered data quasi-interpolation

Quasi-interpolation is very useful in the study of the approximation theory and its applications, since the method can yield solutions directly and does not require solving any linear system of equations. However, quasi-interpolation is usually discussed only for gridded data in the literature. In this paper we shall introduce a generalized Strang–Fix condition, which is related to nonstationary quasi-interpolation. Based on the discussion of the generalized Strang–Fix condition we shall generalize our quasi-interpolation scheme for multivariate scattered data, too. AMS subject classification 41A63, 41A25, 65D10Zong Min Wu: Supported by NSFC No. 19971017 and NOYG No. 10125102.     

Piecewise linear interpolants to Lagrange and Hermite convex scattered data

This paper concerns two fundamental interpolants to convex bivariate scattered data. The first,u, is the supremum over all convex Lagrange interpolants and is piecewise linear on a triangulation. The other,l, is the infimum over all convex Hermite interpolants and is piecewise linear on a tessellation. We discuss the existence, uniqueness, and numerical computation ofu andl and the associated triangulation and tessellation. We also describe how to generate convex Hermite data from convex Lagrange data.Research partially supported by the EU Project FAIRSHAPE, CHRX-CT94-0522. The first author was also partially supported by DGICYT PB93-0310 Research Grant.     

Multiscale kernels

This paper reconstructs multivariate functions from scattered data by a new multiscale technique. The reconstruction uses standard methods of interpolation by positive definite reproducing kernels in Hilbert spaces. But it adopts techniques from wavelet theory and shift-invariant spaces to construct a new class of kernels as multiscale superpositions of shifts and scales of a single compactly supported function φ. This means that the advantages of scaled regular grids are used to construct the kernels, while the advantages of unrestricted scattered data interpolation are maintained after the kernels are constructed. Using such a multiscale kernel, the reconstruction method interpolates at given scattered data. No manipulations of the data (e.g., thinning or separation into subsets of certain scales) are needed. Then, the multiscale structure of the kernel allows to represent the interpolant on regular grids on all scales involved, with cheap evaluation due to the compact support of the function φ, and with a recursive evaluation technique if φ is chosen to be refinable. There also is a wavelet-like data reduction effect, if a suitable thresholding strategy is applied to the coefficients of the interpolant when represented over a scaled grid. Various numerical examples are presented, illustrating the multiresolution and data compression effects.     

SOME SHAPE-PRESERVING QUASI-INTERPOLANTS TO NON-UNIFORMLY DISTRIBUTED DATABY MQ-B-SPLINES

Based on the definition of MQ-B-Splines, this article constructs five types of univariate quasi-interpolants to non-uniformly distributed data. The error estimates and the shape-preserving properties are shown in details. And examples are shown to demonstrate the capacity of the quasi-interpolants for curve representation.     

Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting

In this paper we discuss Sobolev bounds on functions that vanish at scattered points in a bounded, Lipschitz domain that satisfies a uniform interior cone condition. The Sobolev spaces involved may have fractional as well as integer order. We then apply these results to obtain estimates for continuous and discrete least squares surface fits via radial basis functions (RBFs). These estimates include situations in which the target function does not belong to the native space of the RBF.

     

Polyharmonic splines: An approximation method for noisy scattered data of extra-large size

The aim of this paper is to provide a fast method, with a good quality of reproduction, to recover functions from very large and irregularly scattered samples of noisy data, which may present outliers. To the given sample of size N, we associate a uniform grid and, around each grid point, we condense the local information given by the noisy data by a suitable estimator. The recovering is then performed by a stable interpolation based on isotropic polyharmonic B-splines. Due to the good approximation rate, we need only M?N degrees of freedom to recover the phenomenon faithfully.     

An analytic approximation to the cardinal functions of Gaussian radial basis functions on an infinite lattice

Gaussian radial basis functions (RBFs) have been very useful in computer graphics and for numerical solutions of partial differential equations where these RBFs are defined, on a grid with uniform spacing h, as translates of the “master” function (x;α,h)≡exp(-[α²/h²]x²) where α is a user-choosable constant. Unfortunately, computing the coefficients of (x-jh;α,h) requires solving a linear system with a dense matrix. It would be much more efficient to rearrange the basis functions into the equivalent “Lagrangian” or “cardinal” basis because the interpolation matrix in the new basis is the identity matrix; the cardinal basis C_j(x;α,h) is defined by the set of linear combinations of the Gaussians such that C_j(kh)=1 when k=j and C_j(kh)=0 for all integers . We show that the cardinal functions for the uniform grid are C_j(x;h,α)=C(x/h-j;α) where C(X;α)≈(α²/π)sin(πX)/sinh(α²X). The relative error is only about 4exp(-2π²/α²) as demonstrated by the explicit second order approximation. It has long been known that the error in a series of Gaussian RBFs does not converge to zero for fixed α as h→0, but only to an “error saturation” proportional to exp(-π²/α²). Because the error in our approximation to the master cardinal function C(X;α) is the square of the error saturation, there is no penalty for using our new approximations to obtain matrix-free interpolating RBF approximations to an arbitrary function f(x). The master cardinal function on a uniform grid in d dimensions is just the direct product of the one-dimensional cardinal functions. Thus in two dimensions . We show that the matrix-free interpolation can be extended to non-uniform grids by a smooth change of coordinates.     

Achieving accuracy and efficiency in spherical modelling of real data

In this paper, a hybrid approximation method on the sphere is analysed. As interpolation scheme, we consider a partition of unity method, such as the modified spherical Shepard method, which uses zonal basis functions plus spherical harmonics as local approximants. The associated algorithm is efficiently implemented and works well also when the amount of data is very large, as it is based on an optimized searching procedure. Locality of the method guarantees stability in numerical computations, and numerical results show good accuracy. Moreover, we aimed to discuss preservation of such features when the method and the related algorithm are applied to experimental data. To achieve this purpose, we considered the Magnetic Field Satellite data. The goal was reached, as efficiency and accuracy are maintained on several sets of real data. Copyright © 2013 John Wiley & Sons, Ltd.     

Local polynomial reproduction and moving least squares approximation

Local polynomial reproduction is a key ingredient in providingerror estimates for several approximation methods. To boundthe Lebesgue constants is a hard task especially in a multivariatesetting. We provide a result which allows us to bound the Lebesgueconstants uniformly and independently of the space dimensionby oversampling. We get explicit and small bounds for the Lebesgueconstants. Moreover, we use these results to establish errorestimates for the moving least squares approximation scheme,also with special emphasis on the involved constants. We discussthe numerical treatment of the method and analyse its effort.Finally, we give large scale examples.     

Recent developments in error estimates for scattered-data interpolation via radial basis functions

Error estimates for scattered data interpolation by shifts of a positive definite function for target functions in the associated reproducing kernel Hilbert space (RKHS) have been known for a long time. However, apart from special cases where data is gridded, these interpolation estimates do not apply when the target functions generating the data are outside of the associated RKHS, and in fact until very recently no estimates were known in such situations. In this paper, we review these estimates in cases where the underlying space is Rⁿ and the positive definite functions are radial basis functions (RBFs). AMS subject classification 41A25, 41A05, 41A63, 42B35Research supported by grant DMS-0204449 from the National Science Foundation.     

Recursive Kernels

This paper is an extension of earlier papers [8, 9] on the “native” Hilbert spaces of functions on some domain Ω ⊂ R ^d in which conditionally positive definite kernels are reproducing kernels. Here, the focus is on subspaces of native spaces which are induced via subsets of Ω, and we shall derive a recursive subspace structure of these, leading to recursively defined reproducing kernels. As an application, we get a recursive Neville-Aitken-type interpolation process and a recursively defined orthogonal basis for interpolation by translates of kernels.     

RECURSIVE KERNELS

This paper is an extension of earlier papers [8, 9] on the ＂native＂ Hilbert spaces of functions on some domain Ωbelong toR^d Rd in which conditionally positive definite kernels are reproducing kernels. Here, the focus is on subspaces of native spaces which are induced via subsets of Ω, and we shall derive a recursive subspace structure of these, leading to recur- sively defined reproducing kernels. As an application, we get a recursive Neville-Aitken- type interpolation process and a recursively defined orthogonal basis for interpolation by translates of kernels.     

On lower bounds in radial basis approximation

We investigate the approximation by manifolds _n() generated by linear combinations of n radial basis functions on R^d of the form (|–a|), where is the thin-plate spline type function. We obtain exact asymptotic estimates for the approximation of Sobolev classes W^r(B^d) in the space L(B^d) on the unit ball B^d. AMS subject classification 41A25, 41A63, 65D07, 41A15     

函数的径向基表示

本文是关于函数的径向表示的综述性文章，基于我们对这方面的研究工作的了解，介绍了国际上近年来这方面的主要的有关研究结果以及在一些领域中应用的情况，文后附有主要的参考文献以便感兴趣的读者查阅。     

Multilevel regularization of wavelet based fitting of scattered data – some experiments

In [6], an adaptive method to approximate unorganized clouds of points by smooth surfaces based on wavelets has been described. The general fitting algorithm operates on a coarse-to-fine basis. It selects on each refinement level in a first step a reduced number of wavelets which are appropriate to represent the features of the data set. In a second step, the fitting surface is constructed as the linear combination of the wavelets which minimizes the distance to the data in a least squares sense. This is followed by a thresholding procedure on the wavelet coefficients to discard those which are too small to contribute much to the surface representation. In this paper, we firstly generalize this strategy to a classically regularized least squares functional by adding a Sobolev norm, taking advantage of the capability of wavelets to characterize Sobolev spaces of even fractional order. After recalling the usual cross-validation technique to determine the involved smoothing parameters, some examples of fitting severely irregularly distributed data, synthetically produced and of geophysical origin, are presented. In order to reduce computational costs, we then introduce a multilevel generalized cross-validation technique which goes beyond the Sobolev formulation and exploits the hierarchical setting based on wavelets. We illustrate the performance of the new strategy on some geophysical data. AMS subject classification 65T60, 62G09, 93E14, 93E24We gratefully acknowledge the support by the Deutsche Forschungsgemeinschaft (KU 1028/7 1 and SFB 611) and by the Basque Government.     

Scattered data quasi‐interpolation on spheres

This paper studies the construction and approximation of quasi‐interpolation for spherical scattered data. First of all, a kind of quasi‐interpolation operator with Gaussian kernel is constructed to approximate the spherical function, and two Jackson type theorems are established. Second, the classical Shepard operator is extended from Euclidean space to the unit sphere, and the error of approximation by the spherical Shepard operator is estimated. Finally, the compact supported kernel is used to construct quasi‐interpolation operator for fitting spherical scattered data, where the spherical modulus of continuity and separation distance of scattered sampling points are employed as the measurements of approximation error. Copyright © 2014 John Wiley & Sons, Ltd.