Scaling Kernels with Orthogonal and Structured Random Features

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 259 papers95 conceptsfrozen 2026-10-04

Kernel methods are the "heavy hitters" of non-linear modeling, but they suffer from a notorious scalability bottleneck: standard implementations scale quadratically with the number of data points. To solve this, researchers often use Random Fourier Features (RFF) to map data into a low-dimensional space where linear methods can approximate the kernel.

However, the traditional way of building these maps—using independent and identically distributed (i.i.d.) Gaussian projections—is surprisingly inefficient. A growing body of research shows that by introducing structure and negative correlation into these random projections, we can drastically reduce approximation error and enable linear-time versions of complex models like Transformers.

The Problem with Independent Sampling

In a standard RFF setup, we sample random vectors from a distribution (like a Gaussian) to serve as the "basis" for our feature map. Because these vectors are sampled independently, they often "clump" together by chance. When two random vectors point in nearly the same direction, they provide redundant information about the kernel's geometry. This redundancy manifests as high variance in the kernel estimator, requiring a large number of features to achieve decent accuracy.

The core insight of this research direction is that we don't actually want our random features to be independent; we want them to be spread out.

The Orthogonal Breakthrough

Felix X. Yu, Krzysztof Choromanski, and their colleagues introduced a simple but powerful fix in Orthogonal Random Features. Instead of sampling independent Gaussian vectors, they proposed enforcing orthogonality between the rows of the projection matrix.

By ensuring every projection vector is perpendicular to every other vector, the estimator avoids redundancy. This "orthogonal coupling" introduces a negative correlation between the sampled features that significantly reduces the variance of the kernel approximation without introducing any bias. As shown in Initialization matters: Orthogonal Predictive State Recurrent Neural Networks, this structured approach fundamentally improves the spectral properties of the resulting matrices, leading to tighter error bounds and more stable model initialization.

Linearizing the Transformer with FAVOR

This variance reduction isn't just a theoretical curiosity; it is the engine behind the Performer architecture. Standard Transformers scale quadratically ($O(L^2)$) with sequence length because of the attention matrix. In Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers, researchers used a mechanism called FAVOR (Fast Attention Via positive Orthogonal Random features) to approximate the softmax kernel.

By using orthogonal random features, the Performer can decompose the attention matrix into a product of two smaller matrices, reducing the complexity to linear ($O(L)$). Later, Valerii Likhosherstov and Krzysztof Marcin Choromanski pushed this further with FAVOR#, introducing Dense-Exponential Random Features (DERFs). By replacing scalar parameters with optimized matrix parameters, they reduced variance by up to $e^{10}$, allowing linear-time attention to nearly match the performance of exact quadratic attention.

Beyond Orthogonality: Simplex and Optimal Transport

If perpendicular vectors are good, are there even better ways to spread vectors out? Simplex Random Features suggests the answer is yes. Instead of 90-degree angles, this method arranges vectors to point toward the vertices of a simplex, resulting in obtuse angles. This configuration spreads the vectors even more uniformly than orthogonality, achieving the lowest possible estimation error for this class of methods.

Recent work has also begun to unify these heuristics into a rigorous mathematical framework. Isaac Reid and Adrian Weller demonstrated in Variance-Reducing Couplings for Random Features: Perspectives from Optimal Transport that the problem of choosing the best random features is fundamentally equivalent to the Kantorovich formulation of Optimal Transport. This link suggests that kernel approximation can be treated as a transport problem between the target distribution and our finite samples.

Computational Efficiency via Structured Matrices

While orthogonality reduces variance, it can be computationally expensive to generate and multiply large dense matrices. To solve this, researchers use Structured Random Features.

For example, Chang Feng and Shizhong Liao proposed Random Feature Mapping with Signed Circulant Matrix Projection. By using circulant matrices—where each row is a cyclic shift of the first—they achieve log-linear computation time using Fast Fourier Transforms (FFT). Similarly, Tan Yu and Ping Li showed in Fast and Compact Bilinear Pooling by Shifted Random Maclaurin that circularly shifting a single random vector can generate multiple valid approximations at almost zero extra cost.

Summary of Intuition

The evolution of this field can be summarized as a shift in how we view "randomness":

  1. Naive Randomness (RFF): Independent samples are easy but redundant (high variance).
  2. Orthogonal Randomness (ORF): Forcing vectors to be perpendicular removes redundancy (lower variance).
  3. Simplex Randomness (SimRF): Forcing vectors into obtuse angles maximizes spread (minimal variance).
  4. Structured Randomness (SCRF/SORF): Using mathematical symmetries (like circulant shifts) provides the benefits of spread with the speed of structured linear algebra.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 57 papers
  2. Version 1 · 2026-10-04 · 59 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_orthogonal_random_features_cd02c016,
  title = {orthogonal random features},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/orthogonal-random-features/rdr_cd02c016c547491d9c6eb235348c576e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_kernels_with_orthogonal_and_stru_cd02c016_v1,
  title = {Scaling Kernels with Orthogonal and Structured Random Features},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-kernels-with-orthogonal-and-structured-random-features/rdr_cd02c016c547491d9c6eb235348c576e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}