Banded Matrix Operators for Gaussian Markov Models in the Automatic Differentiation Era

Nicolas Durrande, Vincent Adam, Lucas Bordeaux, Stefanos Eleftheriadis, James Hensman

Abstract

Banded matrices can be used as precision matrices in several models including linear state-space models, some Gaussian processes, and Gaussian Markov random fields. The aim of the paper is to make modern inference methods (such as variational inference or gradient-based sampling) available for Gaussian models with banded precision. We show that this can efficiently be achieved by equipping an automatic differentiation framework, such as TensorFlow or PyTorch, with some linear algebra operators dedicated to banded matrices. This paper studies the algorithmic aspects of the required operators, details their reverse-mode derivatives, and show that their complexity is linear in the number of observations.

Introduction

Gaussian Processes (GPs) are fundamental to probabilistic modeling, yet they are often constrained by the "cubic curse"—computational costs that scale at $O(n^3)$ time and $O(n^2)$ space relative to the number of observations $n$. While sparse GPs using inducing points are a common mitigation, many models naturally possess a Markov structure where the precision matrix (the inverse of the covariance matrix) is banded.

Banded matrices, where non-zero entries are confined to a small diagonal band, appear frequently in state-space models, time-series analysis, and Gaussian Markov Random Fields (GMRFs). Despite their ubiquity, modern automatic differentiation (AD) frameworks like TensorFlow and PyTorch are primarily optimized for dense or general sparse tensors. They lack high-performance, specialized operators for banded matrices, particularly the reverse-mode derivatives essential for gradient-based learning methods like Hamiltonian Monte Carlo (HMC) or Variational Inference (VI). This paper bridges that gap by introducing efficient, differentiable banded matrix operators.

Methods: Banded Operators for Automatic Differentiation

The core contribution of this work is a suite of linear algebra primitives designed for banded matrices, integrated as custom operators into TensorFlow.

Key Technical Primitives

  1. Banded Cholesky Decomposition: Efficient implementation of $LL^T = Q$, along with triangular solves and matrix products, all maintaining linear complexity.
  2. Sparse Inverse Subset (Takahashi’s Algorithm): For Variational Inference, computing the Evidence Lower Bound (ELBO) requires marginal variances. Takahashi’s algorithm allows for the computation of elements in the inverse matrix $Q^{-1}$ that correspond to the non-zero band of $Q$ in $O(Nl^2)$ time, avoiding a full $O(N^3)$ inversion.
  3. Reverse-Mode Derivatives: To enable gradient-based optimization, the authors derived and implemented the sensitivity functions for each forward operator. Crucially, these derivatives preserve the $O(Nl^2)$ linear complexity, ensuring that the AD engine does not inadvertently trigger dense, cubic-time calculations.

Experimental Evaluation

The framework was evaluated on two distinct benchmarks: a time-series regression problem and a large-scale spatial GMRF.

Mauna Loa CO2 Concentrations

Using the classic Mauna Loa dataset, the authors implemented a Gaussian Process with a complex compositional kernel (Matérn + Quasi-periodic). This model has a state-space representation that yields a banded precision matrix. As shown in the performance plots below, the custom banded operators achieved a three-order-of-magnitude speedup over standard GP implementations (like GPflow) as the dataset size increased. While standard GPs scaled cubically, the banded approach maintained strict linear scaling.

Performance scaling and CO2 concentration prediction results.

Porto Taxi Pick-ups

To demonstrate scalability on graphs, the authors modeled taxi pick-up density in Porto, Portugal, as a GMRF on the city's road network ($N=11,284$ nodes). This problem involved a non-conjugate Poisson likelihood, necessitating HMC or VI.

Predicted latent field for the Porto Taxi dataset using a GMRF on the road network.

The banded framework successfully handled this large-scale inference, which would be computationally prohibitive using dense covariance methods. By exploiting the sparsity of the precision matrix, the approach also reduced the memory footprint by nearly two orders of magnitude.

Key Insights and Conclusion

The primary bottleneck for many "classical" probabilistic models in the deep learning era has been the lack of low-level, differentiable building blocks. By focusing on the precision matrix rather than the covariance matrix, we can exploit the Markov property to achieve massive efficiency gains.

While the complexity is linear in the number of observations $N$, it remains sensitive to the bandwidth $l$ ($O(Nl^2)$). Future work may extend these AD primitives to more general sparsity patterns, such as those arising from nested dissection, to support even more complex graph structures. Ultimately, this work demonstrates that adding a few specialized banded operators can unlock a vast library of efficient Gaussian Markov models for modern machine learning workflows.

Summary updated

Abstract

Banded matrices can be used as precision matrices in several models including linear state-space models, some Gaussian processes, and Gaussian Markov random fields. The aim of the paper is to make modern inference methods (such as variational inference or gradient-based sampling) available for Gaussian models with banded precision. We show that this can efficiently be achieved by equipping an automatic differentiation framework, such as TensorFlow or PyTorch, with some linear algebra operators dedicated to banded matrices. This paper studies the algorithmic aspects of the required operators, details their reverse-mode derivatives, and show that their complexity is linear in the number of observations.
BibTeX
@inproceedings{durrande2019banded,
  author = {Nicolas Durrande and Vincent Adam and Lucas Bordeaux and Stefanos Eleftheriadis and James Hensman},
  title = {{Banded Matrix Operators for Gaussian Markov Models in the Automatic Differentiation Era}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=BfQgfzMQ0bW},
}
Figure