Simulating Gaussian processes on a lattice

March 17, 2022 — July 26, 2022

Hilbert space
kernel tricks
Lévy processes
stochastic processes
time series

Assumed audience:

ML people

How can I simulate a Gaussian Processes on a lattice with a given covariance?

Figure 1

The general (non-lattice) case is given in historical overview in Liu et al. (2019), but in this notebook we are interested in specialising a little. Following the introduction in Dietrich and Newsam (1993), let’s say we wish to generate a stationary Gaussian process \(Y(x)\) on a points \(\Omega\). \(\Omega=(x_0, x_1,\dots, x_m)\).

Stationary in this context means that the covariance function \(r\) is translation-invariance and depend only on distance, so that it may be given \(r(|x|)\). Without loss of generality, we assume that \(\mathbb E[Y(x)]=0\) and \(\var[Y(x)]=1\).

The problem then reduces to generating a vector \(\vv y=(Y(x_0), Y(x_1), \dots, Y(x_m) )\sim \mathcal{N}(0, R)\) where \(R\) has entries \(R[p,q]=r(|x_p-x_q|).\)

Note that if \(\mathbb \varepsilon\sim\mathcal{N}(0, I)\) is an \(m+1\)-dimensional normal random variable, and \(AA^T=R\), then \(\vv y=\mm A \vv \varepsilon\) has the required distribution.

1 The circulant embedding trick

Figure 2

If we have additional structure, we can work more efficiently.

Suppose further that our points form a grid, \(\Omega=(x_0, x_0+h,\dots, x_0+mh)\); specifically, equally-spaced-points on a line.

We know that \(R\) has a Toeplitz structure. Moreover it is non-negative definite, with \(\vv x^t\mm R \vv x \geq 0\forall \vv x.\) (Why?) 🏗

Wilson et al. (2021) credits the following authors:

Well-known examples of this trend include banded and sparse matrices in the context of one-dimensional Gaussian processes and Gauss–Markov random fields Loper et al. (2021), as well as Kronecker and Toeplitz matrices when working with regularly-spaced grids (Dietrich and Newsam 1997; Grace Chan and Wood 1997).

Figure 3

2 References

Abrahamsen, Kvernelv, and Barker. 2018. Simulation Of Gaussian Random Fields Using The Fast Fourier Transform (Fft).” In.
Chan, Grace, and Wood. 1997. Algorithm AS 312: An Algorithm for Simulating Stationary Gaussian Random Fields.” Journal of the Royal Statistical Society: Series C (Applied Statistics).
Chan, G., and Wood. 1999. Simulation of Stationary Gaussian Vector Fields.” Statistics and Computing.
Davies, and Bryant. 2013. On Circulant Embedding for Gaussian Random Fields in R.” Journal of Statistical Software.
Dietrich, and Newsam. 1993. A Fast and Exact Method for Multidimensional Gaussian Stochastic Simulations.” Water Resources Research.
———. 1997. Fast and Exact Simulation of Stationary Gaussian Processes Through Circulant Embedding of the Covariance Matrix.” SIAM Journal on Scientific Computing.
Durrande, Adam, Bordeaux, et al. 2019. Banded Matrix Operators for Gaussian Markov Models in the Automatic Differentiation Era.” In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics.
Erhel, Oumouni, Pichot, et al. n.d. “Analysis of Continuous Spectral Method for Sampling Stationary Gaussian Random Fields.”
Gilboa, Saatçi, and Cunningham. 2015. Scaling Multidimensional Inference for Structured Gaussian Processes.” IEEE Transactions on Pattern Analysis and Machine Intelligence.
Graham, Kuo, Nuyens, et al. 2017a. Analysis of Circulant Embedding Methods for Sampling Stationary Random Fields.” arXiv:1710.00751 [Math].
———, et al. 2017b. Circulant Embedding with QMC — Analysis for Elliptic PDE with Lognormal Coefficients.” arXiv:1710.09254 [Math].
Gray. 2006. Toeplitz and Circulant Matrices: A Review.
Guinness, and Fuentes. 2016. Circulant Embedding of Approximate Covariances for Inference From Gaussian Data on Large Lattices.” Journal of Computational and Graphical Statistics.
Haran. 2011. Gaussian Random Field Models for Spatial Data.” In Handbook of Markov Chain Monte Carlo.
Lang, and Potthoff. 2011. Fast Simulation of Gaussian Random Fields.” Monte Carlo Methods and Applications.
Liu, Li, Sun, et al. 2019. Advances in Gaussian Random Field Generation: A Review.” Computational Geosciences.
Loper, Blei, Cunningham, et al. 2021. Linear-Time Inference for Gaussian Processes on One Dimension.” Journal of Machine Learning Research.
Powell. 2014. “Generating Realisations of Stationary Gaussian Random Fields by Circulant Embedding.” Matrix.
Rue, Havard. 2001. Fast Sampling of Gaussian Markov Random Fields.” Journal of the Royal Statistical Society. Series B (Statistical Methodology).
Rue, Håvard, and Held. 2005. Gaussian Markov Random Fields: Theory and Applications. Monographs on Statistics and Applied Probability 104.
Teichmann, and van den Boogaart. 2016. Efficient Simulation of Stationary Multivariate Gaussian Random Fields with Given Cross-Covariance.” Applied Mathematics.
Whittle, Peter. 1952. Some Results in Time Series Analysis.” Scandinavian Actuarial Journal.
Whittle, P. 1952. Tests of Fit in Time Series.” Biometrika.
———. 1953a. The Analysis of Multiple Stationary Time Series.” Journal of the Royal Statistical Society: Series B (Methodological).
———. 1953b. Estimation and Information in Stationary Time Series.” Arkiv För Matematik.
Whittle, P. 1954. “On Stationary Processes in the Plane.” Biometrika.
Wilson, Borovitskiy, Terenin, et al. 2021. Pathwise Conditioning of Gaussian Processes.” Journal of Machine Learning Research.