An converse problem to covariance estimation. Related: phase retrieval. Gaussian process regression.
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?)
- 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