Numerical integration, or quadrature, is a fundamental task in scientific computing, often taking the form of a weighted sum $\sum_{n=1}^N w_n f(x_n)$ to approximate an integral $\int f(x) d\mu(x)$. Kernel Quadrature (KQ) is a sophisticated variant where weights are optimized for functions within a specific Reproducing Kernel Hilbert Space (RKHS). While theoretically powerful, KQ often suffers from severe numerical instability, particularly when employing the widely used Gaussian kernel. This paper, published in BIT Numerical Mathematics, introduces a novel method to compute these weights accurately and stably using scaled Gauss–Hermite nodes.
The Challenge of Ill-Conditioning
The primary obstacle in Gaussian kernel quadrature is the "ill-conditioning" problem. When the kernel's length-scale $\ell$ is large—meaning the kernel is relatively "flat"—the kernel matrix used to determine the quadrature weights becomes nearly singular. In standard double-precision arithmetic, the condition number of this matrix can quickly exceed $10^{18}$ even for a modest number of points. This makes the direct inversion of the matrix impossible, forcing researchers to either limit the number of nodes or accept significant numerical errors.
A Spectral Solution: Mercer Eigendecomposition
The authors address this instability by leveraging the spectral properties of the Gaussian kernel. Instead of solving the standard linear system, they utilize the Mercer eigendecomposition, which expresses the kernel as a sum of its eigenvalues and eigenfunctions.
The core of their approach lies in two key innovations:
- Scaled Gauss–Hermite Nodes: Rather than using standard quadrature nodes, the authors employ the roots of the $N$-th Hermite polynomial, scaled by a factor determined by the kernel's length-scale.
- Explicit Weight Formula: By aligning the nodes with the kernel's spectral structure, the authors derive a closed-form, explicit expression for the quadrature weights. This formula utilizes classical Gauss–Hermite weights and a sum of Hermite polynomials, completely bypassing the need for matrix inversion.
Theoretical and Numerical Results
The proposed method offers several significant advantages over traditional KQ approaches:
- Numerical Stability: By truncating the Mercer expansion at $M=N$, the method focuses on the most significant eigenvalues while discarding the exponentially decaying components that typically cause matrix explosion. Experiments demonstrate stability even when $N=99$ and $\ell$ is large, conditions where "naive" KQ fails entirely.
- Exponential Convergence: The authors provide a rigorous proof that for functions belonging to the Gaussian RKHS, the integration error converges at an exponential rate as the number of nodes $N$ increases.
- Computational Efficiency: The explicit weight formula reduces the computational complexity from $O(N^3)$ (required for matrix inversion) to $O(N^2)$. This efficiency gain is particularly impactful when extending the method to high-dimensional problems via tensor product grids.
- Connection to Classical Theory: A notable theoretical insight is that as the length-scale $\ell \to \infty$, the proposed kernel quadrature rule converges to the classical Gauss–Hermite rule. This provides a bridge between modern kernel-based methods and traditional numerical analysis.
Implications and Future Directions
While the paper provides strong numerical evidence that the computed weights are positive—a desirable property that prevents numerical cancellation—a formal mathematical proof of this "positivity conjecture" remains an open challenge. Additionally, the current explicit formula is specifically tailored to scaled Gauss–Hermite nodes and Gaussian measures.
Despite these limitations, this work represents a major step forward for fields such as Gaussian Process regression and Probabilistic Numerics. By providing a stable, efficient, and theoretically grounded method for kernel-based integration, the authors have addressed a critical bottleneck in the practical application of Gaussian kernels.
Summary updated