Simulating Gaussian processes on a lattice

Assumed audience:

ML people

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

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.

The circulant embedding trick

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 [;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).


Abrahamsen, P., V. Kvernelv, and D. Barker. 2018. β€œSimulation Of Gaussian Random Fields Using The Fast Fourier Transform (Fft).” In, 2018:1–14. European Association of Geoscientists & Engineers.
Chan, Grace, and Andrew T.A. Wood. 1997. β€œAlgorithm AS 312: An Algorithm for Simulating Stationary Gaussian Random Fields.” Journal of the Royal Statistical Society: Series C (Applied Statistics) 46 (1): 171–81.
Chan, G., and A. T. A. Wood. 1999. β€œSimulation of Stationary Gaussian Vector Fields.” Statistics and Computing 9 (4): 265–68.
Davies, Tilman M., and David Bryant. 2013. β€œOn Circulant Embedding for Gaussian Random Fields in R.” Journal of Statistical Software 55 (9).
Dietrich, C. R., and G. N. Newsam. 1993. β€œA Fast and Exact Method for Multidimensional Gaussian Stochastic Simulations.” Water Resources Research 29 (8): 2861–69.
β€”β€”β€”. 1997. β€œFast and Exact Simulation of Stationary Gaussian Processes Through Circulant Embedding of the Covariance Matrix.” SIAM Journal on Scientific Computing 18 (4): 1088–1107.
Durrande, Nicolas, Vincent Adam, Lucas Bordeaux, Stefanos Eleftheriadis, and James Hensman. 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, 2780–89. PMLR.
Erhel, Jocelyne, Mestapha Oumouni, GΓ©raldine Pichot, and Franck Schoefs. n.d. β€œAnalysis of Continuous Spectral Method for Sampling Stationary Gaussian Random Fields,” 26.
Gilboa, E., Y. SaatΓ§i, and J. P. Cunningham. 2015. β€œScaling Multidimensional Inference for Structured Gaussian Processes.” IEEE Transactions on Pattern Analysis and Machine Intelligence 37 (2): 424–36.
Graham, Ivan G., Frances Y. Kuo, Dirk Nuyens, Rob Scheichl, and Ian H. Sloan. 2017a. β€œAnalysis of Circulant Embedding Methods for Sampling Stationary Random Fields.” arXiv:1710.00751 [Math], October.
β€”β€”β€”. 2017b. β€œCirculant Embedding with QMC β€” Analysis for Elliptic PDE with Lognormal Coefficients.” arXiv:1710.09254 [Math], October.
Gray, Robert M. 2006. Toeplitz and Circulant Matrices: A Review. Vol. 2.
Guinness, Joseph, and Montserrat Fuentes. 2016. β€œCirculant Embedding of Approximate Covariances for Inference From Gaussian Data on Large Lattices.” Journal of Computational and Graphical Statistics 26 (1): 88–97.
Haran, Murali. 2011. β€œGaussian Random Field Models for Spatial Data.” In Handbook of Markov Chain Monte Carlo, edited by Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Vol. 20116022. Chapman and Hall/CRC.
Lang, Annika, and JΓΌrgen Potthoff. 2011. β€œFast Simulation of Gaussian Random Fields.” Monte Carlo Methods and Applications 17 (3).
Liu, Yang, Jingfa Li, Shuyu Sun, and Bo Yu. 2019. β€œAdvances in Gaussian Random Field Generation: A Review.” Computational Geosciences 23 (5): 1011–47.
Powell, Catherine E. 2014. β€œGenerating Realisations of Stationary Gaussian Random Fields by Circulant Embedding.” Matrix 2 (2): 1.
Rue, Havard. 2001. β€œFast Sampling of Gaussian Markov Random Fields.” Journal of the Royal Statistical Society. Series B (Statistical Methodology) 63 (2): 325–38.
Rue, HΓ₯vard, and Leonhard Held. 2005. Gaussian Markov Random Fields: Theory and Applications. Monographs on Statistics and Applied Probability 104. Boca Raton: Chapman & Hall/CRC.
Teichmann, Jakob, and Karl-Gerald van den Boogaart. 2016. β€œEfficient Simulation of Stationary Multivariate Gaussian Random Fields with Given Cross-Covariance.” Applied Mathematics 7 (17): 2183–94.
Whittle, P. 1954. β€œOn Stationary Processes in the Plane.” Biometrika 41 (3/4): 434–49.
Whittle, P. 1952. β€œTests of Fit in Time Series.” Biometrika 39 (3-4): 309–18.
β€”β€”β€”. 1953a. β€œThe Analysis of Multiple Stationary Time Series.” Journal of the Royal Statistical Society: Series B (Methodological) 15 (1): 125–39.
β€”β€”β€”. 1953b. β€œEstimation and Information in Stationary Time Series.” Arkiv FΓΆr Matematik 2 (5): 423–34.
Whittle, Peter. 1952. β€œSome Results in Time Series Analysis.” Scandinavian Actuarial Journal 1952 (1-2): 48–60.
Wilson, James T, Viacheslav Borovitskiy, Alexander Terenin, Peter Mostowsky, and Marc Peter Deisenroth. 2021. β€œPathwise Conditioning of Gaussian Processes.” Journal of Machine Learning Research 22 (105): 1–47.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.