randomfeatureapproximaties

Random feature approximations are techniques for converting kernel methods into scalable, explicit feature maps. The goal is to approximate a kernel function k(x, y) by a finite-dimensional inner product z(x) · z(y), where z(x) is a fixed feature map. This allows training linear models on the mapped features instead of using expensive kernel computations, enabling large-scale applications.

A prominent approach is the Random Fourier Features (RFF) method, introduced to approximate shift-invariant kernels such as the Gaussian (RBF) kernel. If k(x, y) = k(x − y) and its Fourier transform p(w) is known, one samples D random vectors w1, ..., wD from p(w) and D random phases b1, ..., bD from a uniform distribution on [0, 2π). The feature map is z(x) with components zj(x) = sqrt(2/D) cos(wj^T x + bj). Then k(x, y) is approximated by z(x)·z(y). This reduces kernel learning to linear learning in the D-dimensional feature space, with computational cost that scales linearly in the number of examples and the feature dimension.

Other random feature schemes include random binning features, which partition the input space with random grids to form binary features, and the Nyström method, which approximates the kernel matrix via a low-rank decomposition using a subset of data.

The quality of the approximation improves as D increases, with theoretical guarantees under suitable conditions. Practical use involves choosing the kernel type, sampling distribution, and the number of random features to balance accuracy and computational efficiency. Random feature approximations are widely used in large-scale kernel ridge regression, support vector machines, and related nonlinear learning tasks.