Random feature map

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.