Generation of variable with given auto-correlation function

How can I generate realizations of random complex variable $x(t)$ with a given autocorrelation function $C(s)$, defined by

$$C(s) = \langle x(s) x(0) \rangle$$

and obeying the condition $C(-s) = C^*(s)$?

Any link related to similar random variable generation would be great.

You haven't specified the distribution of $x(t)$. I'll assume that you want to use a complex normal distribution, since that choice makes it reasonably easy to solve the problem and because this assumption is quite common in signal processing. I'll also discretize the problem so that you're generating a vector $X$ of $N$ entries with a specified complex normal distribution (your computer doesn't have enough storage for an infinite number of values.)

See the Wikipedia entry

http://en.wikipedia.org/wiki/Complex_normal_distribution

The complex normal distribution is characterized by its mean $\mu$, covariance matrix $\Gamma$, and relation $C$, where

$\mu=E[X]$

$\Gamma=E[(X-\mu)(X-\mu)^{H}]$

and

$C=E[(X-\mu)(X-\mu)^{T}]$

Note that $\Gamma$ is Hermitian and must be positive semidefinite, while $C$ is symmetric. There are further restrictions on $\Gamma$ and $C$ that ensure that some of the calculations below work out.

It is also common to have $C=0$. In this case we have a "circularly symmetric" distribution.

Write $X$ as

$X=\mu + U+ iV$

where $\mu=E[X]$ and where $U$ and $V$ are jointly distributed real multivariate normal random vectors with mean 0 and covariance

$\mbox{Cov}\left(\left[ \begin{array}{c} U \\ V \end{array} \right]\right)=\Sigma=\left[ \begin{array}{cc} \Sigma_{UU} & \Sigma_{UV} \\ \Sigma_{VU} & \Sigma_{VV} \end{array} \right]$

where

$\Sigma_{UU}=Re(\Gamma+C)/2$

$\Sigma_{UV}=Im(-\Gamma+C)/2$

$\Sigma_{VU}=Im(\Gamma+C)/2$

$\Sigma_{VV}=Re(\Gamma-C)/2$

Now, we've reduced your original problem to the problem of generating real multivariate normal vectors of length $2N$, with mean 0 and covariance $\Sigma$.

There are many techniques for generating such real multivariate normal random numbers. These are discussed in many textbooks on Monte Carlo simulation.

One very simple technique that works well as long as $N$ is reasonably small is to compute the Cholesky factorization of $\Sigma$,

$\Sigma=R^{T}R$.

Then generate a $N(0,I)$ random vector $Z$, and let $W=R^{T}Z$. $W$ will also be multivariate normal with mean 0. By the formula for the covariance of a matrix times a random vector, we get that

$\mbox{Cov}(W)=R^{T}\mbox{Cov}(Z)R=R^{T}IR=\Sigma$.

Thus $W$ has the desired multivariate normal distribution, and we can construct $X$ as $X=\mu+W_{U}+iW_{V}$.

The big problem with this technique is that $N$ gets large, it may not be possible to store the $2N$ by $2N$ matrix $\Sigma$ or its Cholesky factor.

Since your autocovariance matrices have Toeplitz structure, it turns out that there are specialized spectral techniques that can be used to reduce the required storage to $O(N)$ rather than $O(N^2)$. Spectral methods for generation of multivariate normals with specified stationary autocorrelation are discussed in many textbooks on geostatistics.

• Very informative answer! Something that would help make it better might be giving a pointer to an specific technique that allows one to go from the function C in the question, to the parameters for generating X. – Abel Molina Oct 12 '13 at 19:34
• You want $\Gamma_{n+s,n}=E[x(n+s)x(n)]=C(s)$ for $n=1, 2, ...$ and $s=0, \pm 1, \pm 2, ...$. The entries of your $\Gamma$ matrix will be constant along diagonals. – Brian Borchers Oct 13 '13 at 1:34
• Ah interesting, definitely gives some insight as well into what is going on in the discretization step. – Abel Molina Oct 13 '13 at 7:54