Kernel methods are celebrated for their ability to model complex, non-linear relationships without requiring an explicit definition of a high-dimensional feature space. By using the "kernel trick," algorithms like Kernel Ridge Regression (KRR), Support Vector Machines (SVM), and Gaussian Processes operate implicitly within an infinite-dimensional Reproducing Kernel Hilbert Space (RKHS).
However, this expressive power comes with a severe computational penalty. To train an exact kernel model on a dataset of $N$ samples, one must compute an $N \times N$ kernel matrix (or Gram matrix) $K$, where each entry $K_{ij} = k(x_i, x_j)$ represents the similarity between two data points. As noted across numerous domains—from causal inference (Erik Sverdrup et al. in their work) and partial differential equation discovery (Da Long et al. in their paper) to microbiome analysis (Shimeng Huang et al. in their study)—this matrix introduces a quadratic $O(N^2)$ memory bottleneck and a cubic $O(N^3)$ computational bottleneck due to required matrix inversions or decompositions. When $N$ scales into the hundreds of thousands or millions, exact computation becomes entirely impossible.
The Core Intuition: Low-Rank Redundancy
Why should we expect to bypass this $O(N^3)$ wall? The saving grace is that for most real-world datasets, the full kernel matrix $K$ is highly redundant. Its eigenvalues typically decay rapidly, meaning that the matrix can be accurately approximated by a low-rank matrix. If we can find an approximated matrix $\tilde{K}$ of rank $m$ (where $m \ll N$) that closely mirrors $K$, we can reduce the computational complexity from $O(N^3)$ to $O(N m^2)$.
Two primary paradigms have emerged to construct these low-rank approximations: data-dependent sampling (the Nyström method) and data-independent projection (Random Fourier Features).
Data-Dependent Approximation: The Nyström Method
The Nyström method approximates the large $N \times N$ kernel matrix by sampling a small subset of $m$ rows and columns, often called "landmarks." Let $C \in \mathbb{R}^{N \times m}$ represent the sampled columns, and $W \in \mathbb{R}^{m \times m}$ represent the intersection of those rows and columns. The Nyström approximation is defined as:
$$\tilde{K} = C W^{-1} C^T$$
Intuitively, instead of computing the similarity between every single pair of points, we only compute the similarity of all points to the $m$ landmarks ($C$), and use the internal relationships of the landmarks ($W^{-1}$) to extrapolate the rest of the matrix.
Zenglin Xu et al. demonstrated in their analysis that leveraging the restricted eigenvalue condition allows the Nyström method to achieve massive computational speedups without sacrificing the accuracy of sparse solutions. To improve accuracy further, Shusen Wang et al. introduced adaptive sampling strategies in their paper to select better landmarks, while Sanjiv Kumar et al. proposed an ensemble approach in The Ensemble Nystrom Method that combines multiple independent Nyström approximations to scale kernel methods to datasets exceeding a million instances.
Data-Independent Projection: Random Fourier Features
An alternative approach avoids constructing the kernel matrix entirely. Instead, it constructs an explicit, low-dimensional feature map $\phi(x) \in \mathbb{R}^m$ such that the inner product $\langle \phi(x), \phi(y) \rangle$ approximates the kernel function $k(x, y)$.
For shift-invariant kernels (such as the Gaussian RBF kernel), Bochner's Theorem states that the kernel function is the Fourier transform of a probability distribution. By sampling $m$ random frequencies from this distribution, we can construct a randomized feature space. This turns a non-linear kernel problem back into a standard linear problem, which can be solved in $O(N m^2)$ time.
The choice between Nyström and Random Fourier Features (RFF) involves a fundamental trade-off. As proven by Tianbao Yang et al. in their comparative study, because the Nyström method is data-dependent, it can exploit the specific "eigengap" of the data's kernel matrix to achieve a tighter generalization error bound of $O(1/m)$ compared to the $O(1/\sqrt{m})$ bound of the data-independent RFF approach.
Preserving Statistical Guarantees
A natural concern is whether these approximations degrade the statistical performance of the model. Remarkably, theoretical work shows that approximation does not imply a loss in predictive power.
Junhong Lin et al. proved in their paper that sketched and regularized kernel algorithms can achieve the exact same minimax optimal statistical convergence rates as full-scale kernel ridge regression. The key requirement is that the sketch dimension $m$ must scale proportionally with the effective dimension (or degrees of freedom) of the data, rather than the total sample size $N$.
Similarly, Haim Avron et al. developed modified sampling strategies for RFF in their work that drastically reduce the number of features needed while maintaining rigorous statistical guarantees. Even under complex data structures, such as time-series or dependent data, Chao Wang et al. showed in their paper how random features can preserve statistical performance depending on the decay rate of the data dependencies.
Broader Applications
By mitigating the cubic complexity bottleneck, these scaling techniques have unlocked non-parametric modeling across diverse machine learning tasks. For instance, Changjiang Yang demonstrated in Efficient Kernel Machines Using the Improved Fast Gauss Transform how numerical approximations could achieve linear-time performance for kernel machines.
These efficiency gains have enabled the scaling of advanced frameworks like Unsupervised Kernel Dimension Reduction (Meihong Wang et al. in their paper), conditional mean embeddings (Zhu Li et al. in their work), and infinite-dimensional covariance operators for image classification (Minh Ha Quang et al. in their study). Ultimately, these methods bridge the gap between the rich expressive power of infinite-dimensional Hilbert spaces and the practical constraints of modern big data.