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

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.