RKHS, Representer & Mercer's Theorem

1. 1
   Step 1:

   $$k(x',x)=\langle\phi(x'),\phi(x)\rangle_{\mathcal F}=\langle\phi(x),\phi(x')\rangle_{\mathcal F}=k(x,x')$$

   A real inner product is symmetric, so $k$ is symmetric.
2. 2
   Step 2:

   $$\sum_{i,j}c_ic_j\,k(x_i,x_j)=\sum_{i,j}c_ic_j\,\langle\phi(x_i),\phi(x_j)\rangle_{\mathcal F}$$

   Insert the definition of $k$ into the quadratic form.
3. 3
   Step 3:

   $$=\Big\langle\sum_ic_i\phi(x_i),\sum_jc_j\phi(x_j)\Big\rangle_{\mathcal F}$$

   Bilinearity of the inner product pulls the finite sums and the real coefficients inside.
4. 4
   Step 4:

   $$=\Big\lVert\sum_ic_i\phi(x_i)\Big\rVert_{\mathcal F}^2\ \ge\ 0$$

   The inner product of a vector with itself is its squared norm, which is nonnegative.

∎

1. 1
   Step 1:

   $$m=1,\ c=1:\quad c^2k(x,x)=k(x,x)\ge0$$

   The definition with a single point.
2. 2
   Step 2:

   $$K=\begin{pmatrix}k(x,x)&k(x,x')\\k(x',x)&k(x',x')\end{pmatrix}=K^\top$$

   The Gram matrix of the two points $x,x'$; symmetric because $k$ is.
3. 3
   Step 3:

   $$Kv=\lambda v,\ \lVert v\rVert=1\ \Rightarrow\ \lambda=v^\top Kv\ge0$$

   A real symmetric matrix has real eigenvalues with real unit eigenvectors; taking $c=v$ in the definition shows each eigenvalue is nonnegative.
4. 4
   Step 4:

   $$\det K=\lambda_1\lambda_2\ge0$$

   The determinant is the product of the eigenvalues.
5. 5
   Step 5:

   $$k(x,x)k(x',x')-k(x,x')^2\ge0$$

   Expand the $2\times2$ determinant using $k(x',x)=k(x,x')$.

∎

1. 1
   Step 1:

   $$\langle f,g\rangle_0=\sum_{j=1}^nb_j\sum_{i=1}^ma_i\,k(y_j,x_i)=\sum_{j=1}^nb_j\,f(y_j)$$

   Reorder the finite double sum and use $k(x_i,y_j)=k(y_j,x_i)$; the inner sum is $f(y_j)=\sum_ia_ik(y_j,x_i)$, the value of the function $f$ at $y_j$.
2. 2
   Step 2:

   $$\langle f,g\rangle_0=\sum_{i=1}^ma_i\sum_{j=1}^nb_j\,k(x_i,y_j)=\sum_{i=1}^ma_i\,g(x_i)$$

   Summing in the other order, the inner sum is $g(x_i)=\sum_jb_jk(x_i,y_j)$.
3. 3
   Step 3:

   $$(a_i,x_i)\ \text{and}\ (a'_i,x'_i)\ \text{represent the same}\ f\ \Rightarrow\ \sum_jb_jf(y_j)\ \text{is unchanged}$$

   The first expression involves $f$ only through its values $f(y_j)$, so it cannot depend on how $f$ is written. Likewise the second expression shows independence from the representation of $g$. Changing both representations one after the other leaves the number fixed: the form is well defined on pairs of functions.
4. 4
   Step 4:

   $$\langle g,f\rangle_0=\sum_{j,i}b_ja_i\,k(y_j,x_i)=\sum_{i,j}a_ib_j\,k(x_i,y_j)=\langle f,g\rangle_0$$

   Symmetry of $k$.
5. 5
   Step 5:

   $$\langle\alpha f+\beta f',g\rangle_0=\sum_jb_j\big(\alpha f(y_j)+\beta f'(y_j)\big)=\alpha\langle f,g\rangle_0+\beta\langle f',g\rangle_0$$

   Linearity in the first argument from the first expression, since functions are added and scaled pointwise; linearity in the second argument then follows from symmetry.
6. 6
   Step 6:

   $$\langle f,f\rangle_0=\sum_{i,j=1}^ma_ia_j\,k(x_i,x_j)\ \ge\ 0$$

   This is exactly the quadratic form of the definition of a positive-definite kernel with $c=a$.
7. 7
   Step 7:

   $$g=k(\cdot,x)\ (n=1,\ b_1=1,\ y_1=x):\quad\langle f,k(\cdot,x)\rangle_0=b_1f(y_1)=f(x)$$

   The first expression with the one-term representation of $k(\cdot,x)$ — the reproducing property.
8. 8
   Step 8:

   $$\langle k(\cdot,x),k(\cdot,x')\rangle_0=k(x',x)=k(x,x')$$

   Apply the reproducing property to $f=k(\cdot,x)$ evaluated at the point $x'$.

∎

1. 1
   Step 1:

   $$q(t)=\langle f+tg,f+tg\rangle=\langle f,f\rangle+2t\langle f,g\rangle+t^2\langle g,g\rangle\ \ge0\quad\forall t\in\mathbb R$$

   Expand by bilinearity and symmetry; $q(t)\ge0$ because the form is positive semidefinite.
2. 2
   Step 2:

   $$\langle g,g\rangle>0:\quad t=-\frac{\langle f,g\rangle}{\langle g,g\rangle}\ \Rightarrow\ q(t)=\langle f,f\rangle-\frac{\langle f,g\rangle^2}{\langle g,g\rangle}\ge0$$

   Evaluate $q$ at its minimiser: $\langle f,f\rangle-2\frac{\langle f,g\rangle^2}{\langle g,g\rangle}+\frac{\langle f,g\rangle^2}{\langle g,g\rangle}$.
3. 3
   Step 3:

   $$\Rightarrow\ \langle f,g\rangle^2\le\langle f,f\rangle\langle g,g\rangle$$

   Multiply by $\langle g,g\rangle>0$.
4. 4
   Step 4:

   $$\langle g,g\rangle=0:\quad q(t)=\langle f,f\rangle+2t\langle f,g\rangle\ge0\quad\forall t$$

   The quadratic term vanishes and $q$ is affine in $t$.
5. 5
   Step 5:

   $$\Rightarrow\ \langle f,g\rangle=0\ \Rightarrow\ \langle f,g\rangle^2=0\le\langle f,f\rangle\cdot0$$

   If $\langle f,g\rangle>0$, letting $t\to-\infty$ makes the affine function negative; if $\langle f,g\rangle<0$, letting $t\to+\infty$ does. Both contradict $q\ge0$, so $\langle f,g\rangle=0$ and the inequality holds with equality.

∎

1. 1
   Step 1:

   $$f(x)=\langle f,k(\cdot,x)\rangle_0$$

   Reproducing property on $\mathcal H_0$.
2. 2
   Step 2:

   $$\lvert f(x)\rvert^2=\lvert\langle f,k(\cdot,x)\rangle_0\rvert^2\le\langle f,f\rangle_0\,\langle k(\cdot,x),k(\cdot,x)\rangle_0$$

   Cauchy–Schwarz for the positive-semidefinite form $\langle\cdot,\cdot\rangle_0$ — we may not yet assume it is definite, which is why the lemma was proved without that assumption.
3. 3
   Step 3:

   $$=\langle f,f\rangle_0\,k(x,x)$$

   $\langle k(\cdot,x),k(\cdot,x)\rangle_0=k(x,x)$ by the previous lemma.
4. 4
   Step 4:

   $$\langle f,f\rangle_0=0\ \Rightarrow\ f(x)=0\ \ \forall x\in\mathcal X\ \Rightarrow\ f\equiv0$$

   The bound holds at every point, and a function vanishing everywhere is the zero element of $\mathcal H_0$.
5. 5
   Step 5:

   $$\langle f,f\rangle_0>0\ \text{for}\ f\ne0$$

   Together with symmetry, bilinearity and semidefiniteness, this is the definition of an inner product.

∎

1. 1
   Step 1:

   $$\lvert f_n(x)-f_m(x)\rvert=\lvert\langle f_n-f_m,k(\cdot,x)\rangle_0\rvert\le\lVert f_n-f_m\rVert_0\sqrt{k(x,x)}$$

   The pointwise bound applied to $f_n-f_m\in\mathcal H_0$. If $(f_n)$ is Cauchy in $\mathcal H_0$, then $(f_n(x))$ is a Cauchy sequence of real numbers for every fixed $x$.
2. 2
   Step 2:

   $$f(x):=\lim_{n\to\infty}f_n(x),\qquad\mathcal H_k:=\{f:\ f_n\to f\ \text{pointwise},\ (f_n)\ \text{Cauchy in}\ \mathcal H_0\}$$

   $\mathbb R$ is complete, so each pointwise limit exists. $\mathcal H_k$ contains $\mathcal H_0$ (constant sequences) and is a vector space, because sums and multiples of Cauchy sequences are Cauchy and limits are linear.
3. 3
   Step 3:

   $$(f_n)\ \text{Cauchy},\ f_n\to0\ \text{pointwise}\ \Rightarrow\ \lVert f_n\rVert_0\to0$$

   Key lemma. Cauchy sequences are bounded, $\lVert f_n\rVert_0\le B$. Given $\varepsilon>0$ pick $N$ with $\lVert f_n-f_N\rVert_0<\varepsilon$ for $n\ge N$ and write $f_N=\sum_{j=1}^rb_jk(\cdot,y_j)$. Then $\lVert f_n\rVert_0^2=\langle f_n,f_n-f_N\rangle_0+\langle f_n,f_N\rangle_0\le B\varepsilon+\big\lvert\sum_jb_jf_n(y_j)\big\rvert$, and the finite sum tends to $0$ as $n\to\infty$. Hence $\limsup_n\lVert f_n\rVert_0^2\le B\varepsilon$ for every $\varepsilon$.
4. 4
   Step 4:

   $$\langle f,g\rangle_{\mathcal H_k}:=\lim_{n\to\infty}\langle f_n,g_n\rangle_0$$

   The limit exists because $\lvert\langle f_n,g_n\rangle_0-\langle f_m,g_m\rangle_0\rvert\le\lVert f_n-f_m\rVert_0\lVert g_n\rVert_0+\lVert f_m\rVert_0\lVert g_n-g_m\rVert_0$. It does not depend on the sequences: if $(f'_n)$ also converges pointwise to $f$, then $f_n-f'_n$ is Cauchy with pointwise limit $0$, so $\lVert f_n-f'_n\rVert_0\to0$ by the key lemma, and the limits coincide.
5. 5
   Step 5:

   $$\langle f,f\rangle_{\mathcal H_k}=0\ \Rightarrow\ \lvert f(x)\rvert=\lim_n\lvert f_n(x)\rvert\le\lim_n\lVert f_n\rVert_0\sqrt{k(x,x)}=0$$

   Symmetry, bilinearity and semidefiniteness pass to the limit; definiteness follows from the pointwise bound, which also passes to the limit and gives $\lvert f(x)\rvert\le\lVert f\rVert_{\mathcal H_k}\sqrt{k(x,x)}$ on $\mathcal H_k$.
6. 6
   Step 6:

   $$\langle f,k(\cdot,x)\rangle_{\mathcal H_k}=\lim_n\langle f_n,k(\cdot,x)\rangle_0=\lim_nf_n(x)=f(x)$$

   Use the constant sequence for $k(\cdot,x)$ and the reproducing property on $\mathcal H_0$: the reproducing property holds on all of $\mathcal H_k$.
7. 7
   Step 7:

   $$\lVert f-f_n\rVert_{\mathcal H_k}=\lim_{m\to\infty}\lVert f_m-f_n\rVert_0\le\varepsilon\quad(n\ge N)$$

   So $f_n\to f$ in norm and $\mathcal H_0$ is dense. Completeness: the abstract completion of $\mathcal H_0$ consists of equivalence classes of Cauchy sequences; sending a class to its pointwise limit is well defined and injective by the key lemma and isometric by construction, so $\mathcal H_k$ is a copy of the (complete) completion.
8. 8
   Step 8:

   $$\mathcal G\ \text{another RKHS with kernel}\ k:\ \ g\perp k(\cdot,x)\ \forall x\ \Rightarrow\ g(x)=\langle g,k(\cdot,x)\rangle_{\mathcal G}=0$$

   Uniqueness. $\mathcal G\supseteq\mathcal H_0$ with the same inner product ($\langle k(\cdot,x),k(\cdot,y)\rangle_{\mathcal G}=k(x,y)$ by the reproducing property), and its orthogonal complement is $\{0\}$, so $\mathcal H_0$ is dense in $\mathcal G$. Norm convergence in $\mathcal G$ implies pointwise convergence (same bound), hence every $g\in\mathcal G$ is the pointwise limit of a Cauchy sequence in $\mathcal H_0$ with the same norm: $\mathcal G=\mathcal H_k$.

∎

1. 1
   Step 1:

   $$V=\operatorname{span}\{k(\cdot,x_1),\dots,k(\cdot,x_m)\},\qquad\mathcal H_k=V\oplus V^\perp$$

   $V$ is finite-dimensional and therefore closed, so the projection theorem gives a unique decomposition $f=f_\parallel+f_\perp$ with $f_\parallel\in V$ and $f_\perp\perp V$.
2. 2
   Step 2:

   $$f(x_i)=\langle f,k(\cdot,x_i)\rangle=\langle f_\parallel,k(\cdot,x_i)\rangle+\langle f_\perp,k(\cdot,x_i)\rangle$$

   Reproducing property and linearity of the inner product.
3. 3
   Step 3:

   $$\langle f_\perp,k(\cdot,x_i)\rangle=f_\perp(x_i)=0\ \Rightarrow\ f(x_i)=f_\parallel(x_i)$$

   $k(\cdot,x_i)\in V$ and $f_\perp\perp V$; by the reproducing property the inner product is the value $f_\perp(x_i)$. The perpendicular part is invisible at every training point.
4. 4
   Step 4:

   $$L\big(f(x_1),\dots,f(x_m)\big)=L\big(f_\parallel(x_1),\dots,f_\parallel(x_m)\big)$$

   The data term depends on $f$ only through its values at the training points.
5. 5
   Step 5:

   $$\lVert f\rVert^2=\lVert f_\parallel\rVert^2+2\langle f_\parallel,f_\perp\rangle+\lVert f_\perp\rVert^2=\lVert f_\parallel\rVert^2+\lVert f_\perp\rVert^2$$

   Expand the norm; the cross term vanishes because $f_\parallel\in V$ and $f_\perp\perp V$ (Pythagoras).
6. 6
   Step 6:

   $$f_\perp\ne0\ \Rightarrow\ \lVert f_\parallel\rVert<\lVert f\rVert\ \Rightarrow\ g(\lVert f_\parallel\rVert)<g(\lVert f\rVert)\ \Rightarrow\ J(f_\parallel)<J(f)$$

   $\lVert f_\perp\rVert>0$ makes the norm strictly smaller; $g$ is strictly increasing; the data terms are equal.
7. 7
   Step 7:

   $$f^\ast\ \text{minimiser}\ \Rightarrow\ f^\ast_\perp=0\ \Rightarrow\ f^\ast=f^\ast_\parallel=\sum_{i=1}^m\alpha_ik(\cdot,x_i)$$

   Otherwise $f^\ast_\parallel$ would have strictly smaller objective. For nondecreasing $g$ the same computation gives $J(f^\ast_\parallel)\le J(f^\ast)$, so $f^\ast_\parallel$ is a minimiser in $V$.

∎

1. 1
   Step 1:

   $$\sum_j\big(\sqrt{\mu_j}\varphi_j(x)\big)^2=\sum_j\mu_j\varphi_j(x)^2=k(x,x)<\infty$$

   Mercer's expansion at $x'=x$; the terms are nonnegative because $\mu_j\ge0$. So $\Phi(x)$ is square-summable.
2. 2
   Step 2:

   $$\langle\Phi(x),\Phi(x')\rangle_{\ell^2}=\sum_j\sqrt{\mu_j}\varphi_j(x)\sqrt{\mu_j}\varphi_j(x')=\sum_j\mu_j\varphi_j(x)\varphi_j(x')=k(x,x')$$

   Definition of the $\ell^2$ inner product (absolutely convergent by Cauchy–Schwarz in $\ell^2$) and Mercer's expansion.
3. 3
   Step 3:

   $$\int_{\mathcal X}k(x,x)\,d\mu(x)=\sum_j\mu_j\int_{\mathcal X}\varphi_j(x)^2\,d\mu(x)$$

   The series $\sum_j\mu_j\varphi_j(x)^2$ converges uniformly on $\mathcal X$ and $\mu$ is finite, so it may be integrated term by term.
4. 4
   Step 4:

   $$=\sum_j\mu_j\cdot1=\sum_j\mu_j$$

   Orthonormality in $L^2(\mathcal X,\mu)$: $\int\varphi_j^2\,d\mu=1$. The left side is finite because $k$ is continuous on the compact set $\mathcal X$.