
Software & Hardware
Software
CoRK: Optimal Phase Retrieval from 1D Fourier Measurements
K. Huang, Y. C. Eldar and N. D. Sidiropoulos
Introduction
We consider phase retrieval from the magnitude of 1D oversampled Fourier measurements, a classical problem that has challenged researchers in various fields of science and engineering.
We show that an optimal vector in a leastsquares sense can be found by solving a convex problem, thus establishing a hidden convexity in Fourier phase retrieval. We then show that the
standard semidefinite relaxation approach yields the optimal cost function value (albeit not necessarily an optimal solution). A method is then derived to retrieve an optimal minimum phase
solution in polynomial time. Using these results, a new measuring technique is proposed which guarantees uniqueness of the solution, along with an efficient algorithm that can solve largescale
Fourier phase retrieval problems with uniqueness and optimality guarantees. The proposed method is termed autocorrelation retrieval – Kolmogorov (CoRK).
Main Idea
We start with the leastsquares formulation for 1D Fourier phase retrieval
where F_{M} denotes first N columns of the Mpoint DFT matrix. Due to the special structure of the DFT matrix, we show that this seemingly nonconvex problem is exactly equivalent to the following convex problem
where F_{L} denotes first N columns of the Lpoint DFT matrix with a sufficiently large L. The constraint ensures that r is an autocorrelation sequence, which we assumed to be the autocorrelation of x.
To retrieve a solution x from r, we can simply invoke spectral factorization, which is a relatively wellstudied subject, and we do it via Kolmogorov’s method.
Given the Fourier intensity of a signal s, F_{M}s^{2}, there are many alternative solutions of s that gives the same Fourier intensity, besides a global phase shift, spatial shift, and conjugate reversal.
The solution given by spectral factorization has the property of minimum phase, which is not a natural assumption to make for the signals that we want to estimate.
Our idea then is to construct a minimum phase signal before measuring its Fourier intensities, so that it can be uniquely identified via 1D Fourier phase retrieval.
The procedure is very simple: For an arbitrary complex signal s, the augmented signal [δ; s] is minimum phase if δ>s_{1}.
Summary of the Method
 Construct a minimum phase signal [δ; s] and then measure its Fourier intensity.
 Apply CoRK as follows:
 Solve the convex quadratic programming with respect to r, the autocorrelation of the signal, using ADMM;
 Extract the minimum phase solution using Kolmogorov’s method.
 Obtain an estimate by deleting the first element of the solution.
CoRK only does the second step, i.e., solves the problem optimally and produces a minimum phase solution. However, to retrieval the signal accurately, it is recommended to perform the first and third steps.
An Illustrative Example
In each MonteCarlo trial, we first set N as a random integer between [1,1024], and then choose M as the smallest power of 2 that is larger than 4N.
A random signal is then generated with elements drawn from i.i.d. .
Two kinds of measurements are collected for performance comparison: directly measure , and construct a minimum phase
signal s_{min} with δ=3N then measure . We compare CoRK with the classical Fienup’s algorithm,
possibly also followed by spectral factorization if we know the measured signal is minimum phase. The reconstruction error (after resolving global phase ambiguity) and time consumed are shown in the following figures.
References
Software Download
The simulator is freely available for download and manipulation for academic use only, under the GNU license.
Installation:
1. Unzip.
2. Follow the instructions in the ReadMe.txt

