An converse problem to covariance estimation. Related: phase retrieval. Gaussian process regression.

## TODO

Discuss in the context of

- deterministic covariance
- expected autocorrelation in covariance

## Simulating Gaussian RVs with the desired covariance structure

[Following the introduction in (DiNe93)]

Let's say we wish to generate a stationary Gaussian process on a points . .

*Stationary* in this context means that the covariance function
is translation-invariance and depend only on distance,
so that it may be given .
Without loss of generality,
we assume that and .

The problem then reduces to generating a vector where has entries

Note that if is an -dimensional normal random variable, and , then has the required distribution.

### The circulant embedding trick

But what if that's too slow? If we have additional structure, we can do better.

Suppose further that our points form a grid, ; specifically, equally-spaced-points on a line.

We know that has a Toeplitz structure. Moreover it is non-negative definite, with (Why?)

## Refs

- DiNe93: C. R. Dietrich, G. N. Newsam (1993) A fast and exact method for multidimensional gaussian stochastic simulations.
*Water Resources Research*, 29(8), 2861–2869. DOI - GKNS17a: Ivan G. Graham, Frances Y. Kuo, Dirk Nuyens, Rob Scheichl, Ian H. Sloan (2017a) Analysis of circulant embedding methods for sampling stationary random fields.
*ArXiv:1710.00751 [Math]*. - StSL17: Jonathan R. Stroud, Michael L. Stein, Shaun Lysen (2017) Bayesian and Maximum Likelihood Estimation for Gaussian Processes on an Incomplete Lattice.
*Journal of Computational and Graphical Statistics*, 26(1), 108–120. DOI - GuFu16: Joseph Guinness, 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. DOI - GKNS17b: Ivan G. Graham, Frances Y. Kuo, Dirk Nuyens, Rob Scheichl, Ian H. Sloan (2017b) Circulant embedding with QMC -- analysis for elliptic PDE with lognormal coefficients.
*ArXiv:1710.09254 [Math]*. - Whit53a: P. Whittle (1953a) Estimation and information in stationary time series.
*Arkiv För Matematik*, 2(5), 423–434. DOI - YeLi16: Ke Ye, Lek-Heng Lim (2016) Every Matrix is a Product of Toeplitz Matrices.
*Foundations of Computational Mathematics*, 16(3), 577–598. DOI - ElLa92: Robert L. Ellis, David C. Lay (1992) Factorization of finite rank Hankel and Toeplitz matrices.
*Linear Algebra and Its Applications*, 173, 19–38. DOI - HeRo11: Georg Heinig, Karla Rost (2011) Fast algorithms for Toeplitz and Hankel matrices.
*Linear Algebra and Its Applications*, 435(1), 1–59. DOI - Powe14: Catherine E. Powell (2014) Generating realisations of stationary gaussian random fields by circulant embedding.
*Matrix*, 2(2), 1. - DaBr13: Tilman M. Davies, David Bryant (2013) On Circulant Embedding for Gaussian Random Fields in R.
*Journal of Statistical Software*, 55(9). DOI - ChSi16: Krzysztof Choromanski, Vikas Sindhwani (2016) Recycling Randomness with Structure for Sublinear time Kernel Expansions.
*ArXiv:1605.09049 [Cs, Stat]*. - ChWo99: G. Chan, A. T. A. Wood (1999) Simulation of stationary Gaussian vector fields.
*Statistics and Computing*, 9(4), 265–268. DOI - Whit52: Peter Whittle (1952) Some results in time series analysis.
*Scandinavian Actuarial Journal*, 1952(1–2), 48–60. DOI - Whit53b: P. Whittle (1953b) The Analysis of Multiple Stationary Time Series.
*Journal of the Royal Statistical Society. Series B (Methodological)*, 15(1), 125–139. - Gray06: Robert M. Gray (2006) Toeplitz and Circulant Matrices: A Review.
*Foundations and Trends® in Communications and Information Theory*, 2(3), 155–239. DOI