Tight frame expansions of multiscale reproducing kernels in Sobolev spaces

Multiscale kernels are a new type of positive definite reproducing kernels in Hilbert spaces. They are constructed by a superposition of shifts and scales of a single refinable function and were introduced in the paper of R. Opfer [Multiscale kernels, Adv. Comput. Math. (2004), in press]. By applying standard reconstruction techniques occurring in radial basis function- or machine learning theory, multiscale kernels can be used to reconstruct multivariate functions from scattered data. The multiscale structure of the kernel allows to represent the approximant on several levels of detail or accuracy. In this paper we prove that multiscale kernels are often reproducing kernels in Sobolev spaces. We use this fact to derive error bounds. The set of functions used for the construction of the multiscale kernel will turn out to be a frame in a Sobolev space of certain smoothness. We will establish that the frame coefficients of approximants can be computed explicitly. In our case there is neither a need to compute the inverse of the frame operator nor is there a need to compute inner products in the Sobolev space. Moreover we will prove that a recursion formula between the frame coefficients of different levels holds. We present a bivariate numerical example illustrating the mutiresolution and data compression effect.     

Spherical Scattered Data Quasi-interpolation by Gaussian Radial Basis Function

Since the spherical Gaussian radial function is strictly positive definite, the authors use the linear combinations of translations of the Gaussian kernel to interpolate the scattered data on spheres in this article. Seeing that target functions are usually outside the native spaces, and that one has to solve a large scaled system of linear equations to obtain combinatorial coefficients of interpolant functions, the authors first probe into some problems about interpolation with Gaussian radial functions. Then they construct quasiinterpolation operators by Gaussian radial function, and get the degrees of approximation. Moreover, they show the error relations between quasi-interpolation and interpolation when they have the same basis functions. Finally, the authors discuss the construction and approximation of the quasi-interpolant with a local support function.     

On wavelet decomposition of spaces of first order splines

We consider approximate relations in the form of a system of linear algebraic equations that yield B _φ -splines. We construct Lagrange type splines of the first order and give examples of polynomial, trigonometric, hyperbolic, and exponential B _φ -splines. We also construct a system of linear functionals biorthogonal to the B _φ -splines and resolve an interpolation problem generated by this system. For refined nonuniform grids we establish an embedding of spaces of B _φ -splines. The decomposition and reconstruction formulas are obtained. Bibliography: 20 titles. Translated from Problemy Matematicheskogo Analiza, No. 38, December 2008, pp. 47–60.     

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.     

Transfinite Thin Plate Spline Interpolation

Duchon’s method of thin plate splines defines a polyharmonic interpolant to scattered data values as the minimizer of a certain integral functional. For transfinite interpolation, i.e., interpolation of continuous data prescribed on curves or hypersurfaces, Kounchev has developed the method of polysplines, which are piecewise polyharmonic functions of fixed smoothness across the given hypersurfaces and satisfy some boundary conditions. Recently, Bejancu has introduced boundary conditions of Beppo–Levi type to construct a semicardinal model for polyspline interpolation to data on an infinite set of parallel hyperplanes. The present paper proves that, for periodic data on a finite set of parallel hyperplanes, the polyspline interpolant satisfying Beppo–Levi boundary conditions is in fact a thin plate spline, i.e., it minimizes a Duchon type functional. The construction and variational characterization of the Beppo–Levi polysplines are based on the analysis of a new class of univariate exponential ℒ-splines satisfying adjoint natural end conditions.     

Multiscale data sampling and function extension

We introduce a multiscale scheme for sampling scattered data and extending functions defined on the sampled data points, which overcomes some limitations of the Nyström interpolation method. The multiscale extension (MSE) method is based on mutual distances between data points. It uses a coarse-to-fine hierarchy of the multiscale decomposition of a Gaussian kernel. It generates a sequence of subsamples, which we refer to as adaptive grids, and a sequence of approximations to a given empirical function on the data, as well as their extensions to any newly-arrived data point. The subsampling is done by a special decomposition of the associated Gaussian kernel matrix in each scale in the hierarchical procedure.     

On interpolation with products of positive definite functions

In this paper we consider the problem of scattered data interpolation for multivariate functions. In order to solve this problem, linear combinations of products of positive definite kernel functions are used. The theory of reproducing kernels is applied. In particular, it follows from this theory that the interpolating functions are solutions of some varational problems.     

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.     

Stability of kernel-based interpolation

It is often observed that interpolation based on translates of radial basis functions or non-radial kernels is numerically unstable due to exceedingly large condition of the kernel matrix. But if stability is assessed in function space without considering special bases, this paper proves that kernel-based interpolation is stable. Provided that the data are not too wildly scattered, the L ₂ or L _∞ norms of interpolants can be bounded above by discrete ℓ₂ and ℓ_∞ norms of the data. Furthermore, Lagrange basis functions are uniformly bounded and Lebesgue constants grow at most like the square root of the number of data points. However, this analysis applies only to kernels of limited smoothness. Numerical examples support our bounds, but also show that the case of infinitely smooth kernels must lead to worse bounds in future work, while the observed Lebesgue constants for kernels with limited smoothness even seem to be independent of the sample size and the fill distance.     

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.     

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.     

Cardinal Interpolation with Gaussian Kernels

In this paper, interpolation by scaled multi-integer translates of Gaussian kernels is studied. The main result establishes L _p Sobolev error estimates and shows that the error is controlled by the L _p multiplier norm of a Fourier multiplier closely related to the cardinal interpolant, and comparable to the Hilbert transform. Consequently, its multiplier norm is bounded independent of the grid spacing when 1<p<∞, and involves a logarithmic term when p=1 or ∞.     

Boundary layer approximate approximations and cubature of potentials in domains

In this article we present a new approach to the computation of volume potentials over bounded domains, which is based on the quasi‐interpolation of the density by almost locally supported basis functions for which the corresponding volume potentials are known. The quasi‐interpolant is a linear combination of the basis function with shifted and scaled arguments and with coefficients explicitly given by the point values of the density. Thus, the approach results in semi‐analytic cubature formulae for volume potentials, which prove to be high order approximations of the integrals. It is based on multi‐resolution schemes for accurate approximations up to the boundary by applying approximate refinement equations of the basis functions and iterative approximations on finer grids. We obtain asymptotic error estimates for the quasi‐interpolation and corresponding cubature formulae and provide some numerical examples. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multiscale analysis in Sobolev spaces on bounded domains

We study a multiscale scheme for the approximation of Sobolev functions on bounded domains. Our method employs scattered data sites and compactly supported radial basis functions of varying support radii at scattered data sites. The actual multiscale approximation is constructed by a sequence of residual corrections, where different support radii are employed to accommodate different scales. Convergence theorems for the scheme are proven, and it is shown that the condition numbers of the linear systems at each level are independent of the level, thereby establishing for the first time a mathematical theory for multiscale approximation with scaled versions of a single compactly supported radial basis function at scattered data points on a bounded domain.     

Radial basis interpolation on homogeneous manifolds: convergence rates

Pointwise error estimates for approximation on compact homogeneous manifolds using radial kernels are presented. For a positive definite kernel κ the pointwise error at x for interpolation by translates of κ goes to 0 like ρ ^r , where ρ is the density of the interpolating set on a fixed neighbourhood of x. Tangent space techniques are used to lift the problem from the manifold to Euclidean space, where methods for proving such error estimates are well established. Partially supported by NSF Grant DMS-9972004.     

A Newton basis for Kernel spaces

It is well known that representations of kernel-based approximants in terms of the standard basis of translated kernels are notoriously unstable. To come up with a more useful basis, we adopt the strategy known from Newton’s interpolation formula, using generalized divided differences and a recursively computable set of basis functions vanishing at increasingly many data points. The resulting basis turns out to be orthogonal in the Hilbert space in which the kernel is reproducing, and under certain assumptions it is complete and allows convergent expansions of functions into series of interpolants. Some numerical examples show that the Newton basis is much more stable than the standard basis of kernel translates.     

Power Series Kernels

We introduce a class of analytic positive definite multivariate kernels which includes infinite dot product kernels as sometimes used in machine learning, certain new nonlinearly factorizable kernels, and a kernel which is closely related to the Gaussian. Each such kernel reproduces in a certain “native” Hilbert space of multivariate analytic functions. If functions from this space are interpolated in scattered locations by translates of the kernel, we prove spectral convergence rates of the interpolants and all derivatives. By truncation of the power series of the kernel-based interpolants, we constructively generalize the classical Bernstein theorem concerning polynomial approximation of analytic functions to the multivariate case. An application to machine learning algorithms is presented.      

Approximation in Sobolev Spaces by Kernel Expansions

For interpolation of smooth functions by smooth kernels having an expansion into eigenfunctions (e.g., on the circle, the sphere, and the torus), good results including error bounds are known, provided that the smoothness of the function is closely related to that of the kernel. The latter fact is usually quantified by the requirement that the function should lie in the “native” Hilbert space of the kernel, but this assumption rules out the treatment of less smooth functions by smooth kernels. For the approximation of functions from “large” Sobolev spaces W by functions generated by smooth kernels, this paper shows that one gets at least the known order for interpolation with a less smooth kernel that has W as its native space.     

Multiscale support vector regression method in Sobolev spaces on bounded domains

In this paper, we investigate the multiscale support vector regression (SVR) method for approximation of functions in Sobolev spaces on bounded domains. The Vapnik ?-intensive loss function, which has been developed well in learning theory, is introduced to replace the standard l² loss function in multiscale least squares methods. Convergence analysis is presented to verify the validity of the multiscale SVR method with scaled versions of compactly supported radial basis functions. Error estimates on noisy observation data are also derived to show the robustness of our proposed algorithm. Numerical simulations support the theoretical predictions.