Positive semidefinite kernels and reproducing kernel Hilbert spaces

A real kernel on a set $X$ is a function $k:X\times X\to \mathbb{R}$. It is positive semidefinite if it is symmetric and, for every integer $n\ge 1$, every $x_1,\dots ,x_n\in X$, and every $c_1,\dots ,c_n\in \mathbb{R}$,

${\sum }_{i=1}^n{\sum }_{j=1}^n{c}_i{c}_{j}k(x_i,x_j)\ge 0.$

A real reproducing kernel Hilbert space with kernel $k$ is a real Hilbert space $\mathcal{H}$ of functions $X\to \mathbb{R}$ such that, for each $x\in X$, the section $k_x:=k(\cdot ,x)$ lies in $\mathcal{H}$ and $⟨f,k_x{⟩}_{\mathcal{H}}=f(x)$ for every $f\in \mathcal{H}$. Consequently $⟨k_z,k_x{⟩}_{\mathcal{H}}=k(z,x)=k(x,z)$.

For the canonical construction, let $E_0$ be the real vector space of finitely supported functions $a:X\to \mathbb{R}$, write ${\delta }_x$ for the function supported at $x$ with value $1$, and put

$B(a,b):={\sum }_{x\in \mathrm{supp}(a)}{\sum }_{z\in \mathrm{supp}(b)}a(x)b(z)k(x,z)\mathrm{.}$

Let $N:=\{a\in E_0:B(a,a)=0\}$. Under the Axiom of Countable Choice, the canonical space is formed by giving $E_0\mathrm{/}N$ its induced inner product and taking a norm completion; the image of ${\delta }_x$ is denoted $k_x$. For an element $h$ of that completion, its associated function is $x\mapsto ⟨h,k_x⟩$. The quotient, completed inner product, and function identification are justified by the local construction theorem.

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §5.8

Rasmussen and Williams, Gaussian Processes for Machine Learning, §§6.1–6.2

Real and complex inner product spaces, with the inner product linear in the first argument

Hilbert space

Completion of a normed space

The Axiom of Countable Choice (${\mathrm{A}\mathrm{C}}_{\omega }$)

A positive semidefinite kernel has a canonical reproducing kernel Hilbert space under countable choice ↗