Kernel-based Approximation Methods using MATLAB

The following sections are included:

• Dedication
• Preface
• Contents

The following sections are included:

• Positive Definite Kernels: Where Do They Fit in the Mathematical Landscape?
• A Historical Perspective
• The Fundamental Application: Scattered Data Fitting
  • The Haar–Mairhuber–Curtis theorem: Why using kernels is a “natural” approach
  • Variations of scattered data fitting
• Other Applications
  • Statistical data fitting
  • Machine learning
  • Numerical solution of PDEs
  • Computational finance
• Topics We Do Not Cover

In this chapter we provide an overview of the fundamental theoretical concepts — mostly from functional analysis — that are needed to make sense of the more computational and algorithmic material in the later parts of this book. We introduce the notion of a positive definite kernel, provide a basic review of Hilbert–Schmidt theory including Mercer's theorem, and also discuss the Karhunen–Loève expansion theorem, which plays a central role for the stochastic framework in Chapter 5 as well as for many applications in uncertainty quantification. In the second half of the chapter some basic properties of reproducing kernel Hilbert spaces, including connections to feature maps, are stated and some background on the eigenvalue problem for integral operators is provided along with a few examples. Some basic facts from functional analysis that may support the discussion in this chapter are provided in Appendix C.

In this chapter we provide an overview of many different types of positive definite kernels. We focus on their definition and on some of their properties, while in the next chapter we add a discussion of the different kinds of implementations in MATLAB and then use the code to produce plots of some of the kernels featured below.

We start with the case of radial kernels (or radial basis functions), which may be one of the most popular types of kernels discussed in the literature. Then we move on to more general translation invariant kernels and kernels given in series form. Other types of kernels discussed below include general anisotropic kernels, dot product kernels (including zonal kernels on spheres), tensor product kernels, multiscale kernels, space-time kernels and so-called "learned" kernels. We also discuss some recent advances in compactly supported radial kernels and close the chapter with some ideas concerning designer kernels, i.e., kernels which are created either from other positive definite kernels or as infinite series.

Many discussions in this book focus on the theoretical underpinnings of positive definite kernels, without which this text would have no relevance. Simultaneously, however, this book is also concerned with the computational methods used to evaluate and manipulate kernels for interpolation and other mathematical problems. In this chapter, we revisit the various forms of kernels introduced in Chapter 3 and consider implementations in MATLAB that both are efficient computationally and leverage the unique functionality offered in MATLAB…

The kriging approach is a stochastic prediction method that arose in geostatistics and is named after the South African mining engineer Danie Krige (1951), who used this method in his work predicting gold ore distributions from a collection of ore samples. The method was given a solid mathematical foundation and shown to be an optimal linear prediction method by the French mathematician and geostatistician Georges Matheron (1965)…

The following sections are included:

• Introduction
• Green's Kernels Defined
• Differential Eigenvalue Problems
• Computing Green's Kernels
  • An example: Computing the Brownian bridge kernel as Green's kernel
  • Generalizations of the Brownian bridge kernel
• Classical Examples of Green's Kernels
• Sturm–Liouville Theory
• Eigenfunction Expansions
• The Connection Between Hilbert–Schmidt and Sturm–Liouville Eigenvalue Problems
• Limitations
• Summary

In this chapter we will derive series representations — and where feasible also closedform representations — of the family of univariate anisotropic kernels we earlier referred to as iterated Brownian bridge kernels (cf. Example 6.2). We separate the discussion into two parts. First we discuss the case of piecewise polynomial splines (when the shape parameter ε = 0), and then we look at the more general case. In the second part of the chapter we will discuss various properties of these kernels in the context of examples implemented in MATLAB.

Our goal in this chapter is to develop “the right tool for the right job.” We will show that — starting from a linear self-adjoint differential operator L with or without appropriate boundary conditions — we can specify an inner product and then produce the associated reproducing kernel which is optimal for our intended use. In doing so, we can rely on the norm minimization property of a kernel-based interpolant to produce, arguably, the optimal kernel interpolant by the metric given by our chosen inner product. This strategy is reminiscent of the variational approach to curve and surface design in computer-aided geometric design (see, e.g., [Sapidis (1987)]), where aesthetically looking curves or surfaces are obtained by specifying different kinds of norms to be minimized. These ideas go back to at least the splines in tension of Schweikert (1966).

The following sections are included:

• Optimality
• Different Types of Error
• The “Standard” Error Bound
• Error Bounds via Sampling Inequalities
  • How sampling inequalities lead to error bounds
  • Univariate sampling inequalities and error bounds
  • Application to iterated Brownian bridge kernels
  • Sampling inequalities in higher dimensions
• Dimension-independent error bounds
  • Traditional dimension-dependent error bounds
  • Worst-case weighted L₂ error bounds

In this chapter we take a closer look at the effect of the shape parameter ε present in the definition of many of our kernels. In particular, we are interested in understanding the behavior of radial kernel interpolants (cf. Section 3.1) in the limiting case as ε → 0, i.e., the increasingly “flat” limit.

The results in this chapter specifically address the scattered data interpolation problem. In other words, we are given data sites with associated data values {y₁, … , y_N} sampled from some function f and wish to reconstruct f by a function of the form

In the previous chapter we learned that there is a theoretical “flat” limit for kernelbased interpolation, and we also said that this limit might be difficult to achieve computationally. We now provide a typical plot for a very simple univariate interpolation problem with increasingly wider Gaussian kernels, i.e., taking ε to zero.

The main focus of this chapter is to start thinking about different ways to evaluate the kernel interpolant (see (1.3))

In Chapter 10 we established the fact that the kernel-based interpolation problem is well-posed in the flat limit, and then contrasted this in Chapter 11 with the historical belief — and misconception — that increasingly flat kernels are able to provide more accurate interpolants only in exact arithmetic, because the interpolation problem simultaneously becomes more and more ill-conditioned. As explained in Chapter 11, this misconception stems from the fact that the standard basis {K(·, x₁), … , K(·, x_N)} is often insufficient for computing a stable solution in finite precision. Therefore, we were led to investigate alternate bases for stably solving the scattered data interpolation problem in Chapter 12. Alternate bases provide a useful framework for avoiding the ill-conditioning of the flat limit, but the strategy of deriving an alternate basis by decomposing the K matrix likely suffers from the same instabilities present in interpolation. This suggests the need for techniques other than those employed in Chapter 12…

So far, we have introduced two ways in which we can approach the scattered data interpolation task formalized in Problem 1.1: the deterministic approach outlined briefly in Section 1.3 resulting in an interpolant of the form , and the stochastic approach discussed in Chapter 5 which leads to the (simple) kriging prediction . Since the right-hand sides for these two approaches are identical we can see that under certain circumstances they yield the same result…

In Chapter 9 we showed that the kernel interpolant s is the “smoothest” interpolant at X = {x₁, … , x_N} with values y_i = f(x_i), i = 1,…,N, in the sense that s is the interpolant that has minimum Hilbert space norm . In fact, one can formulate this problem as a constrained optimization problem, i.e., we want to find s ∈ H_K(Ω) such that we

The following sections are included:

• Surrogate Modeling
• Experimental Design
• Surrogate Models for Standard Test Functions
  • Piston simulation function
  • Borehole function
• Modeling From Data
• Fitting Empirical Distribution Functions

In Chapter 5 we introduced the use of Gaussian processes as a statistical technique for conducting scattered data fitting. In this chapter we demonstrate the use of these kriging strategies on examples from geostatistics. These examples employ the criteria for optimal parametrizations of the covariance kernel, as introduced in Chapter 14, and some of our examples include the use of estimation to find nonzero mean functions…

In problems we have studied thus far, we have been given data of the form , where x_i ∈ Ω ⊂ ℝ^d and y_i ∈ ℝ, and have asked to develop an approximating function s which can be used to predict s(x) ≈ y for some previously unobserved x value. In Section 1.3, we introduced the scattered data fitting approach, which chose a set of N basis functions and constructed s as a linear combination of those basis functions such that , where y = (y₁ … y_N)^T and s = (s(x₁) … s(x_N))^T. Along the same lines, in Section 12.3, we discussed a modification to this strategy, where s was a linear combination of only M < N basis functions and was constructed to solve . Another technique to fit this data was introduced in Chapter 5 where we assumed that the data was realized by a Gaussian random field Y with a specified covariance and we constructed s such that …

In this chapter we consider two tasks involving derivatives:

• Approximating the derivative of an unknown function u from given data of the form {x_i, u(x_i)}, i = 1, …, N. This task is sometimes referred to as derivative estimation, and will give us an opportunity to introduce the reader to differentiation matrices. Since this problem is approached by first computing a standard kernel-based interpolant to the given data (as discussed throughout this book) and then simply differentiating this interpolant, this process is sometimes referred to as simultaneous approximation in the approximation theory literature.
• Approximating an unknown function u from given data of the form {x_i, L_iu}, i = 1, …, N, where the L_i are bounded linear functionals (including point evaluation and derivative evaluation). This task is known in the numerical analysis and approximation theory literature under the names Hermite interpolation, Hermite–Birkhoff interpolation, or generalized Hermite interpolation; and in the statistics literature as kriging with derivative information or gradient-enhanced kriging

In Chapter 19 we developed the use of differentiation matrices and similar strategies for evaluating derivatives of interpolants. We also applied these ideas in Section 19.4 to couple boundary value problems through an interface by exchanging derivative data between two different computational models. There the individual components, however, were solved using standard (polynomial) finite difference methods. In this chapter we discuss how to add to the list of traditional PDE solvers, such as those finite difference methods, by developing kernel-based methods for the numerical solution of boundary value problems…

This chapter introduces topics from finance, where kernel methods are either fundamental to the structure of the solution scheme or a useful tool to approximate quantities of interest. Because of the complex stochastic nature of financial problems, and the numerous strategies available for gaining insights into them, we restrict ourselves primarily to the application of previously discussed ideas in the financial setting…

The following sections are included:

• Collection of Positive Definite Kernels and Their Known Mercer Series
• How To Choose the Data Sites
• A Few Facts from Analysis and Probability
• The GaussQR Repository in MATLAB

The following sections are included:

• Bibliography
• Index