Auto-correlation function, an inverse problem

Question

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

$\qquad $ if unique, what is the method to find $x[n]$?

$\qquad $ if not unique, what is the class of those $C[n] \rightarrow \{x[n]\}$

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

---

Answer 1

my guess

No, we can't find $x[n]$ from general $C[n]$

In order to make it yes, we need the discrete Fourier transform of $C[n]$ to be semi-positive defined.

$$I[\omega] \geqslant 0 \tag{3}\\ \text{where} \qquad \omega=0,1,2,\cdots,L-1 \\ and \qquad I[\omega]=\text{DFT}[C[n]]:=\sum_{n=0}^{L-1} C[n] e^{\frac{2\pi i}{L}\omega n} $$ By the way, $I(\omega)$ is real as the result of "conjugate-symmetric" property of $C[n]$

(3) is extra condition to make the $x[n]$ exist for given $C[n]$

---

with constraint (1),(2),(3) together. The answer is yes.

But the solution $x[n]$ are not unique.

They are not unique up to $L$ phases factors: $\theta[\omega] \quad \omega =0,1,2,\cdots,L-1$ $$ \tilde{x}[\omega]=\text{DFT}[x[n]]= |\tilde{x}[\omega]| e^{i\theta[\omega]} $$

$$ I[\omega]= |\tilde{x}[\omega]|^2 $$

$\tilde{x}[\omega]$ is the Fourier transform of $x[n]$, knowing $\tilde{x}[\omega]$ then we know $x[n]$

however, when we recover $\tilde{x}[\omega]$ from $I[\omega]$, the phase information $\theta[\omega]$ is completely missing. which makes $x[n]$ not unique.

---

In sum:

$C[n] \xrightarrow{DFT} I[\omega]$

If $I[\omega]$ is not semi-positive defined, then there is no solution for $x[n]$

If $I[\omega]$ is semi-positive defined, then there are solutions of $x[n]$, and they are not unique, up to $L$ phase factors.

$\tilde{x}[\omega]$ is the discrete Fourier transform (DFT) of $x[n]$. DFT is a one-to-one mapping.

$ I[\omega]= |\tilde{x}[\omega]|^2 $

and then $\tilde{x}[\omega] \xrightarrow{\text{inverse} DFT} x[n]$

since $\tilde{x}[\omega]$ is not unique, up to phase factor $|\tilde{x}[\omega]| e^{i\theta[\omega]}$, our $x[n]$ is also not unique.

---

Above is my guess.

Maybe there are already some textbook conclusions from some part of the math I don't know.

So, I hope to get some reference from this subject.

Answer 2

No, it is not unique. Consider the real sequences $x_0 = 0, x_1 =1$ and $y_0=1, y_1=0$ (in both cases $L=2$).

Then for $x$:

$$C_0 = x_0^2+x_1^2 =1,$$ $$C_1 = x_1x_0 + x_0x_1 = 0,$$ $$C_2 = x_0^2+x_1^2 = 1,$$ $$C_3 = x_1x_0 + x_0x_1 = 0...$$

While for $y$:

$$C_0 = y_0^2+y_1^2 =1,$$ $$C_1 = y_1y_0 + y_0y_1 = 0,$$ $$C_2 = y_0^2+y_1^2 = 1,$$ $$C_3 = y_1y_0 + y_0y_1 = 0...$$

The two sequences are shifted. In general, all shifted sequences share the same auto-correlation function. Thus, it is hard to add constraints to get a unique sequence.

Answer 3

Even up to shifts it is not unique at all. For example there is a whole collection of sequences called $m-$sequences (maximal length sequences) generated by binary linear shift registers corresponding to primitive polynomials. See the discussion on wikipedia.

There are $\phi(2^n-1)/n$ different primitive polynomials over the binary field of degree $n$ and each of these give rise to an $m-$sequence (and all its shifts). All these sequences have period $2^n-1$ and ideal autocorrelation $$C_t=-1+\delta(t)2^n$$ where $\delta(\cdot)$ is the Kronecker delta.

Corresponding complex valued sequences exist for non-binary fields, over $GF(p)$ they are sequences over complex roots of unity of order $p.$