Feature map

A feature map sends $x$ to a vector $\varphi (x)$ in a vector space with an inner product so that $k(x,y)=⟨\varphi (x),\varphi (y)⟩$.

On the finite formal span of symbols $e_x$, define $B(e_x,e_y)=k(x,y)$ and extend bilinearly. For a positive-semidefinite kernel, the null vectors of this positive semidefinite bilinear form form its radical of a bilinear form. Quotienting by that linear subspace gives an inner product space and feature map $x\mapsto [e_x]$ with $⟨[e_x],[e_y]⟩=k(x,y)$. This construction works for degenerate and zero kernels.

A random feature map is a random function $\hat{\varphi }:\mathcal{X}\to {\mathbb{R}}^q$ whose expected inner product represents a kernel:

Random Fourier features represent a translation-invariant positive-semidefinite kernel by sampling frequencies from its spectral distribution and using sine and cosine features. They replace an implicit infinite-dimensional feature map by a finite random approximation.