From the representer theorem and Mercer's theorem,
\begin{align*}
f(x) &= \sum_{n=1}^N \alpha_n k(x_n, x) \\
&= \sum_{n=1}^N \alpha_n \langle \varphi(x_n) , \varphi(x) \rangle_{\mathcal{H}} \\
&= \sum_{n=1}^N \alpha_n z(x_n)^\top z(x) \\
&\equiv \beta^\top z(x)
\end{align*}
where \varphi : x \rightarrow k(\cdot, x) is a reproducing map, \mathcal{H} is a reproducing kernel Hilbert space, and z : \mathbb{R}^D \rightarrow \mathbb{R}^M is an approximation of \varphi.
In this article, I will attempt to express z(x) as random features.
From Bochner's theorem and let p(\omega) be a non-negative measure,
\begin{align*}
k(x, y) &= k(x - y) \\
&= \int p(\omega) \exp \left(i \omega^\top (x - y) \right) d \omega \\
&= \int p(\omega)
\left\{
\cos \left( \omega^\top (x - y) \right)
+ \cancel{ i \sin \left(\omega^\top (x - y) \right)}
\right\} d \omega \\
&= E_{\omega} \left[ \cos \left( \omega^\top (x - y) \right) \right] \\
&= E_{\omega} \left[ \cos \left( \omega^\top x - \omega^\top y \right) \right] \\
&= E_{\omega} \left[ \cos(\omega^\top x) \cos(\omega^\top y) + \sin(\omega^\top x)\sin(\omega^\top y) \right] \\
&\approx
\frac{1}{M} \sum_{m=1}^M
\cos(\omega_m^\top x) \cos(\omega_m^\top y) + \sin(\omega_m^\top x)\sin(\omega_m^\top y) \\
&= \begin{pmatrix}
\frac{1}{\sqrt{M}} \cos(\omega_1^\top x)\\
\vdots \\
\frac{1}{\sqrt{M}} \cos(\omega_M^\top x)\\
\frac{1}{\sqrt{M}} \sin(\omega_1^\top x)\\
\vdots \\
\frac{1}{\sqrt{M}} \sin(\omega_M^\top x)\\
\end{pmatrix}^\top
\begin{pmatrix}
\frac{1}{\sqrt{M}} \cos(\omega_1^\top y)\\
\vdots \\
\frac{1}{\sqrt{M}} \cos(\omega_M^\top y)\\
\frac{1}{\sqrt{M}} \sin(\omega_1^\top y)\\
\vdots \\
\frac{1}{\sqrt{M}} \sin(\omega_M^\top y)\\
\end{pmatrix} \\
&\equiv z(x)^\top z(y) ,\quad z(x),z(y) \in \R^{2 M}
\end{align*}
Furthermore, it is possible to obtain another lower-dimensional form of z(x).
Let b \sim \mathrm{Unif}(b|0, 2\pi), we have:
\begin{align*}
k(x, y) &= E_{\omega} \left[ \cos \left( \omega^\top (x - y) \right) \right] \\
&\overset{\natural}{=} E_{\omega, b} [ 2 \cos(\omega^\top x + b) \cos(\omega^\top y + b) ] \\
&\approx
\frac{2}{M} \sum_{m=1}^M \cos(\omega_m^\top x + b_m) \cos(\omega_m^\top y + b_m) \\
&= \begin{pmatrix}
\sqrt{\frac{2}{M}} \cos(\omega_1^\top x + b_1) \\
\vdots \\
\sqrt{\frac{2}{M}} \cos(\omega_M^\top x + b_M) \\
\end{pmatrix}^\top
\begin{pmatrix}
\sqrt{\frac{2}{M}} \cos(\omega_1^\top y + b_1) \\
\vdots \\
\sqrt{\frac{2}{M}} \cos(\omega_M^\top y + b_M) \\
\end{pmatrix} \\
&\equiv z(x)^\top z(y) ,\quad z(x), z(y) \in \R^M
\end{align*}
Proof of \overset{\natural}= .
From the trigonometric product to sum formula, 2 \cos(\alpha) \cos(\beta) = \cos(\alpha + \beta) + \cos(\alpha - \beta), let \alpha = \omega^\top x + b, \beta = \omega^\top y + b.
\begin{align*}
E_{\omega,b} [ 2 \cos(\omega^\top x + b) \cos(\omega^\top y + b) ]
&= E_{\omega, b}[ \cos(\omega^\top (x + y) + 2 b) + \cos(\omega^\top (x - y)) ] \\
&= E_{\omega, b}[ \cos(\omega^\top (x + y) + 2 b)] + E_{\omega,b}[ \cos(\omega^\top (x - y)) ] \\
&= E_\omega[ E_b [\cos(\omega^\top (x + y) + 2 b) | \omega] ] + E_{\omega,b}[ \cos(\omega^\top (x - y)) ] \\
&\overset{\flat}= E_\omega[0 ] + E_{\omega,b}[ \cos(\omega^\top (x - y)) ] \\
&= E_\omega[ \cos(\omega^\top (x - y)) ] \\
\end{align*}
Proof of \overset{\flat}= .
\begin{align*}
E_b [\cos(\omega^\top (x + y) + 2 b) | \omega] &= \int_{0}^{2\pi} \mathrm{Unif}(b|0, 2\pi) \cos(\omega^\top (x + y) + 2 b) db \\
&= \int_{0}^{2\pi} \frac{1}{2\pi - 0} \cos(\omega^\top (x + y) + 2 b) db \\
&= \frac{1}{2 \pi} \int_{0}^{2\pi} \left\{ \frac{1}{2} \sin(\omega^\top (x + y) + 2 b) \right\}' db \\
&= \frac{1}{2 \pi} \left[ \frac{1}{2} \sin(\omega^\top (x + y) + 2 b) \right]_0^{2\pi} \\
&= \frac{1}{2 \pi} \left\{ \frac{1}{2} \sin(\omega^\top (x + y) + 4 \pi) - \frac{1}{2} \sin(\omega^\top (x + y) ) \right\} \\
&= \frac{1}{2 \pi} \left\{ \frac{1}{2} \sin(\omega^\top (x + y)) - \frac{1}{2} \sin(\omega^\top (x + y) ) \right\} \\
&= 0
\end{align*}
Reference
Discussion