Simulating Gaussian processes on a lattice

March 17, 2022 β€” July 26, 2022

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 [RueGaussian2005@LoperLineartime2021;Durrande et al. (2019)], 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.
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.