Regularized kernel prediction system

Let $\mathcal{X}$ be a set, $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ a real positive-semidefinite kernel, and $\mathcal{H}$ a real reproducing-kernel Hilbert space with kernel $k$. Let $X=(x_i{)}_{i=1}^n$ be a nonempty finite ordered training list in $\mathcal{X}$, let $K=(k(x_i,x_j){)}_{i,j=1}^n$, let $y\in {\mathbb{R}}^n$, and let $\lambda >0$. Set $\tau =n\lambda$ and define the mean-square empirical objective

$J(f)=\frac{1}{n}{\sum }_{i=1}^n(y_i-f(x_i){)}^2+\lambda \parallel f{\parallel }_{\mathcal{H}}^2\mathrm{.}$

For any finite real symmetric positive-semidefinite matrix $G\in {\mathbb{R}}^{n\times n}$, define its regularized kernel prediction system by $a_G=(G+\tau I_n{)}^{-1}y$ and $u_G=G{a}_G$, where $I_n$ is the $n\times n$ identity matrix. The original training system uses $G=K$. The same definition applies to any positive-semidefinite matrix approximation $\tilde{K}$ of $K$, with $a_{\tilde{K}}=(\tilde{K}+\tau I_n{)}^{-1}y$ and $u_{\tilde{K}}=\tilde{K}{a}_{\tilde{K}}$. In either case $u_G=y-\tau a_G$. The scalar $\tau =n\lambda$ fixes the normalization between mean-square loss and the unnormalized finite linear system.

A real positive-semidefinite kernel has nonnegative finite Gram quadratic forms, and its RKHS reproduces the kernel sections.

The definitions allow $K$ to be singular or zero. More generally, for every finite real symmetric positive-semidefinite $G$ and $\tau >0$, each nonzero $x$ satisfies $x^T(G+\tau I_n)x=x^{T}Gx+\tau \parallel x{\parallel }_2^2\ge \tau \parallel x{\parallel }_2^2>0$. Thus each shifted matrix in the definition is positive definite and invertible, including when $G=K$ or $G=\tilde{K}$; no full-rank assumption is placed on the kernel Gram matrix or on a sketch.