I know there are lots of papers proposing algorithms for the problem of reconstructing a signal from modulus of its Fourier Transform (so-called Phase Retrieval Problem).

Also, recently it is studied for the case of sparse signals.

I want to know whether there is any paper or survey working on "reconstruction of signal from modulus of its DFT" or equivalently, reconstruction of signal from its circular auto-correlation ?

Or is there a way we can relate these two problems?

Edit: The prior information I have is :

  1. Time-domain signal is positive-valued.

  2. Time domain signal is zero in some points, i.e. signal has a support $P \subset \{0,1,2,\cdots,N-1\}$

  • $\begingroup$ I don't think you can construct any phase from the auto correlation since the autocorrelation spectrum is real and therefore all phase information is lost $\endgroup$ – Hilmar Aug 13 '13 at 11:48
  • $\begingroup$ @Hilmar I didn't get exactly what you mean. Generally, reconstructing a signal from its auto-correlation is possible through algorithms developed for phase retrieval such as : Phase retrieval algorithms: a comparison or a recent one : Recovery of Sparse 1-D Signals from the Magnitudes of their Fourier Transform and etc. But these are for modulus of Fourier Transform and I'm looking for the case when modulus of DFT is available. $\endgroup$ – Mahdi Khosravi Aug 13 '13 at 16:26

Problems such as those are closely related to "inverse problems", whereby one attempts to reconstruct a signal from an under-determined system of equations, (ill-posed problems) given some apriori information. As @Hilmar mentioned, you cannot reconstruct phase information from the absolute magnitude of a DFT, unless you have prior information that constrains you. For example, in the paper you mention, the author states:

Both the problem of phase retrieval from two intensity measurements (in electron microscopy or wave front sensing) and the problem of phase retrieval from a single intensity measurement plus a non-negativity constraint (in astronomy) are considered, with emphasis on the latter. It is shown [...]

The bold is mine. Even in the paper you allude to, there are constraints that then allow for a Maximum Likelihood framework to be applied, or one where sparsity is rewarded, etc.

Edit: The prior information I have is : Time-domain signal is positive-valued. Time domain signal is zero for in some points, i.e. signal has a support P⊂{0,1,2,⋯,N−1}

All your signal being positive valued is irrelevant to the phase information of the entire DFT spectrum. To see this, consider this following:

Note that having an all positive signal $x[n]$ means you are guaranteed to have a DC bias. This means that the first bin in the absolute magnitude of you DFT corresponding to $|X(0)|$ will be strictly positive. Let us split the input signal into its zero-mean partition, ($z[n]$) plus the mean value, $m$. Then:

$$x[n] = z[n] + m$$

The DFT of the result is, (exploiting the linearity property of the DFT):

$$ X[k] = \sum_{n=0}^{N-1} x[n] \ e^{-j \frac{ \Large 2 \pi n k }{N}} = \sum_{n=0}^{N-1} \Big[z[n] + m \Big] \ e^{-j \frac{ \Large 2 \pi n k }{N}} = \sum_{n=0}^{N-1} z[n] \ e^{-j \frac{ \Large 2 \pi n k }{N}} + \sum_{n=0}^{N-1} m \ e^{-j \frac{ \Large 2 \pi n k }{N}} $$

Recall that the DFT is nothing but a projection of your signal $x[n]$ onto an orthogonal basis set composed of complex exponentials. Save for the DC component at $k=0$, all the complex sinusoids have mean $0$. Thus the second term $\sum_{n=0}^{N-1} m \ e^{-j \frac{ \Large 2 \pi n k }{N}}$ completely vanishes for all $k \ne 0$. Hence, we can now write the DFT of $x[n]$ as being:

$$ X[k] = \left\{ \begin{array}{l l} \sum_{n=0}^{N-1} z[n] \ e^{-j \frac{ \Large 2 \pi n k }{N}} + mN = mN & ,k = 0\\ \sum_{n=0}^{N-1} z[n] \ e^{-j \frac{ \Large 2 \pi n k }{N}} & , k \ne 0 \end{array} \right. $$

This then shows that your signal always being positive is completely irrelevant to the phase signal spectrum.

Hence, this prior information ($x[n] \ge 0, n \in 0, 1, ... N-1$) is irrelevant, and no recovery is possible given $|X[k]|$, with only this constraint.

You are right in that these types of problems have some solutions to them, but it is also important for you to also remember that you have to define your constraints before you can solve for your unknown entities. That is, you have to give prior information that you can utilize.

As a simple example, given the absolute magnitude vector $|X(f)|$, there is an infinite number of possible solutions to what values $\angle X(f)$ can take on. However, if you "know" before hand that, say, all the imaginary co-efficients of $X(f) \in \mathfrak{C} $ are zero, then we can easily recover what the real co-efficients are up to a sign ambiguity.

The take home message however, is what prior information do you have, and how is it related to the DFT. Hope this helped.

  • $\begingroup$ I've written the available constraints in the EDIT part. Thanks for your answer $\endgroup$ – Mahdi Khosravi Aug 14 '13 at 5:47
  • $\begingroup$ @MahdiKhosravi Please see my edits. $\endgroup$ – Tarin Ziyaee Aug 14 '13 at 18:36
  • $\begingroup$ What about the sparsity of signal (support of $P$) ? $\endgroup$ – Mahdi Khosravi Aug 14 '13 at 19:03
  • $\begingroup$ @MahdiKhosravi I do not believe that will help you either. Sparse in time would mean broad in spectral energy, but it does not say anything about the phase. $\endgroup$ – Tarin Ziyaee Aug 14 '13 at 19:09
  • $\begingroup$ I've added a new constraint, do you think this would help? $\endgroup$ – Mahdi Khosravi Aug 14 '13 at 19:19

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.