Kernel methods and Gaussian Processes (GPs) offer elegant, non-parametric flexibility and rigorous uncertainty quantification. However, they suffer from a notorious computational bottleneck: for $N$ data points, computing the full covariance (or Gram) matrix requires $O(N^2)$ space, and solving or training the model typically requires $O(N^3)$ time due to matrix inversions or log-determinant computations. This cubic bottleneck historically restricted GPs and kernel ridge regression to small datasets ($N < 10,000$).
Early scaling attempts explored various workarounds. For instance, Yamana et al. trained ensembles of kernel machines on small, independent subsets to achieve linear scaling, while Yang et al. leveraged the Improved Fast Gauss Transform to accelerate matrix-vector products within iterative solvers. Other approaches optimized low-rank decompositions like the Nyström method by incorporating task-specific priors (Zhang et al.). However, a unified framework that preserves the exact kernel's expressive power while scaling linearly remained elusive until the development of Structured Kernel Interpolation (SKI).
The Core Intuition: Mapping to a Regular Grid
How do we bypass computing an $N \times N$ matrix? The core insight behind SKI is to decouple the data points from the underlying kernel computation by introducing a regular, synthetic grid of $M$ inducing points, $G$.
Instead of evaluating the kernel function directly between every pair of arbitrary data points $x_i$ and $x_j$, we evaluate the kernel only on the grid points to form a grid covariance matrix $K_{GG}$. We then approximate the covariance between any two arbitrary data points by interpolating from this grid.
Mathematically, the full kernel matrix $K_{XX}$ is approximated as:
$$\tilde{K}_{XX} = W K_{GG} W^T$$
where $W$ is an $N \times M$ sparse interpolation matrix. Each row of $W$ contains the interpolation weights (e.g., from local linear or cubic interpolation) that map a real data point $x_i$ to its nearest neighbors on the grid $G$. Because interpolation is purely local, each row of $W$ has only a tiny, constant number of non-zero entries.
[Data Points X] ---> [Sparse Interpolation W] ---> [Regular Grid G (K_GG)]
Why it Works: Exploiting Algebraic Structure
The real magic happens when we look at the structure of $K_{GG}$. Because the grid $G$ is chosen to be completely regular and evenly spaced, the covariance between grid points depends only on their relative distance. This means $K_{GG}$ possesses a highly exploitable algebraic structure:
- In one dimension, $K_{GG}$ is a Toeplitz matrix (constant along its diagonals).
- In multiple dimensions, if the grid is a Cartesian product, $K_{GG}$ becomes a Kronecker product of Toeplitz matrices.
As Wilson et al. demonstrated, this structure drastically accelerates matrix-vector multiplications (MVMs), which are the fundamental building blocks of iterative linear solvers like Conjugate Gradient (CG).
Suppose we need to compute the product $\tilde{K}_{XX} v$ for some vector $v$. We evaluate it from right to left:
$$\tilde{K}_{XX} v = W \left( K_{GG} \left( W^T v \right) \right)$$
Let's trace the computational cost of each step:
- $W^T v$: Since $W$ is extremely sparse (a constant number of non-zero entries per row), multiplying by $W^T$ takes $O(N)$ time.
- $K_{GG} (W^T v)$: Multiplying a Toeplitz matrix by a vector can be computed in the frequency domain using the Fast Fourier Transform (FFT) in $O(M \log M)$ time. For multi-dimensional Kronecker structures, this scales as $O(d M^{1/d} \log M)$.
- $W (\dots)$: Multiplying the result by $W$ again takes $O(N)$ time.
By avoiding the explicit construction of the $N \times N$ matrix, the total complexity of an MVM drops from $O(N^2)$ to $O(N + M \log M)$. This allows kernel methods to scale linearly with the number of data points.
Scaling Training: Log Determinants in Linear Time
While fast MVMs allow for rapid predictions, training a Gaussian Process requires maximizing the marginal log-likelihood, which involves computing a log-determinant term: $\log |K_{XX} + \sigma^2 I|$. Computing a determinant traditionally requires a Cholesky decomposition, costing $O(N^3)$ time.
To maintain linear scaling during training, Eriksson et al. introduced a method that combines SKI with stochastic trace estimation and Lanczos/Chebyshev expansions. Instead of computing the determinant explicitly, the log-determinant is rewritten as a trace of a matrix function, which can be approximated using only a small number of fast SKI-based matrix-vector multiplications. This breakthrough allowed fully probabilistic kernel learning to scale linearly to massive datasets with hundreds of thousands of observations (Jang et al.; Wilson et al.).
Overcoming the Curse of Dimensionality
If SKI relies on a regular grid, doesn't it suffer from the curse of dimensionality? If we place a grid across $d$ dimensions with $m$ points per dimension, the total number of grid points is $M = m^d$, which grows exponentially.
Researchers have developed several ingenious strategies to bypass this limitation:
- Deep Kernel Learning (DKL): Wilson et al. proposed combining the feature-extraction power of Deep Neural Networks with GPs. The network projects high-dimensional inputs down to a low-dimensional space (e.g., 1D or 2D), and SKI is applied exclusively within this low-dimensional embedding. This architecture has been successfully deployed in complex real-time scenarios, such as predicting vehicle dynamics in autonomous racing (Ning et al.) and modeling counterfactual outcomes (Caron et al.).
- Additive Decompositions: Another strategy decomposes a high-dimensional kernel into a sum of one-dimensional projected kernels. This allows SKI to operate on each 1D projection independently, completely bypassing the exponential grid growth and enabling fast inference in spaces with thousands of dimensions.
- Alternative Feature Mappings: When grids are entirely impractical, alternative linear-time approximations are used, such as randomized feature mappings (Hu et al.; Entesari et al.) or Locality Sensitive Hashing (Zandieh et al.), which approximate smooth kernels without relying on rigid coordinate grids.
By transforming the computational landscape of kernel machines from cubic to linear, these techniques have transitioned GPs from small-scale theoretical tools to high-performance engines for massive datasets. Applications range from physics-informed 3D magnetic field mapping (Kok et al.) to anomalous pattern detection in non-iid data streams (Herlands et al.), proving that non-parametric Bayesian methods can thrive in the era of big data.
Key Foundational Work
Efficient Kernel Machines Using the Improved Fast Gauss Transform (2004) — contributed 1 concept elements to this direction.
On different ensembles of kernel machines (2003) — contributed 1 concept elements to this direction.