# Auto-correlation function, an inverse problem

$x[n]$ is a complex function $n=0,1,2,\cdots,L-1$

we assume $x[n]$ is periodic in its index: $x[n+L]=x[n]$

Its auto-correlation function $C[n]$ is uniquely defined as: $$C[n]=\sum_{i=0}^{L-1} x[i+n]x^*[i]$$ $C[n]$ also has the periodic property: $$C[n+L]=C[n]\tag{1}$$

And ''conjugate-symmetry'' property: $C[-n]=C^*[n] \tag{2}$

### Now my question is:

For given $C[n]$, which satisfies property (1) and (2):

Can we find the corresponding $x[n]$ ?

If yes, is it unique? and what is the method to find $x[n]$?

If no, what other constraint properties should we add to $C[n]$, in order to make it yes?

• By the way, if $L$ is even, $(2) \wedge (1)$ implies that $C[-\frac L2]=C[\frac L2] = C[\frac z2 L] \in \mathbb R$ for all $z\in \mathbb Z$. That has a consequence $x$! Namely, every $x[i+\frac L2]= x^*[i]$. – Marcus Müller Jun 13 '18 at 21:03
• Hi: don't know about the complex case but, in statistics, if the covariance matrix is symmetric and positive definite, it is possible. see theorem 7.5 of this link for the details. I don't know if or how that would translate to the complex case ? fepress.org/wp-content/uploads/2014/06/…. – mark leeds Jun 13 '18 at 21:13
• also, I'm not sure if it helps or hurts but the periodicity that you describe is not necessary in the proof at the link because the concept of periodicity is already kind of embedded in the covariance matrix so it's not really dealt with in statistics ( atleast as far as my experience goes. ). – mark leeds Jun 13 '18 at 21:20
• matrix seems to be on the right track, but I don't understand what's the relation between covariance matrix and auto-correlation function here. What are $x[n]$ and $C[n]$ in the language of matrix? – wwwjjj Jun 13 '18 at 21:38
• In the convariance matrix theory, we have random variables $X[n]$, we can add a second dimension $t$ meaning the random time series, $X[n,t]$ the summation is over $t$ instead of the periodic $n$. I believe it must have some interesting relations with the non-random problem in my case. – wwwjjj Jun 13 '18 at 21:49

Let's look at the case $x[n] \in \mathbb{R}$, where $x[n]$ is real.

Autocorrelation is basically convolution of the signal with it's time inverse. This can be easily expressed in the frequency domain.

$$\mathscr{F}\Big\{ r_{xx}[n] \Big\} = \mathscr{F}\Big\{ x[n] \Big\} \cdot \mathscr{F}\Big\{ x[-n] \Big\}$$

$$R_{xx}(\omega) = X(\omega)\cdot X^*(\omega) = \Big| X(\omega) \Big|^2$$

So it's easy to see that the Fourier Transform of the auto correlation is simply the magnitude squared of the Fourier Transform of the input signal. That's sometimes referred to as the Power Spectrum.

It's also easy to see that information gets lost in the process. There are $N$ unique values going in but because of the symmetry properties of the auto correlation there are only $\frac{N}{2}$ unique (independent) values coming out. Looking in the frequency domain, we can see that the phase is lost.

If yes, is it unique? and what is the method to find $x[n]$?

No, it's not unique

Can we find the corresponding $x[n]$ ?

There is an infinite number of $x[n]$.

1. Take the Fourier Transform of the autocorrelation
2. Take the square root
3. Add an aribtiraty (but odd-symmetric) phase function
4. Do an inverse Fourier Transform

Any signal derived this way will have the same original auto correlation function.

if no, what other constraint properties should we add to $C[n]$, in order to make it yes?

You can't make it a yes, since it's not unique. No matter what auto correlation you choose, there will be infinite $x[n]$ that will have it as an autocorrelation.

• I’m not sure but the Weiner Filter might be a unique spectral factorization – user28715 Jun 14 '18 at 1:31
• sorry Hil, but i can't resist wallowing in a little bit of OCD. – robert bristow-johnson Jun 14 '18 at 1:53
• actually Hilmar, if there are $N$ unique and non-zero values going into the autocorrelation, and it's linear correlation so it's just like convolving $x[n]$ with a time-reversed copy of the same: \begin{align} r_{xx}[n] &= x[n] \circledast x[-n] \\ &= \sum_i x[i]x[i+n] \\ \end{align} then $N$ values go in, $2N-1$ values come out, but there is symmetry and $N-1$ of the values of the $2N-1$ are redundant. that still leaves $N$ values. but i agree (from the frequency-domain argument) that the mapping of $x[n]$ to $r_{xx}[n]$ is not one-to-one. – robert bristow-johnson Jun 14 '18 at 1:59
• can someone explain why we can create the unique x in the time domain ( see link in my comment earlier ) ? does it have something to do with the periodicity requirement ? – mark leeds Jun 14 '18 at 6:24
• @markleeds : by "not unique" I mean the following: all signals that have the same power spectrum have the same auto correlation. Very different signals can have the same power spectrum. Example: A delta impulse and white noise have the same auto correlation. It's not just a bias. Another Example: the impulse response of every all pass filter has the same auto correlation, there many, many different allpass filters but they all have the same auto correlation – Hilmar Jun 14 '18 at 11:25

There is in general, as @Hilmar's answer points out, no unique solution to the question of a sequence that has the given perodic autocorrelation function. In the simplest case, that a shifted version $y$ of any sequence $x$ (e.g. $y[n] = x[n-3]$ for all $n$) has the same autocorrelation function as $x$. Similarly, $y[n] = x[-n]$ for all $n$ has the same autocorrelation function as $x$. If you feel that such $y$'s are really no different from $x$, then consider that all binary PN sequences of period $L = 2^m-1$ have the same periodic autocorrelation function $$C[n] = \begin{cases}L, & n \equiv 0\bmod L,\\-1,& \text{otherwise,} \end{cases}$$ and the PN sequences are very distinguishable from one another.