kernel trick

Let $K$ be a Mercer kernel such that ${\sup }_{x,y}K(x,y)<\infty$. Then there exists an orthonormal basis for $L_2(\mathcal{X})$, $\{{\psi }_i\}$ and eigenvalues ${\lambda }_1\ge {\lambda }_2\ge \dots$ such that

$$K(x,y)=\sum _i{\lambda }_i{\psi }_i(x){\psi }_i(y).$$

The Kernel is thus “ordering” the basis, in the sense that it assigns higher weight to ${\psi }_1$ than ${\psi }_2$ and so on. If we gather the first $r$ eigenfunctions, then we can think of this as dimensionality reduction.

However, we can do something better by appealing to the kernel trick. For each $x\in \text{cX}$, define the map

$$\Phi (x)=(\sqrt{{\lambda }_i}{\psi }_i(x){)}_{i=1}^{\infty },$$

which is an infinite dimensional feature map for $x$. Then,

$$⟨\Phi (x),\Phi (y)⟩=\sum _i{\lambda }_i{\psi }_i(x){\psi }_i(y)=K(x,y).$$

That is, the Kernel embeds the information about these infinite dimensional sequences. Thus, if we can structure our computation to only require computations of $K(x,y)$, then we can essentially use the entire feature maps (sans dimensionality reduction), which having to represent them explicitly. This is known as the Kernel trick.