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, embedding problem, information theory, and other areas. This article  will discuss some of the historical and current developments of the theory of positive-definite kernels, starting with the general idea and properties before considering practical applications. Definition. Let formula_1 be a nonempty set, sometimes referred to as the index set. A symmetric function formula_2 is called a positive-definite (p.d.) kernel on formula_3 if holds for any formula_5, given formula_6. In probability theory, a distinction is sometimes made between positive-definite kernels, for which equality in (1.1) implies formula_7, 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, formula_8, has either entirely positive (p.d.) or nonnegative (p.s.d.) eigenvalues. In mathematical literature, kernels are usually complex valued functions, but in this article we assume real-valued functions, which is the common practice in applications of p.d. kernels. can be used to define p.d. kernels using the following formula History. Positive-definite kernels, as defined in (1.1), appeared first in 1909 in a paper on integral equations by James Mercer. Several other authors made use of this concept in the following two decades, but none of them explicitly used kernels formula_43, 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 where formula_46 is a continuous real symmetric kernel, formula_47 is continuous, formula_48 is a complete system of orthonormal eigenfunctions, and formula_49’s are the corresponding eigenvalues of (1.2). Hilbert defined a “definite” kernel as one for which the double integral satisfies formula_51 except for formula_52. 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 formula_53 to be of positive type (i.e. positive-definite) if formula_54 for all real continuous functions formula_47 on formula_56, 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, motivated by a different  question in the theory of integral equations, showed that for continuous kernels condition (1.1) is equivalent to formula_54 for all formula_59. E.H. Moore initiated the study of a very general kind of p.d. kernel. If formula_60 is an abstract set, he calls functions formula_61 defined on formula_62 “positive Hermitian matrices” if they satisfy (1.1) for all formula_63. Moore was interested in generalization of integral equations and showed that to each such formula_46 there is a Hilbert space formula_34 of functions such that, for each formula_66. 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. Let formula_67 be a set, formula_34 a Hilbert space of functions formula_69, and formula_35 the corresponding inner product on formula_34. For any formula_72 the evaluation functional formula_73 is defined by formula_74. We first define a reproducing kernel Hilbert space (RKHS): Definition: Space formula_34 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 formula_76 such that The latter property is called the reproducing property. The following result shows equivalence between RKHS and reproducing kernels: Theorem: Every reproducing kernel formula_46 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 formula_46, it is possible  to build an associated RKHS with formula_46 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 formula_84 be a Hilbert space, and formula_85 the corresponding inner product. Any map formula_86 is called a feature map. In this case we call formula_84 the feature space. It is easy to see that every feature map defines a unique p.d. kernel by Indeed, positive definiteness of formula_46 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 formula_90, and formula_91 for all formula_72. Then formula_93, 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 formula_47 and formula_95 are through the value formula_61. 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 formula_46 and distances formula_98. Here by a distance function between each pair of elements of some set formula_67, we mean a metric defined on that set, i.e. any nonnegative-valued function formula_98 on formula_101 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 formula_107 is called a negative definite (n.d.) kernel on  formula_3 if holds for any formula_110 and formula_111 such that formula_112. The parallel between n.d. kernels and distances is in the following: whenever a n.d. kernel vanishes on the set formula_113, and is zero only on this set, then its square root is a distance for formula_3. At the same time each distance does not correspond necessarily to a n.d. kernel. This is only true for Hilbertian distances, where distance formula_98 is called Hilbertian if one can embed the metric space formula_116 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 formula_46 is said to be infinitely divisible if for every formula_118 there exists a positive-definite kernel formula_119 such that formula_120. Another link is that a p.d. kernel induces a pseudometric, where the first constraint on the distance function is loosened to allow formula_121 for formula_122. Given a positive-definite kernel formula_123, we can define a distance function as: Some applications. Kernels in machine learning. 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 formula_145, with zero mean and variance formula_146, is added to formula_47, such that the noise is independent for different formula_47 and independent of formula_149 there , then the problem of finding a good estimate for formula_126 is identical to the above one, but with a modified kernel given by formula_151. 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. 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.