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.     

Approximate Hermite quasi-interpolation

In this article, we derive approximate quasi-interpolants when the values of a function u and of some of its derivatives are prescribed at the points of a uniform grid. As a byproduct of these formulas we obtain very simple approximants, which provide high-order approximations for solutions to elliptic differential equations with constant coefficients.     

An analysis of wavelet frame based scattered data reconstruction

In real world applications many signals contain singularities, like edges in images. Recent wavelet frame based approaches were successfully applied to reconstruct scattered data from such functions while preserving these features. In this paper we present a recent approach which determines the approximant from shift invariant subspaces by minimizing an ${?}_1$-regularized least squares problem which makes additional use of the wavelet frame transform in order to preserve sharp edges. We give a detailed analysis of this approach, i.e., how the approximation error behaves dependent on data density and noise level. Moreover, a link to wavelet frame based image restoration models is established and the convergence of these models is analyzed. In the end, we present some numerical examples, for instance how to apply this approach to handle coarse-grained models in molecular dynamics.     

Error estimates for scattered data interpolation on spheres

We study Sobolev type estimates for the approximation order resulting from using strictly positive definite kernels to do interpolation on the -sphere. The interpolation knots are scattered. Our approach partly follows the general theory of Golomb and Weinberger and related estimates. These error estimates are then based on series expansions of smooth functions in terms of spherical harmonics. The Markov inequality for spherical harmonics is essential to our analysis and is used in order to find lower bounds for certain sampling operators on spaces of spherical harmonics.

     

Global errors for approximate approximations with Gaussian kernels on compact intervals

This paper investigates the global errors which result when the method of approximate approximations is applied to a function defined on a compact interval. By extending the functions to a wider interval, we are able to introduce modified forms of the quasi-interpolant operators. Using these operators as approximation tools, we estimate upper bounds on the errors in terms of a uniform norm. We consider only continuous and differentiable functions. A similar problem is solved for the two-dimensional case.     

Meshless Galerkin algorithms for boundary integral equations with moving least square approximations

In this paper, we first give error estimates for the moving least square (MLS) approximation in the Hk norm in two dimensions when nodes and weight functions satisfy certain conditions. This two-dimensional error results can be applied to the surface of a three-dimensional domain. Then combining boundary integral equations (BIEs) and the MLS approximation, a meshless Galerkin algorithm, the Galerkin boundary node method (GBNM), is presented. The optimal asymptotic error estimates of the GBNM for three-dimensional BIEs are derived. Finally, taking the Dirichlet problem of Laplace equation as an example, we set up a framework for error estimates of the GBNM for boundary value problems in three dimensions.     

A weighted least squares method for scattered data fitting

In this paper, we present a weighted least squares method to fit scattered data with noise. Existence and uniqueness of a solution are proved and an error bound is derived. The numerical experiments illustrate that our weighted least squares method has better performance than the traditional least squares method in case of noisy data.     

Refined Error Estimates for Radial Basis Function Interpolation

We discuss new and refined error estimates for radial-function scattered-data interpolants and their derivatives. These estimates hold on R ^d , the d-torus, and the 2-sphere. We employ a new technique, involving norming sets, that enables us to obtain error estimates, which in many cases give bounds orders of magnitude smaller than those previously known.     

Detection of discontinuities in scattered data approximation

A Detection Algorithm for the localisation of unknown fault lines of a surface from scattered data is given. The method is based on a local approximation scheme using thin plate splines, and we show that this yields approximation of second order accuracy instead of first order as in the global case. Furthermore, the Detection Algorithm works with triangulation methods, and we show their utility for the approximation of the fault lines. The output of our method provides polygonal curves which can be used for the purpose of constrained surface approximation. This revised version was published online in June 2006 with corrections to the Cover Date.     

The validity of the KdV approximation in case of resonances arising from periodic media

It is the purpose of this short note to discuss some aspects of the validity question concerning the Korteweg-de Vries (KdV) approximation for periodic media. For a homogeneous model possessing the same resonance structure as it arises in periodic media we prove the validity of the KdV approximation with the help of energy estimates.     

A kind of multiquadric quasi-interpolation operator satisfying any degree polynomial reproduction property to scattered data

In this paper, by virtue of using the linear combinations of the shifts of f(x) to approximate the derivatives of f(x) and Waldron’s superposition idea (2009), we modify a multiquadric quasi-interpolation with the property of linear reproducing to scattered data on one-dimensional space, such that a kind of quasi-interpolation operator L_r+1f has the property of r+1(r∈Z,r≥0) degree polynomial reproducing and converges up to a rate of r+2. There is no demand for the derivatives of f in the proposed quasi-interpolation L_r+1f, so it does not increase the orders of smoothness of f. Finally, some numerical experiments are shown to compare the approximation capacity of our quasi-interpolation operators with that of Wu-Schaback’s quasi-interpolation scheme and Feng-Li’s quasi-interpolation scheme.     

Sobolev Error Estimates and a Bernstein Inequality for Scattered Data Interpolation via Radial Basis Functions

Error estimates for scattered-data interpolation via radial basis functions (RBFs) for target functions in the associated reproducing kernel Hilbert space (RKHS) have been known for a long time. Recently, these estimates have been extended to apply to certain classes of target functions generating the data which are outside the associated RKHS. However, these classes of functions still were not "large" enough to be applicable to a number of practical situations. In this paper we obtain Sobolev-type error estimates on compact regions of Rⁿ when the RBFs have Fourier transforms that decay algebraically. In addition, we derive a Bernstein inequality for spaces of finite shifts of an RBF in terms of the minimal separation parameter.     

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     

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.     

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)     

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.     

Optimal average approximations for functions mapping in quasi-Banach spaces

In 1994, M.M. Popov [6] showed that the fundamental theorem of calculus fails, in general, for functions mapping from a compact interval of the real line into the _?p${?}_p$-spaces for 0<p<1$0<p<1$, and the question arose whether such a significant result might hold in some other non-Banach spaces. In this article we completely settle the problem by proving that the fundamental theorem of calculus breaks down in the context of any non-locally convex quasi-Banach space. Our approach introduces the tool of Riemann-integral averages of continuous functions, and uses it to bring out to light the differences in behavior of their approximates in the lack of local convexity. As a by-product of our work we solve a problem raised in [1] on the different types of spaces of differentiable functions with values on a quasi-Banach space.     

Detecting and approximating fault lines from randomly scattered data

Discretely defined surfaces that exhibit vertical displacements across unknown fault lines can be difficult to approximate accurately unless a representation of the faults is known. Accurate representations of these faults enable the construction of constrained approximation models that can successfully overcome common problems such as over-smoothing. In this paper we review an existing method for detecting fault lines and present a new detection approach based on data triangulations and discrete Gaussian curvature (DGC). Furthermore, we show that if the fault line can be described non-parametrically, then accurate support vector machine (SVM) models can be constructed that are independent of the type of triangulation used in the detection algorithms. We shall also see that SVM models are particularly effective when the data produced by the detection algorithms are noisy. We compare the performances of the various new and established models.     

Polynomial Trace Estimates for Semigroups

For semigroups (e ^tA ) _t0 of operators on a Hilbert space, we give conditions guaranteeing trace estimates of the polynomial type 0$$ " align="middle" border="0"> , where denotes the trace class. As an application we present higher order analogues of results due to E.B. Davies, B. Simon and M. van den Berg of the type 0$$ " align="middle" border="0"> , for certain unbounded domains , e.g. spiny urchin domains.     

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.