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, embedding problem, information theory, and other areas.


Let be a nonempty set, sometimes referred to as the index set. A symmetric function is called a positive-definite (p.d.) kernel on if






holds for any , given .

In probability theory, a distinction is sometimes made between positive-definite kernels, for which equality in (1.1) implies , and positive semi-definite (p.s.d.) kernels, which do not impose this condition. Note that this is equivalent to requiring that any finite matrix constructed by pairwise evaluation, , has either entirely positive (p.d.) or nonnegative (p.s.d.) eigenvalues.

In mathematical literature, kernels are usually complex valued functions. That is, a complex valued function is called a Hermitian kernel if and positive definite if for any finite set of points and any complex numbers ,

where denotes the complex conjugate.[1] 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

Examples of p.d. kernels


See also: Mercer's theorem

Positive-definite kernels, as defined in (1.1), appeared first in 1909 in a paper on integral equations by James Mercer.[3] Several other authors made use of this concept in the following two decades, but none of them explicitly used kernels , 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 [4] on Fredholm integral equations of the second kind:






In particular, Hilbert had shown that






where is a continuous real symmetric kernel, is continuous, is a complete system of orthonormal eigenfunctions, and ’s are the corresponding eigenvalues of (1.2). Hilbert defined a “definite” kernel as one for which the double integral

satisfies except for . The original object of Mercer’s paper was to characterize the kernels which are definite in the sense of Hilbert, but Mercer soon found that the class of such functions was too restrictive to characterize in terms of determinants. He therefore defined a continuous real symmetric kernel to be of positive type (i.e. positive-definite) if for all real continuous functions on , and he proved that (1.1) is a necessary and sufficient condition for a kernel to be of positive type. Mercer then proved that for any continuous p.d. kernel the expansion
holds absolutely and uniformly.

At about the same time W. H. Young,[5] motivated by a different question in the theory of integral equations, showed that for continuous kernels condition (1.1) is equivalent to for all .

E.H. Moore [6][7] initiated the study of a very general kind of p.d. kernel. If is an abstract set, he calls functions defined on “positive Hermitian matrices” if they satisfy (1.1) for all . Moore was interested in generalization of integral equations and showed that to each such there is a Hilbert space of functions such that, for each . 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[8] 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.[9]

Connection with reproducing kernel Hilbert spaces and feature maps

Further information: Reproducing kernel Hilbert space

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.

Let be a set, a Hilbert space of functions , and the corresponding inner product on . For any the evaluation functional is defined by . We first define a reproducing kernel Hilbert space (RKHS):

Definition: Space 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: Reproducing kernel is a function such that

  1. , and
  2. , for all and .

The latter property is called the reproducing property.

The following result shows equivalence between RKHS and reproducing kernels:

Theorem —  Every reproducing kernel induces a unique RKHS, and every RKHS has a unique reproducing kernel.

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

Theorem —  Every reproducing kernel is positive-definite, and every positive definite kernel defines a unique RKHS, of which it is the unique reproducing kernel.

Thus, given a positive-definite kernel , it is possible to build an associated RKHS with as a reproducing kernel.

As stated earlier, positive definite kernels can be constructed from inner products. This fact can be used to connect p.d. kernels with another interesting object that arises in machine learning applications, namely the feature map. Let be a Hilbert space, and the corresponding inner product. Any map is called a feature map. In this case we call the feature space. It is easy to see [10] that every feature map defines a unique p.d. kernel by

Indeed, positive definiteness of follows from the p.d. property of the inner product. On the other hand, every p.d. kernel, and its corresponding RKHS, have many associated feature maps. For example: Let , and for all . Then , by the reproducing property. This suggests a new look at p.d. kernels as inner products in appropriate Hilbert spaces, or in other words p.d. kernels can be viewed as similarity maps which quantify effectively how similar two points and are through the value . 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. In this section we discuss parallels between their two respective ingredients, namely kernels and distances .

Here by a distance function between each pair of elements of some set , we mean a metric defined on that set, i.e. any nonnegative-valued function on which satisfies

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: A symmetric function is called a negative definite (n.d.) kernel on if






holds for any and such that .

The parallel between n.d. kernels and distances is in the following: whenever a n.d. kernel vanishes on the set , and is zero only on this set, then its square root is a distance for .[11] At the same time each distance does not correspond necessarily to a n.d. kernel. This is only true for Hilbertian distances, where distance is called Hilbertian if one can embed the metric space isometrically into some Hilbert space.

On the other hand, n.d. kernels can be identified with a subfamily of p.d. kernels known as infinitely divisible kernels. A nonnegative-valued kernel is said to be infinitely divisible if for every there exists a positive-definite kernel such that .

Another link is that a p.d. kernel induces a pseudometric, where the first constraint on the distance function is loosened to allow for . Given a positive-definite kernel , we can define a distance function as:

Some applications

Kernels in machine learning

Further information: Kernel method

Positive-definite kernels, through their equivalence with reproducing kernel Hilbert spaces, 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.

Assume now that a noise variable , with zero mean and variance , is added to , such that the noise is independent for different and independent of there, then the problem of finding a good estimate for is identical to the above one, but with a modified kernel given by .

Numerical solution of partial differential equations

Further information: Meshfree methods

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.[12]

Stinespring dilation theorem

Further information: Stinespring dilation theorem

Other applications

In the literature on computer experiments [13] 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.[14]

See also


  1. ^ Berezanskij, Jurij Makarovič (1968). Expansions in eigenfunctions of selfadjoint operators. Providence, RI: American Mathematical Soc. pp. 45–47. ISBN 978-0-8218-1567-0.
  2. ^ Hein, M. and Bousquet, O. (2005). "Hilbertian metrics and positive definite kernels on probability measures". In Ghahramani, Z. and Cowell, R., editors, Proceedings of AISTATS 2005.
  3. ^ Mercer, J. (1909). “Functions of positive and negative type and their connection with the theory of integral equations”. Philosophical Transactions of the Royal Society of London, Series A 209, pp. 415-446.
  4. ^ Hilbert, D. (1904). "Grundzuge einer allgemeinen Theorie der linearen Integralgleichungen I", Gott. Nachrichten, math.-phys. K1 (1904), pp. 49-91.
  5. ^ Young, W. H. (1909). "A note on a class of symmetric functions and on a theorem required in the theory of integral equations", Philos. Trans. Roy.Soc. London, Ser. A, 209, pp. 415-446.
  6. ^ Moore, E.H. (1916). "On properly positive Hermitian matrices", Bull. Amer. Math. Soc. 23, 59, pp. 66-67.
  7. ^ Moore, E.H. (1935). "General Analysis, Part I", Memoirs Amer. Philos. Soc. 1, Philadelphia.
  8. ^ Krein. M (1949/1950). "Hermitian-positive kernels on homogeneous spaces I and II" (in Russian), Ukrain. Mat. Z. 1(1949), pp. 64-98, and 2(1950), pp. 10-59. English translation: Amer. Math. Soc. Translations Ser. 2, 34 (1963), pp. 69-164.
  9. ^ Loève, M. (1960). "Probability theory", 2nd ed., Van Nostrand, Princeton, N.J.
  10. ^ Rosasco, L. and Poggio, T. (2015). "A Regularization Tour of Machine Learning - MIT 9.520 Lecture Notes" Manuscript.
  11. ^ Berg, C., Christensen, J. P. R., and Ressel, P. (1984). "Harmonic Analysis on Semigroups". Number 100 in Graduate Texts in Mathematics, Springer Verlag.
  12. ^ Schaback, R. and Wendland, H. (2006). "Kernel Techniques: From Machine Learning to Meshless Methods", Cambridge University Press, Acta Numerica (2006), pp. 1-97.
  13. ^ Haaland, B. and Qian, P. Z. G. (2010). "Accurate emulators for large-scale computer experiments", Ann. Stat.
  14. ^ Gumerov, N. A. and Duraiswami, R. (2007). "Fast radial basis function interpolation via preconditioned Krylov iteration". SIAM J. Scient. Computing 29/5, pp. 1876-1899.