Domains of Integration -- the kernel trick and box-muller

Question

I wonder if there is any deeper connection between two "tricks" from applied math, the kernel trick and the box-muller algorithm for generating draws from a random normal.

The kernel trick, used in support vector machines, is to project from feature space to some inner product space. Hopefully the (images of the) data are linearly separable within the larger inner product space.

The Box-Muller algorithm takes $I = \int e^{-x^2}$ and instead cleverly considers the problem of finding $I^2$ via $\int e^{-x^2} dx \ \cdot \; \int e^{-y^2} dy$ which can be transformed using the pythagorean identity $\sin^2 \phi + \cos^2 \phi = 1$ into $\int r \cdot e^{-r^2} dr$ which is integrable.

Both "tricks" involve projecting a simple problem into a seemingly more complicated space, wherein the previously hard problem becomes easy. And then the answer is inverse-mapped back to the original domain, $f^{-1} \circ g \circ f$. But is there a connection other than this very broad observation?

Answer 1

I think there may be a distant link, but I might be understanding this wrongly!!

There were two nice papers by Ali Rahimi and Ben Recht: Random Features for Large-Scale Kernel Machines (2007) and Uniform Approximation of Functions with Random Bases by (2008) which use techniques from probability on Banach Spaces to random nonlinearities, and provide $L_\infty$ and $L_2$ error bounds for approximating functions in Reproducing Kernel Hilbert Spaces. The show links between these and kernel functions. In section V (examples) of the 08 paper they give the following:

Random Fourier Bases: Sinusoidal nonlinearities of the form $\phi (x, \theta ) = \cos(\omega' x + b)$ with $\theta = (w, b)$ and $\omega = \mathbb{R}^d \times [−\pi, \pi]$ are 1-Lipschitz and satisfy the assumptions of Theorem 3.2. These features project their input onto a randomly chosen line, and then pass the resulting scalar through a sinusoid.

Hence this seems to use a similar trick of transforming from a Gaussian distribution in the input space to a uniform distribution in the projected space. Possibly a bit tenuous though ...