Orthonormal Expansions for Translation-Invariant Kernels

Filip Tronarp, Toni Karvonen

This blog-style summary provides an overview of the paper "Orthonormal Expansions for Translation-Invariant Kernels" by Filip Tronarp and Toni Karvonen.

TL;DR

The authors introduce a general Fourier-analytic "recipe" for constructing orthonormal basis expansions of translation-invariant kernels (like the Matérn and Gaussian kernels) using standard bases of $L_2(\mathbb{R})$. This technique allows researchers to break down complex kernels into series expansions, enabling more efficient "sub-cubic" computations and providing new theoretical tools for Gaussian process modeling.

What Problem Does This Paper Address?

In fields like spatial statistics and machine learning, kernels are the workhorses that define how points in space relate to one another. However, working with these kernels often involves computational costs that scale cubically ($O(N^3)$) with the number of data points. To bypass this, researchers use orthonormal expansions—essentially breaking a kernel down into a sum of simpler basis functions.

While these expansions are incredibly useful for numerical stability and speed, they are surprisingly difficult to find. Until now, explicit expansions were only widely known for the Gaussian kernel and the simplest Matérn kernel (order 1/2). The challenge is that most existing methods are "space-centric," starting with a specific Hilbert space and trying to find its kernel. This paper flips the script with a "kernel-centric" approach, starting with the kernels we actually use in practice and deriving their expansions.

Methods

The core of the paper is Theorem 1.1, a general technique for constructing orthonormal bases for the Reproducing Kernel Hilbert Space (RKHS) of a translation-invariant kernel.

The "recipe" works as follows:

  1. Start with the Kernel: Take a translation-invariant kernel $r(t, u) = \Phi(t - u)$.
  2. Fourier Domain Square Root: Find the Fourier transform (spectral density) of the kernel and take its "square root" in the frequency domain.
  3. Map the Basis: Take a known orthonormal basis of the standard square-integrable function space $L_2(\mathbb{R})$ (like Laguerre or Hermite functions).
  4. Convolve: Convolve these standard basis functions with the time-domain version of the spectral square root.

The authors demonstrate this by deriving specific expansions for:

  • Matérn Kernels: For all half-integer orders, using Laguerre functions.
  • Cauchy Kernels: Using rational functions, leveraging the Fourier duality between Cauchy and Matérn kernels.
  • Gaussian Kernels: Using Hermite functions, providing a more principled derivation than the standard ad hoc methods like Mehler’s formula.

Datasets

Not discussed in the paper. As a theoretical mathematical work, the paper focuses on proofs, derivations, and error analysis rather than empirical testing on specific datasets.

Key Insights and Ideas

  • The "Almost Mercer" Property: A major finding is that the Matérn expansions derived here are "almost" Mercer expansions. In a standard Mercer expansion, basis functions are eigenfunctions of an integral operator. The authors show that for Matérn kernels, most of the basis functions fit this description, except for a small, finite "null-space" set that behaves differently near the origin.
  • Duality as a Tool: The authors utilize the fact that the Cauchy kernel is the Fourier dual of the Matérn-1/2 kernel. This allowed them to modify Laguerre functions to create a new class of "Cauchy-Laguerre" functions.
  • Principled Gaussian Derivation: While the Gaussian expansion was already known, it was usually derived through complex identities. This paper shows it is a natural consequence of their general Fourier technique, suggesting that a specific standard deviation for the Gaussian weight ($\alpha = \sqrt{2/3}$) is the most "natural" choice.

Key Results

  • Explicit Formulas: The paper provides ready-to-use closed-form expressions for basis functions $\psi_m(t)$ for the Matérn, Cauchy, and Gaussian kernels.
  • Truncation Error Bounds: The authors provide rigorous bounds on how much error is introduced when you stop the expansion after $n$ terms.
  • For the Gaussian kernel, the error decays exponentially ($1/3^n$), making it extremely efficient to approximate.
  • For Matérn kernels, the error decays polynomially ($n^{-(\nu+1/2)}$), which is slower but still mathematically well-behaved.
  • Uniform Convergence: The authors prove that while these expansions converge pointwise everywhere, uniform convergence for Matérn kernels on the entire real line is likely impossible due to the nature of the bounds.

Limitations and Future Work

  • The Null-Space Issue: The Matérn basis functions in the "null-space" do not decay to zero fast enough at the origin to be included in certain weighted $L_2$ spaces. The authors suggest that future work could investigate "symmetric square-roots" to see if a more unified space can be found.
  • Cauchy Weight Spaces: While they found the expansion for the Cauchy kernel, identifying the specific weighted $L_2$ space where these basis functions are perfectly orthogonal remains an open problem.
  • Higher Dimensions: The current work focuses on the real line ($\mathbb{R}$). Extending these explicit expansions to multi-dimensional spaces ($\mathbb{R}^d$) is a logical next step for practical applications in spatial statistics.

Summary updated

Abstract

We present a general Fourier analytic technique for constructing orthonormal basis expansions of translation-invariant kernels from orthonormal bases of $\mathscr{L}_2(\mathbb{R})$. This allows us to derive explicit expansions on the real line for (i) Matérn kernels of all half-integer orders in terms of associated Laguerre functions, (ii) the Cauchy kernel in terms of rational functions, and (iii) the Gaussian kernel in terms of Hermite functions.
BibTeX
@article{tronarp2022orthonormal,
  author = {Filip Tronarp and Toni Karvonen},
  title = {{Orthonormal Expansions for Translation-Invariant Kernels}},
  journal = {J. Approx. Theory},
  year = {2022},
}
Figure