Analysis of circulant embedding methods for sampling stationary random fields

Ivan G. Graham, Frances Y. Kuo, Dirk Nuyens, Robert Scheichl, Ian H. Sloan

Research output: Contribution to journalArticle

3 Citations (Scopus)
13 Downloads (Pure)

Abstract

A standard problem in uncertainty quantification and in computational statistics is the sampling of stationary Gaussian random fields with given covariance in a d-dimensional (physical) domain. In many applications it is sufficient to perform the sampling on a regular grid on a cube enclosing the physical domain, in which case the corresponding covariance matrix is nested block Toeplitz. After extension to a nested block circulant matrix, this can be diagonalized by FFT—the “circulant embedding method.” Provided the circulant matrix is positive definite, this provides a finite expansion of the field in terms of a deterministic basis, with coefficients given by i.i.d. standard normals. In this paper we prove, under mild conditions, that the positive definiteness of the circulant matrix is always guaranteed, provided the enclosing cube is sufficiently large. We examine in detail the case of the Matérn covariance, and prove (for fixed correlation length) that, as h 0 ? 0, positive definiteness is guaranteed when the random field is sampled on a cube of size order (1 + ? 1/ 2 log h - 0 1 ) times larger than the size of the physical domain. (Here h 0 is the mesh spacing of the regular grid and ? the Matérn smoothness parameter.) We show that the sampling cube can become smaller as the correlation length decreases when h 0 and ? are fixed. Our results are confirmed by numerical experiments. We prove several results about the decay of the eigenvalues of the circulant matrix. These lead to the conjecture, verified by numerical experiment, that they decay with the same rate as the Karhunen–Loève eigenvalues of the covariance operator. The method analyzed here complements the numerical experiments for uncertainty quantification in porous media problems in an earlier paper by the same authors in J. Comput. Phys., 230 (2011), pp. 3668–3694.

Original languageEnglish
Pages (from-to)1871-1895
Number of pages25
JournalSIAM Journal on Numerical Analysis (SINUM)
Volume56
Issue number3
Early online date28 Jun 2018
DOIs
Publication statusPublished - 2018

Fingerprint

Random Field
Regular hexahedron
Positive Definiteness
Circulant Matrix
Correlation Length
Sampling
Numerical Experiment
Decay
Covariance Operator
Eigenvalue
Experiments
Spacing
Smoothness
Mesh
Grid
Decrease

Keywords

  • Analysis
  • Circulant embedding
  • Fast Fourier transform
  • Gaussian random fields
  • Matérn covariance
  • Statistical homogeneity

ASJC Scopus subject areas

  • Numerical Analysis

Cite this

Analysis of circulant embedding methods for sampling stationary random fields. / Graham, Ivan G.; Kuo, Frances Y.; Nuyens, Dirk ; Scheichl, Robert; Sloan, Ian H.

In: SIAM Journal on Numerical Analysis (SINUM), Vol. 56, No. 3, 2018, p. 1871-1895.

Research output: Contribution to journalArticle

@article{eb258c9492644361ad2a954c76b733ca,
title = "Analysis of circulant embedding methods for sampling stationary random fields",
abstract = "A standard problem in uncertainty quantification and in computational statistics is the sampling of stationary Gaussian random fields with given covariance in a d-dimensional (physical) domain. In many applications it is sufficient to perform the sampling on a regular grid on a cube enclosing the physical domain, in which case the corresponding covariance matrix is nested block Toeplitz. After extension to a nested block circulant matrix, this can be diagonalized by FFT—the “circulant embedding method.” Provided the circulant matrix is positive definite, this provides a finite expansion of the field in terms of a deterministic basis, with coefficients given by i.i.d. standard normals. In this paper we prove, under mild conditions, that the positive definiteness of the circulant matrix is always guaranteed, provided the enclosing cube is sufficiently large. We examine in detail the case of the Mat{\'e}rn covariance, and prove (for fixed correlation length) that, as h 0 ? 0, positive definiteness is guaranteed when the random field is sampled on a cube of size order (1 + ? 1/ 2 log h - 0 1 ) times larger than the size of the physical domain. (Here h 0 is the mesh spacing of the regular grid and ? the Mat{\'e}rn smoothness parameter.) We show that the sampling cube can become smaller as the correlation length decreases when h 0 and ? are fixed. Our results are confirmed by numerical experiments. We prove several results about the decay of the eigenvalues of the circulant matrix. These lead to the conjecture, verified by numerical experiment, that they decay with the same rate as the Karhunen–Lo{\`e}ve eigenvalues of the covariance operator. The method analyzed here complements the numerical experiments for uncertainty quantification in porous media problems in an earlier paper by the same authors in J. Comput. Phys., 230 (2011), pp. 3668–3694.",
keywords = "Analysis, Circulant embedding, Fast Fourier transform, Gaussian random fields, Mat{\'e}rn covariance, Statistical homogeneity",
author = "Graham, {Ivan G.} and Kuo, {Frances Y.} and Dirk Nuyens and Robert Scheichl and Sloan, {Ian H.}",
year = "2018",
doi = "10.1137/17M1149730",
language = "English",
volume = "56",
pages = "1871--1895",
journal = "SIAM Journal on Numerical Analysis (SINUM)",
issn = "0036-1429",
publisher = "SIAM",
number = "3",

}

TY - JOUR

T1 - Analysis of circulant embedding methods for sampling stationary random fields

AU - Graham, Ivan G.

AU - Kuo, Frances Y.

AU - Nuyens, Dirk

AU - Scheichl, Robert

AU - Sloan, Ian H.

PY - 2018

Y1 - 2018

N2 - A standard problem in uncertainty quantification and in computational statistics is the sampling of stationary Gaussian random fields with given covariance in a d-dimensional (physical) domain. In many applications it is sufficient to perform the sampling on a regular grid on a cube enclosing the physical domain, in which case the corresponding covariance matrix is nested block Toeplitz. After extension to a nested block circulant matrix, this can be diagonalized by FFT—the “circulant embedding method.” Provided the circulant matrix is positive definite, this provides a finite expansion of the field in terms of a deterministic basis, with coefficients given by i.i.d. standard normals. In this paper we prove, under mild conditions, that the positive definiteness of the circulant matrix is always guaranteed, provided the enclosing cube is sufficiently large. We examine in detail the case of the Matérn covariance, and prove (for fixed correlation length) that, as h 0 ? 0, positive definiteness is guaranteed when the random field is sampled on a cube of size order (1 + ? 1/ 2 log h - 0 1 ) times larger than the size of the physical domain. (Here h 0 is the mesh spacing of the regular grid and ? the Matérn smoothness parameter.) We show that the sampling cube can become smaller as the correlation length decreases when h 0 and ? are fixed. Our results are confirmed by numerical experiments. We prove several results about the decay of the eigenvalues of the circulant matrix. These lead to the conjecture, verified by numerical experiment, that they decay with the same rate as the Karhunen–Loève eigenvalues of the covariance operator. The method analyzed here complements the numerical experiments for uncertainty quantification in porous media problems in an earlier paper by the same authors in J. Comput. Phys., 230 (2011), pp. 3668–3694.

AB - A standard problem in uncertainty quantification and in computational statistics is the sampling of stationary Gaussian random fields with given covariance in a d-dimensional (physical) domain. In many applications it is sufficient to perform the sampling on a regular grid on a cube enclosing the physical domain, in which case the corresponding covariance matrix is nested block Toeplitz. After extension to a nested block circulant matrix, this can be diagonalized by FFT—the “circulant embedding method.” Provided the circulant matrix is positive definite, this provides a finite expansion of the field in terms of a deterministic basis, with coefficients given by i.i.d. standard normals. In this paper we prove, under mild conditions, that the positive definiteness of the circulant matrix is always guaranteed, provided the enclosing cube is sufficiently large. We examine in detail the case of the Matérn covariance, and prove (for fixed correlation length) that, as h 0 ? 0, positive definiteness is guaranteed when the random field is sampled on a cube of size order (1 + ? 1/ 2 log h - 0 1 ) times larger than the size of the physical domain. (Here h 0 is the mesh spacing of the regular grid and ? the Matérn smoothness parameter.) We show that the sampling cube can become smaller as the correlation length decreases when h 0 and ? are fixed. Our results are confirmed by numerical experiments. We prove several results about the decay of the eigenvalues of the circulant matrix. These lead to the conjecture, verified by numerical experiment, that they decay with the same rate as the Karhunen–Loève eigenvalues of the covariance operator. The method analyzed here complements the numerical experiments for uncertainty quantification in porous media problems in an earlier paper by the same authors in J. Comput. Phys., 230 (2011), pp. 3668–3694.

KW - Analysis

KW - Circulant embedding

KW - Fast Fourier transform

KW - Gaussian random fields

KW - Matérn covariance

KW - Statistical homogeneity

UR - http://www.scopus.com/inward/record.url?scp=85049424743&partnerID=8YFLogxK

U2 - 10.1137/17M1149730

DO - 10.1137/17M1149730

M3 - Article

VL - 56

SP - 1871

EP - 1895

JO - SIAM Journal on Numerical Analysis (SINUM)

JF - SIAM Journal on Numerical Analysis (SINUM)

SN - 0036-1429

IS - 3

ER -