Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 205 / 1

A positive-semidefinite kernel on a nonempty set $\mathcal{X}$ is a symmetric function $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ such that, for every $n\ge 1$, every $x_1,\dots ,x_n\in \mathcal{X}$, and every $c_1,\dots ,c_n\in \mathbb{R}$,Equivalently, every finite kernel matrix $(k(x_r,x_s){)}_{r,s}$ is a positive semidefinite matrix.

The Gaussian kernel with bandwidth ${\sigma }^2>0$ is

Every $2\times 2$ principal submatrix of a kernel matrix is positive semidefinite, soThe Cauchy-Schwarz inequality for integrals therefore givesThus every entry of $k(x,y)=\int k_{\tau }(x,y)d\tau$ is well defined. For any finite coefficients $c_r$ and points $x_r$, linearity of the integral givesbecause the integrand is nonnegative. Hence $k$ is a positive-semidefinite kernel. This proves the integral closure of positive-semidefinite kernels.

The Gamma integral $u^{-1/2}={\pi }^{-1/2}{\int }_0^{\infty }{t}^{-1/2}{e}^{-ut}dt$ givesFor each $t>0$, the last factor is a Gaussian kernel, and the remaining weight is nonnegative. The diagonal integral equals ${\alpha }^{-1/2}<\infty$, so part ii shows that the displayed function is a positive-semidefinite kernel.

For points $x_1,\dots ,x_n$ and coefficients $c_1,\dots ,c_n$,The bound $|\hat{\varphi }|\le M$ ensures that this expected value is finite. Symmetry is immediate, so an expected outer product of a random feature map always defines a positive-semidefinite kernel.

Let $V_1,\dots ,V_d$ be independent standard Cauchy random variables. Their characteristic functions and independence giveTaking real parts yieldsFor each realization of $V$, both products are rank-one positive-semidefinite kernels. Their sum and then their expectation remain positive semidefinite by the closure property of positive-semidefinite kernels. This is a Random Fourier feature representation of the Laplace kernel.