fft - 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?

---

Answer

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.