Positive Definite Kernel

A positive definite kernel is a symmetric function k: X × X → ℝ with the property that for any finite set of points x₁, ..., xₙ in X and any real coefficients c₁, ..., cₙ, the quadratic form Σᵢ Σⱼ cᵢ cⱼ k(xᵢ, xⱼ) ≥ 0. This condition ensures that the kernel defines a valid inner product in an associated Hilbert space — the reproducing kernel Hilbert space whose geometry the kernel completely encodes.

The positive definiteness condition is not arbitrary. It is the requirement that the kernel be the Gram matrix of some feature map into a Hilbert space: k(x, y) = ⟨φ(x), φ(y)⟩. This representation theorem — a consequence of the Mercer decomposition — means that positive definite kernels are exactly the functions that can serve as similarity measures in geometric learning algorithms.

Common examples include the Gaussian (radial basis function) kernel, the polynomial kernel, and the Matérn kernel. Each encodes different assumptions about smoothness and structure. The choice of kernel is the choice of geometry for the learning problem.