Kernel Interpolation with Sparse Grids
Kernel Interpolation with Sparse Grids
复制标题
DOI：
10.48550/arxiv.2305.14451
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Mohit Yadav;D. Sheldon;Cameron Musco
中科院分区：
文献类型：
--
作者：
Mohit Yadav;D. Sheldon;Cameron Musco
结构化核插值（SKI）通过使用诱导点的密集网格对核协方差函数进行插值来加速高斯过程（GP）推断，其对应的核矩阵是高度结构化的，因此适合于快速线性代数。不幸的是，SKI在输入点的维度上的伸缩性很差，因为密集的网格大小随维度呈指数级增长。为了缓解这个问题，我们建议在SKI框架内使用稀疏网格。这些网格可以实现精确的插值，但随着维度的增加，点的数量增长得更慢。针对稀疏网格核矩阵，提出了一种近似线性时间的矩阵向量乘算法。接下来，我们将介绍如何稀疏网格可以结合一个有效的插值方案的基础上单纯形。通过这些变化，我们证明了SKI可以扩展到更高的维度，同时保持准确性。
Structured kernel interpolation (SKI) accelerates Gaussian process (GP) inference by interpolating the kernel covariance function using a dense grid of inducing points, whose corresponding kernel matrix is highly structured and thus amenable to fast linear algebra. Unfortunately, SKI scales poorly in the dimension of the input points, since the dense grid size grows exponentially with the dimension. To mitigate this issue, we propose the use of sparse grids within the SKI framework. These grids enable accurate interpolation, but with a number of points growing more slowly with dimension. We contribute a novel nearly linear time matrix-vector multiplication algorithm for the sparse grid kernel matrix. Next, we describe how sparse grids can be combined with an efficient interpolation scheme based on simplices. With these changes, we demonstrate that SKI can be scaled to higher dimensions while maintaining accuracy.