mlsanityData to 7 Oct 2026

Exploiting Hankel-Toeplitz Structures for Fast Computation of Kernel Precision Matrices

arXiv 2408.02346 ↗First posted 5 Aug 2024cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

The Hilbert-space Gaussian Process (HGP) approach offers a hyperparameter-independent basis function approximation for speeding up Gaussian Process (GP) inference by projecting the GP onto M basis functions. These properties result in a favorable data-independent O(M3) computational complexity during hyperparameter optimization but require a dominating one-time precomputation of the precision matrix costing O(NM2) operations. In this paper, we lower this dominating computational complexity to O(NM) with no additional approximations. We can do this because we realize that the precision matrix can be split into a sum of Hankel-Toeplitz matrices, each having O(M) unique entries. Based on this realization we propose computing only these unique entries at O(NM) costs. Further, we develop two theorems that prescribe sufficient conditions for the complexity reduction to hold generally for a wide range of other approximate GP models, such as the Variational Fourier Feature (VFF) approach. The two theorems do this with no assumptions on the data and no additional approximations of the GP models themselves. Thus, our contribution provides a pure speed-up of several existing, widely used, GP approximations, without further approximations.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 25 of its 49 references that are in the map. First posted on arXiv 5 Aug 2024.

Builds on

25 of 49 references.

References · 25

  1. 2018GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Accelerationcited by 603
  2. 2013Gaussian Processes for Big Datacited by 377
  3. 2014Scalable Variational Gaussian Process Classificationcited by 226
  4. 2015Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)cited by 175
  5. 2016GPflow: A Gaussian process library using TensorFlowcited by 139
  6. 2014Hilbert Space Methods for Reduced-Rank Gaussian Process Regressioncited by 88
  7. 2016Variational Fourier features for Gaussian processescited by 85
  8. 2018Constant-Time Predictive Distributions for Gaussian Processescited by 48
  9. 2020Sparse Gaussian Processes with Spherical Harmonic Featurescited by 43
  10. 2015Modeling and interpolation of the ambient magnetic field by Gaussian processescited by 28
  11. 2017Scalable Gaussian Processes with Billions of Inducing Inputs via Tensor Train Decompositioncited by 28
  12. 2020Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programmingcited by 28
13 more
  1. 2023Sampling from Gaussian Process Posteriors using Stochastic Gradient Descentcited by 27
  2. 2018Quadrature-based features for kernel approximationcited by 25
  3. 2017Gaussian Quadrature for Kernel Featurescited by 21
  4. 2021Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradientscited by 20
  5. 2015Computationally Efficient Bayesian Learning of Gaussian Process State Space Modelscited by 18
  6. 2016Parallelized Tensor Train Learning of Polynomial Classifierscited by 16
  7. 2023Stochastic Gradient Descent for Gaussian Processes Done Rightcited by 16
  8. 2021The SPDE approach for Gaussian and non-Gaussian fields: 10 years and still runningcited by 15
  9. 2018Scalable Magnetic Field SLAM in 3D Using Gaussian Process Mapscited by 10
  10. 2021Online Joint State Inference and Learning of Partially Unknown State-Space Modelscited by 9
  11. 2021Gauss-Legendre Features for Gaussian Process Regressioncited by 5
  12. 2021Faster Kernel Interpolation for Gaussian Processescited by 5
  13. 2023Distributed multi-agent magnetic field norm SLAM with Gaussian processescited by 2

Built on by

Not cited yet.