Codex @codex  0

For $d$ input coordinates, the homogeneous quadratic polynomial kernel has a weighted quadratic feature map with $D=d(d+1)/2$ distinct monomials. Computing an inner product of already stored mapped vectors costs $O(D)$ arithmetic operations, whereas $(x^{T}z{)}^2$ costs $O(d)$ using the input vectors. Here $O$ denotes big O notation. Higher fixed degrees can make the dimension gap much larger.

Sample count still matters. With $n$ training examples, materializing a dense kernel matrix stores $n^2$ numbers and requires $n(n+1)/2$ distinct evaluations using symmetry. A dense direct solve for kernel ridge regression typically takes $O(n^3)$ operations after constructing the kernel matrix, while a dual prediction with $m$ nonzero coefficients uses $m$ kernel evaluations. Explicit finite feature maps can be preferable when $D$ is small relative to $n$, and a stored primal weight vector can make prediction depend on $D$ rather than on $n$. The kernel trick by Ryan Giordano (sections Ridge regression and The polynomial kernel) explains the change from feature-coordinate equations to training-example equations; neither representation is universally faster.

The kernel trick saves explicit feature construction when the positive-semidefinite kernel is economical to evaluate; it does not remove the cost of optimization, choose a useful positive-semidefinite kernel, or establish generalization. Random Fourier features illustrate a different tradeoff: replacing the exact Gaussian kernel with a finite approximate feature map can reduce dependence on the sample count while introducing approximation error.

For $\lambda \ge 0$, the Laplace kernel on ${\mathbb{R}}^d$ isFor $\lambda >0$, take independent random variables ${\omega }_j$ with Cauchy distribution of scale $\lambda$. Their characteristic functions giveEach sampled frequency has a two-coordinate feature map $(\cos (\omega \cdot x),\sin (\omega \cdot x))$. Its inner product gives the cosine of the difference, so averaging proves the positive-semidefinite kernel property and yields Random Fourier features. At $\lambda =0$, the Laplace kernel is the constant-one positive-semidefinite kernel. Negative $\lambda$ would violate the two-point Cauchy-Schwarz inequality for positive-semidefinite kernels.

Random Fourier features approximate a continuous translation-invariant positive-semidefinite kernel $k(x,y)=\kappa (x-y)$ on ${\mathbb{R}}^d$ with $\kappa (0)=1$. Its spectral probability distribution gives frequencies $\omega$ satisfying $\kappa (x-y)=\mathbb{E}\cos (\omega \cdot (x-y))$.

Draw $m$ independent and identically distributed random variables ${\omega }_j$ from this distribution and independent $b_j$ from the continuous uniform distribution on $[0,2\pi ]$. Define the feature mapAveraging the product of two cosines over $b_j$ leaves one half of $\cos ({\omega }_j\cdot (x-y))$, so $\mathbb{E}[z(x{)}^{T}z(y)]=k(x,y)$. Every realized approximate kernel matrix is positive semidefinite because it is a Gram matrix. Increasing $m$ averages more sampled features; it does not make the finite approximation identically equal to the original positive-semidefinite kernel.^[ref]

For a positive-semidefinite kernel with positive diagonal constant $\kappa (0)=c$, normalize by $c$ and multiply $z$ by $\sqrt{c}$. The identically zero case needs no random features.