Fast and accurate interpolation of large scattered data sets on the sphere

In this paper a new efficient algorithm for spherical interpolation of large scattered data sets is presented. The solution method is local and involves a modified spherical Shepard’s interpolant, which uses zonal basis functions as local approximants. The associated algorithm is implemented and optimized by applying a nearest neighbour searching procedure on the sphere. Specifically, this technique is mainly based on the partition of the sphere in a suitable number of spherical zones, the construction of spherical caps as local neighbourhoods for each node, and finally the employment of a spherical zone searching procedure. Computational cost and storage requirements of the spherical algorithm are analyzed. Moreover, several numerical results show the good accuracy of the method and the high efficiency of the proposed algorithm.     

Thinning algorithms for scattered data interpolation

Multistep interpolation of scattered data by compactly supported radial basis functions requires hierarchical subsets of the data. This paper analyzes thinning algorithms for generating evenly distributed subsets of scattered data in a given domain in ℝ ^d .     

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.

     

Numerical differentiation on scattered data through multivariate polynomial interpolation

BIT Numerical Mathematics - We discuss a pointwise numerical differentiation formula on multivariate scattered data, based on the coefficients of local polynomial interpolation at Discrete Leja...     

Monotone interpolation of scattered data in R s

We present a method to interpolate scattered monotone data in R ^s using a variational approach. We present both theoretical and practical properties and give a dual algorithm allowing us to compute the resulting function whens=2. The method is specially suited for scattered data but comparison with existing methods for data on grids shows that it is a valid approach even in that case.Communicated by Wolfgang Dahmen.     

Piecewise complementary Lidstone interpolation and error inequalities

The purpose of this paper is to develop piecewise complementary Lidstone interpolation in one and two variables and establish explicit error bounds for the derivatives in L_∞ and L₂ norms.     

C^1 C^2 INTERPOLATION OF SCATTERED DATA POINTS

In this paper an error in [4] is pointed out and a method for constructing surface interpolating scattered data points is presented, The main feature of the method in this paper is that the surface so constructed is polynomial, which makes the construction simple and the calculation easy.     

Hermite-Birkhoff interpolation of scattered data by radial basis functions

For Hermite-Birkhoff interpolation of scattered multidimensional data by radial basis function φ, existence and characterization theorems and a variational principle are proved. Examples include φ(r)=r^b, Duchon’s thin-plate splines, Hardy’s multiquadrics, and inverse multiquadrics.     

A note on stability results for scattered data interpolation on Euclidean spheres

The present work considers the interpolation of the scattered data on the d-sphere by spherical polynomials. We prove bounds on the conditioning of the problem which rely only on the separation distance of the sampling nodes and on the degree of polynomials being used. To this end, we establish a packing argument for well separated sampling nodes and construct strongly localized polynomials on spheres. Numerical results illustrate our theoretical findings. Dedicated to Professor Manfred Tasche on the occasion of his 65th birthday.     

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)     

Improved error bounds for scattered data interpolation by radial basis functions

If additional smoothness requirements and boundary conditions are met, the well-known approximation orders of scattered data interpolants by radial functions can roughly be doubled.

     

The convergence of three spline methods for scattered data interpolation and fitting

The convergences of three L₁ spline methods for scattered data interpolation and fitting using bivariate spline spaces are studied in this paper. That is, L₁ interpolatory splines, splines of least absolute deviation, and L₁ smoothing splines are shown to converge to the given data function under some conditions and hence, the surfaces from these three methods will resemble the given data values.     

On a quadratic functional occurring in a bivariate scattered data interpolation problem

Sunto L’applicazione di noti metodi che utilizzano funzioni di tipo blending per la costruzione di funzioni bivariate C¹ per l’interpolazione di dati, richiede la conoscenza delle derivate parziali del primo ordine ai vertici di una triangolazione sottostante. In questo lavoro consideriamo il metodo proposto da Nielson, che consiste nel calcolare stime delle derivate parziali del primo ordine minimizzando un opportuno funzionale quadratico, caratterizzato da parametri di tensione non negativi. Scopo del lavoro è l’analisi di alcune proprietà particolari di questo funzionale per la costruzione di algoritmi efficienti e robusti per la determinazione delle stime suddette delle derivate quando si ha a che fare con insiemi di dati di grandi dimensioni. Abstract The application of widely known blending methods for constructingC ¹ bivariate functions interpolating scattered data requires the knowledge of the partial derivatives of first order at the vertices of an underlying triangulation. In this paper we consider the method proposed by Nielson that consists in computing estimates of the first order partial derivatives by minimizing an appropriate quadratic functional, characterized by nonnegative tension parameters. The aim of the paper is to analyse some peculiar properties of this functional in order to construct robust and efficient algorithms for determining the above estimates of the derivatives when we are concerned with extremely large data sets.      

Maximum scattered linear sets and MRD-codes

The rank of a scattered \({\mathbb F}_q\)-linear set of \({{\mathrm{{PG}}}}(r-1,q^n)\), rn even, is at most rn / 2 as it was proved by Blokhuis and Lavrauw. Existence results and explicit constructions were given for infinitely many values of r, n, q (rn even) for scattered \({\mathbb F}_q\)-linear sets of rank rn / 2. In this paper, we prove that the bound rn / 2 is sharp also in the remaining open cases. Recently Sheekey proved that scattered \({\mathbb F}_q\)-linear sets of \({{\mathrm{{PG}}}}(1,q^n)\) of maximum rank n yield \({\mathbb F}_q\)-linear MRD-codes with dimension 2n and minimum distance \(n-1\). We generalize this result and show that scattered \({\mathbb F}_q\)-linear sets of \({{\mathrm{{PG}}}}(r-1,q^n)\) of maximum rank rn / 2 yield \({\mathbb F}_q\)-linear MRD-codes with dimension rn and minimum distance \(n-1\).     

Multilevel interpolation of scattered data using H ${\mathcal{H}}$ -matrices

Numerical Algorithms - Scattered data interpolation can be used to approximate a multivariate function by a linear combination of positive definite radial basis functions (RBFs). In practice, the...     

Matrix-valued interpolation and hyperconvex sets

We prove that it is possible for two uniform algebras to have the same scalar interpolating sets, yet still have different matrix-valued interpolating sets.We prove a result for tensor products of uniform algebras that extends Agler's interpolation formula for the bidisk to more general product domains. This is accomplished by introducing a dual object for interpolation problems, which we call a Schur ideal, and proving that the Schur ideal for a tensor product is the intersection of the corresponding Schur ideals.Research supported in part by a grant from the NSF