Symmetric, positive definite functions are kernels (feature space in the universe of )
ProvedSupportVectorMachines.Kernels.theorem_4_16_symmetric_pd_iff_kernel_v2This is Theorem 4.16 of Steinwart & Christmann, Support Vector Machines (Springer 2008, p. 118): a function on a non-empty set is a kernel if and only if it is symmetric and positive definite,
The "only if" direction follows from : symmetry of the real inner product, and . The "if" direction builds the feature space intrinsically: the completion of the pre-Hilbert space of finite linear combinations of the functions , with feature map .
Formalization Note. The mathematics of the retired version was correct; it was refuted only by a Lean universe artefact: IsKernel fixed the feature space to universe while ranged over every universe, so for an too large to embed in universe (Ordinal.{0}) the Kronecker kernel was symmetric and positive definite but had no universe- feature space. The corrected IsKernel quantifies the feature space over the universe of , where the book's construction lives (and any feature space in a larger universe can be replaced by the closed span of , isometric to one in the universe of ); Symmetric and PositiveDefinite are Definition 4.15 unchanged, and is non-empty as in Definition 4.1.
import Mathlib import Definitions.Def_SupportVectorMachines_Kernels_IsKernel_v2 import Definitions.Def_SupportVectorMachines_Kernels_PositiveDefinite universe u
namespace SupportVectorMachines.Kernels
/-- Theorem 4.16 (Symmetric, positive definite functions are kernels), Steinwart & Christmann,
*Support Vector Machines*, Springer 2008, p. 118: a function `k : X × X → ℝ` on a non-empty set
`X` is a kernel if and only if it is symmetric and positive definite. Here `IsKernel` quantifies
the feature space over the same universe as `X` (the retired `IsKernel` fixed it to universe `0`
while `X` was arbitrary, a Lean universe artefact that made the "if" direction refutable for a
large `X`; the mathematics is unchanged). Corrected version of
`theorem_4_16_symmetric_pd_iff_kernel`. -/
theorem theorem_4_16_symmetric_pd_iff_kernel_v2 {X : Type u} [Nonempty X] (k : X → X → ℝ) :
IsKernel k ↔ Symmetric k ∧ PositiveDefinite k := by sorry
end SupportVectorMachines.Kernels