Nyström approximation and random Fourier features: Definition & Examples

Nyström approximation and random Fourier features construct small, explicit feature vectors whose inner products approximate a chosen kernel. They make nonlinear kernel methods usable with linear-model solvers. For a quant fitting execution costs across many orders, the practical attraction is replacing a large table of pairwise order similarities with a manageable table of transformed inputs.

Write the training Gram matrix as $K_{ij}=k(x_i,x_j)$ . A feature matrix $Z$ has one row $z(x_i)^\top$ per observation and aims for

K\approx ZZ^\top,\qquad k(x,x')\approx z(x)^\top z(x').

If there are

n

observations and

r

features, storing

Z

takes

nr

entries instead of

n^2

for a dense

K

. This saves memory when

r\ll n

; it does not promise that the resulting predictions match an exact fit. scikit-learn, Kernel approximation

Nyström: keep directions represented by landmarks

Choose

m

training inputs as landmarks, indexed by

L

. For a real positive semidefinite kernel, define

C=K_{:,L},\qquad W=K_{L,L},\qquad \widetilde K=CW^{\dagger}C^\top.

Here $C$ is $n\times m$ , $W$ is $m\times m$ , and $W^{\dagger}$ is the Moore–Penrose pseudoinverse. It equals the inverse when $W$ is nonsingular. Duplicate or dependent landmark features can make $W$ singular; an ordinary inverse then does not exist.

If $W=U_+\Lambda_+U_+^\top$ retains all its strictly positive eigenvalues, an explicit factor is

Z=CU_+\Lambda_+^{-1/2},\qquad z(x)^\top=k(x,L)U_+\Lambda_+^{-1/2}.

The second expression transforms a new input using the same landmarks and normalization. In feature-space terms, this projects onto the span of the landmark feature vectors. It is data dependent even when the landmarks are sampled randomly. The classical construction and its projection interpretation are developed in Rasmussen and Williams, §8.1, following Williams and Seeger (2001).

Truncation and regularization change the approximation. Dropping small positive eigenvalues gives a truncated pseudoinverse. Replacing

W^{\dagger}

(W+\eta I)^{-1}

, with

\eta>0

, gives a regularized variant. Neither is the exact all-positive-eigenvalue projection above. State the threshold or

\eta

rather than silently treating all three constructions as identical.

A landmark can reproduce similarities and still lose length

Consider a fictional, dimensionless example:

K=\begin{pmatrix}1&0.5\\0.5&1\end{pmatrix}.

This matrix is positive definite: its eigenvalues are $1.5$ and $0.5$ . Select the first observation as the sole landmark. Then

C=\begin{pmatrix}1\\0.5\end{pmatrix},\qquad W=(1),\qquad \widetilde K=CC^\top= \begin{pmatrix}1&0.5\\0.5&0.25\end{pmatrix}.

The first row and column are exact, but the second diagonal falls from $1$ to $0.25$ . Its error is $0.75$ . The approximation has rank one, with eigenvalues $1.25$ and $0$ ; the original has rank two.

The geometry explains the missing amount independently. Choose exact feature vectors

\phi_1=(1,0)^\top,\qquad \phi_2=(1/2,\sqrt3/2)^\top.

Their inner products give $K$ . Projection onto the first landmark removes the second coordinate of $\phi_2$ . The lost squared length is $(\sqrt3/2)^2=3/4$ . Thus the residual is

K-\widetilde K=\begin{pmatrix}0&0\\0&0.75\end{pmatrix}.

Exact unitless feature vectors are phi1 equal to (1,0) and phi2 equal to (0.5, square root of 3 divided by 2). Projecting onto the first landmark leaves phi2 with squared length 0.25 instead of 1. The omitted squared perpendicular length is 0.75; the approximate Gram matrix has rank 1.

Original deterministic geometry for the two-observation example. The first landmark retains the horizontal feature direction and discards the vertical direction. Matrix entries are dimensionless inner products.

This is a controlled loss of feature directions, not an identity for the full kernel. In particular, an exact landmark column does not establish a good approximation for the rest of the sample. Dividing the approximate rows by their norms would also change the approximating kernel.

Random Fourier features: sample the kernel's spectrum

Random Fourier features (RFF) use a different construction. For a continuous, real, stationary PSD kernel on $\mathbb R^d$ , write $k(x,x')=\kappa(x-x')$ . With $\kappa(0)=1$ , Bochner's theorem provides a spectral probability measure $p$ satisfying

\kappa(\delta)=\mathbb E_{\omega\sim p}[\cos(\omega^\top\delta)].

Draw $r$ independent frequencies $\omega_j\sim p$ and independent phases $b_j\sim\operatorname{Uniform}[0,2\pi]$ . One real-valued map is

z_j(x)=\sqrt{\frac2r}\cos(\omega_j^\top x+b_j),\qquad \mathbb E[z(x)^\top z(x')]=k(x,x').

For the Gaussian kernel

k(x,x')=\exp(-\lVert x-x'\rVert^2/(2\ell^2))

, draw

\omega_j\sim\mathcal N(0,\ell^{-2}I_d)

. An overall kernel amplitude

a>0

requires multiplying the normalized map by

\sqrt a

. This is Fourier sampling, not landmark selection. Rahimi and Recht, §3

The equality holds in expectation over draws. A finite realized map has error; increasing the feature count need not improve every pair monotonically. Its Gram matrix is PSD because it is $ZZ^\top$ , though individual estimated similarities can be negative. Standard RFF requires stationarity; Nyström can also approximate nonstationary PSD kernels. The paired sine/cosine map in the paper's Algorithm 1 is another valid construction, with different feature-count bookkeeping.

Keep the approximation inside the research split

Choice	Nyström	Standard RFF
What fixes the coordinates?	Landmark inputs and their kernel matrix	Kernel spectrum and sampled frequencies/phases
Dependence on observed input values	Direct	None for a fixed kernel and input dimension
Main approximation budget	Landmark count and retained eigenvalues	Number of sampled features
What must travel with the fitted model?	Landmarks, kernel settings and normalization	Frequencies, phases and kernel settings

Both also need any fitted input preprocessing. In a chronological experiment, fit scaling and select Nyström landmarks using the training window only. Apply those frozen transformations to validation and test observations. Tune bandwidth, feature count and any eigenthreshold or regularization inside the training/validation procedure; selecting them from final test results leaks information. scikit-learn, §§12.1–12.2.1

Fix and record random seeds for reproducibility, and examine sensitivity across seeds without choosing the best seed on the final test set. RFF frequencies are data independent conditional on the kernel, but a bandwidth or scaler estimated using future inputs is still a data-dependent choice. Re-sampling frequencies at prediction time changes the coordinates under an already fitted model.

A linear ridge regression on

Z

is kernel ridge regression for the approximating kernel

\widetilde k(x,x')=z(x)^\top z(x')

, under matched loss, penalty and intercept conventions. Compare its held-out loss and operational cost with an exact-kernel benchmark when feasible; kernel approximation error alone is not a trading-performance measure.

For the underlying feature-map intuition, The Kernel Trick: Feature Maps and Properties of Kernels develops explicit inner products and the Gaussian kernel. The full lesson requires membership; its preview is public.

Sources

Rasmussen and Williams, Gaussian Processes for Machine Learning (2006), §8.1, especially equations 8.4–8.10 and the projection interpretation of Williams and Seeger's (2001) construction.
Rahimi and Recht, Random Features for Large-Scale Kernel Machines (2007), §3 and Algorithm 1.
scikit-learn User Guide, Kernel approximation, §§8.7.1–8.7.2; current documentation accessed 1 November 2026.
scikit-learn User Guide, Common pitfalls and recommended practices, §§12.1–12.2.1; current documentation accessed 1 November 2026.

Nyström: keep directions represented by landmarks

A landmark can reproduce similarities and still lose length

Random Fourier features: sample the kernel's spectrum

Keep the approximation inside the research split

Sources

Related terms

Kernel method and kernel trick

Kernel ridge regression

Mercer's theorem and valid kernels