= Solution
Let $V_1,\ldots,V_d$ be independent standard <Cauchy random variables>. Their <characteristic functions> and independence give
$$
\mathbb E e^{i\lambda V^T(x-y)}
=\prod_{j=1}^d e^{-\lambda|x_j-y_j|}
=e^{-\lambda\|x-y\|_1}.
$$
Taking real parts yields
$$
e^{-\lambda\|x-y\|_1}
=\mathbb E\!\left[
\cos(\lambda V^Tx)\cos(\lambda V^Ty)
+\sin(\lambda V^Tx)\sin(\lambda V^Ty)
\right].
$$
For 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>.
Back to article page
