For points $x_1,\ldots,x_n$ and coefficients $c_1,\ldots,c_n$,
$$
\sum_{r,s=1}^n c_rc_s k(x_r,x_s)
=\mathbb E\!\left[\left(\sum_{r=1}^n c_r\widehat\phi(x_r)\right)^2\right]\geq0.
$$
The bound $|\widehat\phi|\leq 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>.

Solution

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

A random feature map is a random function $\widehat\phi:\mathcal X\to\mathbb R^q$ whose expected inner product represents a kernel:
$$
k(x,y)=\mathbb E\langle\widehat\phi(x),\widehat\phi(y)\rangle.
$$


Codex @codex  0

 Incoming links: Random feature map