Nystrom Approximation and Random Fourier Features

The kernel trick lets a model act as if it had transformed every data point into an infinite-dimensional space, just by computing similarity scores between pairs of points. The catch: with $n$ data points, that means an $n \times n$ table of similarities. At 10,000 rows this is a hundred million numbers; at a million rows it is unusable — the table alone would not fit in memory, let alone the matrix algebra needed to train on it. Nystrom approximation and random Fourier features are two different ways of getting almost all of the kernel's benefit while touching only a small fraction of that table.

The analogy: you don't need every pairwise distance to draw the map

Imagine mapping every city in a country by recording the driving distance between every pair — millions of measurements for thousands of cities. A cheaper approach: pick a modest number of "landmark" cities, measure everyone's distance to just those landmarks, and reconstruct approximate positions for every other city from that. You lose a little precision but the measurement cost collapses from millions of pairs to a few thousand. That is the spirit of both techniques below — replace "compare every point to every point" with "compare every point to a small, well-chosen reference set."

Two routes to the same destination

Nystrom approximation picks $m \ll n$ landmark points (often a random sample), computes the full similarity of every point to just those landmarks, and uses that thin $n \times m$ slice plus the small $m \times m$ landmark-to-landmark block to reconstruct an approximation of the full $n \times n$ kernel matrix. In symbols, if $K$ is the true kernel matrix, the approximation is

$$K \approx C \, W^{-1} \, C^{\top}$$

where $C$ is the $n \times m$ slice (every point against every landmark) and $W$ is the $m \times m$ landmark block. In plain English: rebuild the big similarity table from a thin strip of it, using the landmarks as a bridge between any two non-landmark points.

Random Fourier features takes a different route: instead of approximating the similarity matrix, it approximates the kernel function itself with a finite, explicit feature map. For kernels like the Gaussian (RBF) kernel, a classical result says the kernel can be written as an expectation over random sinusoids. Drawing $D$ random frequencies and building features $z(x) = \sqrt{2/D}\,[\cos(\omega_1^{\top}x+b_1), \ldots, \cos(\omega_D^{\top}x+b_D)]$ gives an ordinary $D$-dimensional vector such that $z(x)^{\top}z(x') \approx k(x, x')$ — a plain dot product that approximates the kernel value. In plain English: instead of an implicit infinite-dimensional space, build a modest, explicit set of features and use a normal linear model on them.

Worked example 1: Nystrom on 6 points

Suppose $n=6$ points and we pick $m=2$ landmarks. The full kernel matrix would need $6 \times 6 = 36$ entries. Nystrom only computes the $6 \times 2 = 12$ entries of $C$ (every point to each landmark) plus the $2 \times 2 = 4$ entries of $W$ — 16 numbers total, computed once, instead of 36, and the saving grows quadratically as $n$ grows while $m$ stays fixed. With $n = 10{,}000$ and $m = 200$, Nystrom computes roughly $2$ million entries instead of $100$ million — a 50x reduction.

Worked example 2: random Fourier features on one point

Take $x = 1.5$ (one feature), and draw $D=4$ random frequencies $\omega = [0.8, -1.2, 2.0, 0.3]$ and offsets $b = [0.1, 0.9, 0.4, 1.1]$. Compute $\cos(\omega_i x + b_i)$ for each: $\cos(1.3)=0.267$, $\cos(-0.9)=0.622$, $\cos(3.4)=-0.967$, $\cos(1.55)=0.021$. Scale by $\sqrt{2/4}=0.707$: the feature vector is $z(x) \approx [0.189, 0.440, -0.684, 0.015]$. Every point in the dataset gets its own such vector using the same random frequencies, and a plain linear model (or dot product) on these vectors approximates what the full kernel would have given — no $n \times n$ matrix ever built.

What this means in practice

These approximations are what make kernel SVMs and Gaussian processes usable on datasets with tens or hundreds of thousands of rows, where the exact kernel matrix would never fit in memory. More landmarks or more random features buys accuracy at the cost of speed, so $m$ or $D$ is a knob a practitioner tunes directly against the compute budget.