I came across this beautiful idea of Random Fourier Features by Rahimi and Recht while working on optimising my GP model using Predictive Entropy Search.
I understand the overall idea of approximating a NxN kernel matrix using finite random features. The kernel's Fourier dual needs to be properly scaled such that it represents a normalised density function. However, I am not clear on what does the scaling mean and how does it relate to the kernel that is being approximated. Explicitly, how does the scaling factor multiplied to matrix W
relate to the exact kernel's hyperparameters?
The scaling factor is treated differently in implementations.
For example, in the source code by Hernández-Lobato, this W
is scaled by the lengthscale l
:
l = 1 ./ gp_rec.cf{ 1 }.lengthScale.^2;
% We draw the random features
W = randn(nFeatures, d) .* repmat(sqrt(l(i,:)), nFeatures, 1);
b = 2 * pi * rand(nFeatures, 1);
There is also a great tutorial on RFF written by Gregory Gundersen, in his implementation, the W
is scaled by sigma
instead of lengthscale l
:
Z = norm * np.sqrt(2) * np.cos(self.sigma * W @ X.T + B)
I follow the idea that
$2/D * \cos(\mathbf{\omega}^T \mathbf{x}+\mathbf{b}) * \cos(\mathbf{\omega}^T \mathbf{x'}+\mathbf{b}) = \exp(i\mathbf{\omega}^T(\mathbf{x}-\mathbf{x}'))$
A Gaussian kernel has the form $\sigma^2\exp(- \frac{\tau^2}{2l^2})$, in rff we work with the form $\exp(-i w \tau)$ and its z-map has the form $c\cos(wx+b)$.
It is not clear how $\sigma$ and $l$ are related to $w$ or $aw$. Because $w$ is inside $\cos$, and such scaling $\cos(aw)$ is not linear, for example $\cos(2x) \neq 2\cos(x)$ in general. Similarly, $\cos(2x)*cos(2x) \neq 1/4\cos(x)*cos(x)$, while the approximation is $c \cdot cos(wx+b)*cos(wx+b) = k(\cdot)$ = $\sigma^2\exp(- \frac{\tau^2}{2l^2})$...
and my questions are:
what does it mean if we scale the
z
by means of scaling theW
by a scalara
? i.e. $z_{\omega}(\mathbf{x}) = \sqrt{2}\cos(a \mathbf{\omega}^T \mathbf{x}+\mathbf{b}) $.how does $\exp(i\mathbf{\omega}^T(\mathbf{x}-\mathbf{x}'))$ link to the exact kernel and its hyperparameters such as
sigma
(variance) andl
(lengthscale)? In other words, how does the scaling factora
relate to the set of hyperparamters $\sigma$ and $l$?
Or do I in fact misunderstand the intention here?
Thank you.