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.     

Sampling inequalities for infinitely smooth radial basis functions and its application to error estimates

Recently, Rieger and Zwicknagl (2010) have introduced sampling inequalities for infinitely smooth functions to derive Sobolev-type error estimates. They introduced exponential convergence orders for functions within the native space associated with the given radial basis function (RBF). Our major concern of this paper is to extend the results made in Rieger and Zwicknagl (2010). We derive generalized sampling inequalities for the larger class of infinitely smooth RBFs, including multiquadrics, inverse multiquadrics, shifted surface splines and Gaussians.     

Approximation power of RBFs and their associated SBFs: a connection

Error estimates for scattered data interpolation by “shifts” of a conditionally positive definite function (CPD) for target functions in its native space, which is its associated reproducing kernel Hilbert space (RKHS), have been known for a long time. Regardless of the underlying manifold, for example ℝⁿ or S ⁿ, these error estimates are determined by the rate of decay of the Fourier transform (or Fourier series) of the CPD. This paper deals with the restriction of radial basis functions (RBFs), which are radial CPD functions on ℝⁿ⁺¹, to the unit sphere S ⁿ. In the paper, we first strengthen a result derived by two of us concerning an explicit representation of the Fourier–Legendre coefficients of the restriction in terms of the Fourier transform of the RBF. In addition, for RBFs that are related to completely monotonic functions, we derive a new integral representation for these coefficients in terms of the measure generating the completely monotonic function. These representations are then utilized to show that if an RBF has a native space equivalent to a Sobolev space H _s(ℝⁿ⁺¹), then the restriction to S ⁿ has a native space equivalent to H _s−1/2(S ⁿ). In addition, they are used to recover the asymptotic behavior of such coefficients for a wide variety of RBFs. Some of these were known earlier. Joseph D. Ward: Francis J. Narcowich: Research supported by grant DMS-0204449 from the National Science Foundation.     

Sharp estimates for the covering numbers of the Weierstrass fractal kernel

In this paper, we present sharp estimates for the covering numbers of the embedding of the reproducing kernel Hilbert space (RKHS) associated with the Weierstrass fractal kernel into the space of continuous functions. The method we apply is based on the characterization of the infinite-dimensional RKHS generated by the Weierstrass fractal kernel and it requires estimates for the norm operator of orthogonal projections on the RKHS.     

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.     

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.

     

Reproducing Kernel Hilbert Spaces Associated with Analytic Translation-Invariant Mercer Kernels

In this article we study reproducing kernel Hilbert spaces (RKHS) associated with translation-invariant Mercer kernels. Applying a special derivative reproducing property, we show that when the kernel is real analytic, every function from the RKHS is real analytic. This is used to investigate subspaces of the RKHS generated by a set of fundamental functions. The analyticity of functions from the RKHS enables us to derive some estimates for the covering numbers which form an essential part for the analysis of some algorithms in learning theory. The work is supported by City University of Hong Kong (Project No. 7001816), and National Science Fund for Distinguished Young Scholars of China (Project No. 10529101).     

Local uniform error estimates for spherical basis functions interpolation

This paper discusses local uniform error estimates for spherical basis functions (SBFs) interpolation, where error bounds for target functions are restricted on spherical cap. The discussion is first carried out in the native space associated with the smooth SBFs, which is generated by a strictly positive definite zonal kernel. Then, the smooth SBFs are embedded in a larger space that is generated by a less smooth kernel, and for the target functions outside the original native space, the local uniform error estimates are established. Finally, some numerical experiments are given to illustrate the theoretical results. Copyright © 2013 John Wiley & Sons, Ltd.     

Learning Theory Estimates via Integral Operators and Their Approximations

The regression problem in learning theory is investigated with least square Tikhonov regularization schemes in reproducing kernel Hilbert spaces (RKHS). We follow our previous work and apply the sampling operator to the error analysis in both the RKHS norm and the L² norm. The tool for estimating the sample error is a Bennet inequality for random variables with values in Hilbert spaces. By taking the Hilbert space to be the one consisting of Hilbert-Schmidt operators in the RKHS, we improve the error bounds in the L² metric, motivated by an idea of Caponnetto and de Vito. The error bounds we derive in the RKHS norm, together with a Tsybakov function we discuss here, yield interesting applications to the error analysis of the (binary) classification problem, since the RKHS metric controls the one for the uniform convergence.     

Reproducing Kernel Hilbert Spaces and fractal interpolation

Reproducing Kernel Hilbert Spaces (RKHSs) are a very useful and powerful tool of functional analysis with application in many diverse paradigms, such as multivariate statistics and machine learning. Fractal interpolation, on the other hand, is a relatively recent technique that generalizes traditional interpolation through the introduction of self-similarity. In this work we show that the functional space of any family of (recurrent) fractal interpolation functions ((R)FIFs) constitutes an RKHS with a specific associated kernel function, thus, extending considerably the toolbox of known kernel functions and introducing fractals to the RKHS world. We also provide the means for the computation of the kernel function that corresponds to any specific fractal RKHS and give several examples.     

Radial kernels and their reproducing kernel Hilbert spaces

We describe how to use Schoenberg’s theorem for a radial kernel combined with existing bounds on the approximation error functions for Gaussian kernels to obtain a bound on the approximation error function for the radial kernel. The result is applied to the exponential kernel and Student’s kernel. To establish these results we develop a general theory regarding mixtures of kernels. We analyze the reproducing kernel Hilbert space (RKHS) of the mixture in terms of the RKHS’s of the mixture components and prove a type of Jensen inequality between the approximation error function for the mixture and the approximation error functions of the mixture components.     

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.     

Reproducing Properties of Differentiable Mercer-Like Kernels on the Sphere

We study differentiability of functions in the reproducing kernel Hilbert space (RKHS) associated with a smooth Mercer-like kernel on the sphere. We show that differentiability up to a certain order of the kernel yields both, differentiability up to the same order of the elements in the series representation of the kernel and a series representation for the corresponding derivatives of the kernel. These facts are used to embed the RKHS into spaces of differentiable functions and to deduce reproducing properties for the derivatives of functions in the RKHS. We discuss compactness and boundedness of the embedding and some applications to Gaussian-like kernels.     

Weighted Fourier–Laplace transforms in reproducing kernel Hilbert spaces on the sphere

We study the action of a weighted Fourier–Laplace transform on the functions in the reproducing kernel Hilbert space (RKHS) associated with a positive definite kernel on the sphere. After defining a notion of smoothness implied by the transform, we show that smoothness of the kernel implies the same smoothness for the generating elements (spherical harmonics) in the Mercer expansion of the kernel. We prove a reproducing property for the weighted Fourier–Laplace transform of the functions in the RKHS and embed the RKHS into spaces of smooth functions. Some relevant properties of the embedding are considered, including compactness and boundedness. The approach taken in the paper includes two important notions of differentiability characterized by weighted Fourier–Laplace transforms: fractional derivatives and Laplace–Beltrami derivatives.     

Approximation in rough native spaces by shifts of smooth kernels on spheres

Within the conventional framework of a native space structure, a smooth kernel generates a small native space, and “radial basis functions” stemming from the smooth kernel are intended to approximate only functions from this small native space. Therefore their approximation power is quite limited. Recently, Narcowich et al. (J. Approx. Theory 114 (2002) 70), and Narcowich and Ward (SIAM J. Math. Anal., to appear), respectively, have studied two approaches that have led to the empowerment of smooth radial basis functions in a larger native space. In the approach of [NW], the radial basis function interpolates the target function at some scattered (prescribed) points. In both approaches, approximation power of the smooth radial basis functions is achieved by utilizing spherical polynomials of a (possibly) large degree to form an intermediate approximation between the radial basis approximation and the target function. In this paper, we take a new approach. We embed the smooth radial basis functions in a larger native space generated by a less smooth kernel, and use them to approximate functions from the larger native space. Among other results, we characterize the best approximant with respect to the metric of the larger native space to be the radial basis function that interpolates the target function on a set of finite scattered points after the action of a certain multiplier operator. We also establish the error bounds between the best approximant and the target function.     

Online Gradient Descent Learning Algorithms

This paper considers the least-square online gradient descent algorithm in a reproducing kernel Hilbert space (RKHS) without an explicit regularization term. We present a novel capacity independent approach to derive error bounds and convergence results for this algorithm. The essential element in our analysis is the interplay between the generalization error and a weighted cumulative error which we define in the paper. We show that, although the algorithm does not involve an explicit RKHS regularization term, choosing the step sizes appropriately can yield competitive error rates with those in the literature.     

Oracle inequalities for support vector machines that are based on random entropy numbers

In this paper, we present a new technique for bounding local Rademacher averages of function classes induced by a loss function and a reproducing kernel Hilbert space (RKHS). At the heart of this technique lies the observation that certain expectations of random entropy numbers can be bounded by the eigenvalues of the integral operator associated with the RKHS. We then work out the details of the new technique by establishing two new oracle inequalities for support vector machines, which complement and generalize previous results.     

On the structure of function spaces in optimal recovery of point functionals for ENO-schemes by radial basis functions

Summary. Radial basis functions are used in the recovery step of finite volume methods for the numerical solution of conservation laws. Being conditionally positive definite such functions generate optimal recovery splines in the sense of Micchelli and Rivlin in associated native spaces. We analyse the solvability to the recovery problem of point functionals from cell average values with radial basis functions. Furthermore, we characterise the corresponding native function spaces and provide error estimates of the recovery scheme. Finally, we explicitly list the native spaces to a selection of radial basis functions, thin plate splines included, before we provide some numerical examples of our method. Received March 14, 1995     

Orthogonality from disjoint support in reproducing kernel Hilbert spaces

We investigate reproducing kernel Hilbert spaces (RKHS) where two functions are orthogonal whenever they have disjoint support. Necessary and sufficient conditions in terms of feature maps for the reproducing kernel are established. We also present concrete examples of finite dimensional RKHS and RKHS with a translation invariant reproducing kernel. In particular, it is shown that a Sobolev space has the orthogonality from disjoint support property if and only if it is of integer index.     

Least-squares regularized regression with dependent samples and q-penalty

Least-squares regularized learning algorithms for regression were well-studied in the literature when the sampling process is independent and the regularization term is the square of the norm in a reproducing kernel Hilbert space (RKHS). Some analysis has also been done for dependent sampling processes or regularizers being the qth power of the function norm (q-penalty) with 0?q?≤?2. The purpose of this article is to conduct error analysis of the least-squares regularized regression algorithm when the sampling sequence is weakly dependent satisfying an exponentially decaying α-mixing condition and when the regularizer takes the q-penalty with 0?q?≤?2. We use a covering number argument and derive learning rates in terms of the α-mixing decay, an approximation condition and the capacity of balls of the RKHS.