Random fourier features and Bochner's Theorem The paper, Random Fourier Features for Large-Scale Kernel Machines by Ali Rahimi and Ben Recht
,
makes use of Bochner's theorem which says that the Fourier transform $p(w) $ of shift-invariant kernels $k(x,y)$ is a probability distribution (in layman terms).
And therefore the kernel can be expressed as the inverse-Fourier transform of $p(w)$
$\begin{eqnarray}
k(x,y) &=& \int_{R^d} p(w) e^{j w^T (x-y} dw \\
       &=& \mathbb{E}_w[\psi_w(x) \psi_w(y)^*] 
\end{eqnarray}$
where,
$\psi_w(x) = e^{j w^T x}$, and 
$\psi_w(y)^* = e^{-j w^T y }$ is the complex conjugate
The statement the paper makes at this point is that since, $p(w)$ is real and even, the complex exponentials can be replaced with cosines, to give,
$k(x,y) = \mathbb{E}_w[z_w(x) z_w(y)]$
where $z_w(x) = \sqrt{2} cos(w^T x)$
I do not understand where this comes from.
From what I understand about Fourier Transforms, $p(w)$ is real and even for real and even $k(x,y)$.
Therefore, it should actually be,
$\begin{eqnarray}
k(x, y) &=& \mathbb{E}_w[cos(w^T (x-y)] \\
        &=& \mathbb{E}_w[cos(w^T x) cos(w^T y) + sin(w^T x) sin(w^T y)] \\
        &=& \mathbb{E}_w[z_w(x)^T z_w(y)] 
\end{eqnarray}$
where $z_w(x) = [cos(w^T x), sin(w^T x)]^T$
What am I missing ?
 A: The direct Fourier interpretation would indeed be $\cos(w^T x), \sin(w^T x)]$, as you've listed.
You've actually slightly misunderstood the paper's proposal for only-cosine features, though; they use $\sqrt{2} \cos(w^T x + b)$, with $b \sim \mathrm{Uniform}[0, 2 \pi]$. Then
\begin{align}
\sqrt{2}\cos(w^T x + b) \sqrt{2}\cos(w^T y + b)
&= \cos((w^T x + b) - (w^T y + b)) + \cos((w^T x + b) + (w^T y + b))
\\&= \cos(w^T (x - y)) + \cos(w^T (x + y) + 2 b)
,\end{align}
and we have
\begin{align}
\mathbb E_{w,b} 2 \cos(w^T x + b) \cos(w^T y + b)
&= \mathbb E_{w,b}\left[ \cos(w^T (x - y)) + \cos(w^T (x + y) + 2 b) \right]
\\&= \mathbb E_w \left[ \cos(w^T (x - y)) \right] + \mathbb E_{w,b}\left[ \cos(w^T (x + y) + 2 b) ] \right]
\\&= k(x, y) + 0
.\end{align}
The random offset $b$ makes the second term zero.
This form is somewhat more convenient, in that you have one feature per dimension. But it turns out that actually, given a constant number of dimensions, you get slightly better kernel approximations by using pairs of features without the additive noise than you do by using single dimensions with the additive noise – see chapter 3 of my thesis, which fixes a few slight errors in our earlier paper.
