Positive-definite kernel on arvau

Wikipedia / Positive-definite kernel

In operator theory, a branch of mathematics, a positive-definite kernel is a generalization of a positive-definite function or a positive-definite matrix. It was first introduced by James Mercer in the early 20th century, in the context of solving integral operator equations. Since then, positive-definite functions and their various analogues and generalizations have arisen in diverse parts of mathematics. They occur naturally in Fourier analysis, probability theory, operator theory, complex function-theory, moment problems, integral equations, boundary-value problems for partial differential equations, machine learning, the embedding problem, information theory, and other areas.

Definition

be a nonempty set, sometimes referred to as the index set. A symmetric function if .

, has either entirely positive (p.d.) or nonnegative (p.s.d.) eigenvalues.

is called a Hermitian kernel and positive definite if for every finite set,

denotes the complex conjugate. In the rest of this article we assume real-valued functions, which is the common practice in applications of p.d. kernels.

Some general properties

is p.d. if the limit exists.
.
is also a p.d. kernel.

Examples of p.d. kernels

Common examples of p.d. kernels defined on Euclidean space include:

.
Polynomial kernel.
Gaussian kernel (RBF kernel.
.
.
Kernel generating Sobolev spaces is the Bessel function of the third kind.
.
is a Hilbert space
and histograms: Histograms are frequently encountered in applications of real-life problems. Most observations are usually available under the form of nonnegative vectors of counts, which, if normalized, yield histograms of frequencies. It has been shown -square, Total Variation, and two variations of the Hellinger distance:can be used to define p.d. kernels using the following formula

Examples of other kernels

are real parameters. The kernel is not PD, but has been sometimes used for kernel algorithms.

History

Positive-definite kernels, as defined in (1.1), appeared first in 1909 in a paper on integral equations by James Mercer., i.e. p.d. functions (indeed M. Mathias and S. Bochner seem not to have been aware of the study of p.d. kernels). Mercer’s work arose from Hilbert’s paper of 1904 on Fredholm integral equations of the second kind:

In particular, Hilbert had shown that is a complete system of orthonormal eigenfunctions’s are the corresponding eigenvalues holds absolutely and uniformly.

At about the same time W. H. Young,.

E.H. Moore . This property is called the reproducing property of the kernel and turns out to have importance in the solution of boundary-value problems for elliptic partial differential equations.

Another line of development in which p.d. kernels played a large role was the theory of harmonics on homogeneous spaces as begun by E. Cartan in 1929, and continued by H. Weyl and S. Ito. The most comprehensive theory of p.d. kernels in homogeneous spaces is that of M. Krein which includes as special cases the work on p.d. functions and irreducible unitary representations of locally compact groups.

In probability theory, p.d. kernels arise as covariance kernels of stochastic processes.

Connection with reproducing kernel Hilbert spaces and feature maps

Positive-definite kernels provide a framework that encompasses some basic Hilbert space constructions. In the following we present a tight relationship between positive-definite kernels and two mathematical objects, namely reproducing Hilbert spaces and feature maps.

the corresponding inner product on . We first define a reproducing kernel Hilbert space (RKHS):

Definition is called a reproducing kernel Hilbert space if the evaluation functionals are continuous.

Every RKHS has a special function associated to it, namely the reproducing kernel:

Definition such that

, and
.

The latter property is called the reproducing property.

The following result shows equivalence between RKHS and reproducing kernels:

Now the connection between positive definite kernels and RKHS is given by the following theorem

as a reproducing kernel.

the feature space. It is easy to see . Moreover, through the equivalence of p.d. kernels and its corresponding RKHS, every feature map can be used to construct a RKHS.

Kernels and distances

Kernel methods are often compared to distance based methods such as nearest neighbors.

, we mean a metric which satisfies

if and only if,

One link between distances and p.d. kernels is given by a particular kind of kernel, called a negative definite kernel, and defined as follows

Definition if . . isometrically into some Hilbert space.

Another link is that a p.d. kernel induces a pseudometric

Some applications

Kernels in machine learning

Positive-definite kernels, through their equivalence with reproducing kernel Hilbert spaces (RKHS), are particularly important in the field of statistical learning theory because of the celebrated representer theorem which states that every minimizer function in an RKHS can be written as a linear combination of the kernel function evaluated at the training points. This is a practically useful result as it effectively simplifies the empirical risk minimization problem from an infinite dimensional to a finite dimensional optimization problem.

Kernels in probabilistic models

There are several different ways in which kernels arise in probability theory.

can be obtained by using kernel interpolation with the covariance kernel, ignoring the probabilistic background completely.

as a smooth estimate.

Numerical solution of partial differential equations

One of the greatest application areas of so-called meshfree methods is in the numerical solution of PDEs. Some of the popular meshfree methods are closely related to positive-definite kernels (such as meshless local Petrov Galerkin (MLPG), Reproducing kernel particle method (RKPM) and smoothed-particle hydrodynamics (SPH)). These methods use radial basis kernel for collocation.

Stinespring dilation theorem

Other applications

In the literature on computer experiments and other engineering experiments, one increasingly encounters models based on p.d. kernels, RBFs or kriging. One such topic is response surface methodology. Other types of applications that boil down to data fitting are rapid prototyping and computer graphics. Here one often uses implicit surface models to approximate or interpolate point cloud data.

Applications of p.d. kernels in various other branches of mathematics are in multivariate integration, multivariate optimization, and in numerical analysis and scientific computing, where one studies fast, accurate and adaptive algorithms ideally implemented in high-performance computing environments.