2
$\begingroup$

Say I have a function, $C=C\left(x\right)$, whose fourier transform is denoted by $c=c\left(k\right)$, i.e. $C\left(x\right)=\sum_{k=-\infty}^{\infty}c\left(k\right)\chi\left(x\right)$, where $\chi\left(x\right)$ is some complex valued basis function.

I know that the autocorrelation is given by $M\left(\Delta x\right)=\sum_{k=-\infty}^{\infty}m\left(k\right)\chi\left(\Delta x\right)$, where $\Delta x = x_2-x_1$ and by the convolution theorem I know that $m\left(k\right)=\left(c\left(k\right)\right)^*c\left(k\right)$. This means that knowing the coefficients of the autocorrelation immediately gives me the squared magnitude of the original coefficients. This implies that any two functions $C'\left(x\right)=C\left(x-x'\right)$, that differ only by a translation, will possess the same autocorrelation, $M\left(\Delta x\right)$, and so if I am trying to obtain the $c\left(k\right)$ from the $m\left(k\right)$, then I can choose an arbitrary phase for the $c\left(k\right)$. However, I don't think I can choose the phase of $c\left(k\right)$ independently for each $k$, it seems like there needs to be some way to consistently choose the phase for all $k$ (which corresponds to specifying a translation for $C\left(x\right)$).

My question is: How do I choose a consistent phase for each of the coefficients for the original function, i.e. for all $k$?

| improve this question | | | | |
$\endgroup$
  • $\begingroup$ Your question is basically unanswerable. Barring possible conjugate symmetry constraints that $c(\cdot)$ must satisfy if $C(\cdot)$ is real-valued, all possible choices for $\theta_k$ in $\sqrt{|m(k)|}e^{j\theta_k}$ are equally valid. $\endgroup$ – Dilip Sarwate Sep 12 '13 at 22:44
  • $\begingroup$ There are in fact such symmetry constraints. $C\left(x\right)$ is real valued, and the reality constraint leads to the following constraint on the coefficients: $$c\left(-k\right)=c\left(k\right)^*$$. Does that help? $\endgroup$ – okj Sep 13 '13 at 13:26
  • $\begingroup$ No, it does not help since all that happens is that you get to choose the phases $\theta_k$ for $1 \leq k \leq N/2$ and the rest are those that you get via the conjugacy constraints. $\endgroup$ – Dilip Sarwate Sep 13 '13 at 14:05
  • $\begingroup$ So there is no intrinsic relationship between the $\theta_k$ for different values of $k$? I realize that you can choose any "global" phase, since the autocorrelation is shift-invariant, but my question is, if I specify $\theta_1$ for instance, how do I choose $\theta_2$, $\theta_3$,... etc. in a consistent way? It sounds to me like you're saying I can choose an arbitrary phase independently for all $k$, am I understanding what you're saying correctly? $\endgroup$ – okj Sep 13 '13 at 14:31
  • 2
    $\begingroup$ Many totally different sequences can have the same autocorrelation function. Yes, C and a delayed version of C will have the same autocorrelation, but so will C reversed in time. You can assign phases arbitrarily to the square roots of $|m(k)|$ and get a sequence with autocorrelation $m$. There is no way of getting $C$ back if all you have is $m$; there are infinitely many possible sequences that all have autocorrelation $m$. $\endgroup$ – Dilip Sarwate Sep 13 '13 at 17:05
4
$\begingroup$

For a real-valued signal $C$, the autocorrelation function $M$ is a real-valued even function and the power spectral density $m$ (Fourier transform of $M$) is a real-valued nonnegative even function. Now, $m(k) = c(k)c^*(k)$ where $c$ is the Fourier transform of $C$, as you correctly assert, but given only $m$ and no other information about $c$ (or $C$), it is not possible to determine $c$ at all. Note that $m(k)$ also equals $[c(k)e^{j\theta_k}][c(k)e^{j\theta_k}]^* = c(k)c^*(k) e^{j\theta_k}e^{-j\theta_k}$ for arbitrary choice of $\theta_k$, and the inverse Fourier transform of $c(k)e^{j\theta_k}$ is also a real-valued signal if we are careful to preserve conjugate symmetry so that we choose $\theta_{-k}$ as $-\theta_k$. In other words, there are infinitely many quite different signals that share the same autocorrelation function, and it is not the case that only $C$ and its time-delayed versions have autocorrelation function $M$. As an example, all PN signals, that is, pulse trains generated from a maximal-length linear feedback shift register (LFSR), have an inverted thumbtack autocorrelation, and the distinct PN signals (from different LFSRs) are even two-level signals, a property not shared by all of the infinitely many real signals that have inverted thumbtack autocorrelation.

| improve this answer | | | | |
$\endgroup$
1
$\begingroup$

This is impossible in general as stated in the accepted answer.

The conditions under which it becomes possible to reconstruct the original signal given its autocorrelation need not be very restrictive however. If the signal that is to be reconstructed is sparse in some basis so that the constraint-ratio is larger than one certain phase retrieval algorithms can be employed to reconstruct the signal except for certain symmetries (shift, inversion).

In the simplest case assume the signal has extent a which is less than 1/2 the extent of the autocorrellation function in each direction. The simplest reconstruction algorithm is an iterative projection between the Fourier amplitude constraint and the known extent. This approach is known as error reduction. Starting from random phases and the amplitudes given by the Fourier transform of the autocorrelation signal, this signal is inversely Fourier-transformed. Then everything outside the known extent of the signal, the support, is imposed, everything outside is set to zero. This approximation is then Fourier-transformed and the amplitudes of the signal are set to the known amplitudes of the autocorrelation signal. This algorithm will eventually converge and produce an estimate of the signal with some probability greater than 0 , so usually it is run several times to generate a set of possible solutions from which the best one is chosen.

import numpy as np
import matplotlib
import matplotlib.pyplot as plt

n    = 256
mask = np.arange(n)<16
orig = np.random.rand()*mask
data = abs(np.fft.fft(orig))
recon= np.random.rand(n)
for i in range(4096):
  recon =np.fft.fft(b)
  recon =np.where(abs(recon)<1e-60,1e-60,recon)
  recon*=data/abs(recon)
  recon =mask*np.fft.ifft(recon)
plt.plot(orig)
plt.plot(recon)
plt.show()
| improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.