Fourier Phase Retrieval:
Uniqueness and Algorithms
arXiv:1705.09590v3 [] 6 Nov 2017

Tamir Bendory∗1 , Robert Beinert†2 and Yonina C. Eldar‡3
1 The

Program in Applied and Computational Mathematics,
Princeton University, Princeton, NJ, USA
2 Institute of Mathematics and Scientific Computing, University of
Graz, Heinrichstraße 36, 8010 Graz, Austria
3 The Andrew and Erna Viterbi Faculty of Electrical Engineering,
Technion - Israel Institute of Technology, Haifa, Israel

Abstract
The problem of recovering a signal from its phaseless Fourier transform
measurements, called Fourier phase retrieval, arises in many applications in
engineering and science. Fourier phase retrieval poses fundamental theoretical and algorithmic challenges. In general, there is no unique mapping
between a one-dimensional signal and its Fourier magnitude and therefore
the problem is ill-posed. Additionally, while almost all multidimensional
signals are uniquely mapped to their Fourier magnitude, the performance
of existing algorithms is generally not well-understood. In this chapter we
survey methods to guarantee uniqueness in Fourier phase retrieval. We then
present different algorithmic approaches to retrieve the signal in practice.
We conclude by outlining some of the main open questions in this field.

∗ tamir.bendory@princeton.edu
† robert.beinert@uni-graz.at.

The Institute of Mathematics and Scientific Computing is a member of NAWI Graz (http://www.nawigraz.at). The author is supported by the Austrian Science
Fund (FWF) within the project P 28858.
‡ yonina@ee.technion.ac.il. The author is supported by the European Unions Horizon 2020
research and innovation program under grant agreement no. 646804-ERC-COG-BNYQ, and from
the Israel Science Foundation under Grant no. 335/14.

1

1

Introduction

The task of recovering a signal from its Fourier transform magnitude, called
Fourier phase retrieval, arises in many areas in engineering and science.
The problem has a rich history, tracing back to 1952 [110]. Important examples for Fourier phase retrieval naturally appear in many optical settings
since optical sensors, such as a charge-coupled device (CCD) and the human eye, are insensitive to phase information of the light wave. A typical example is coherent diffraction imaging (CDI) which is used in a variety of imaging techniques [24, 33, 34, 92, 105, 109]. In CDI, an object
is illuminated with a coherent electro-magnetic wave and the far-field intensity diffraction pattern is measured. This pattern is proportional to the
object’s Fourier transform and therefore the measured data is proportional
to its Fourier magnitude. Phase retrieval also played a key role in the development of the DNA double helix model [55]. This discovery awarded
Watson, Crick and Wilkins the Nobel prize in Physiology or Medicine in
1962 [1]. Additional examples for applications in which Fourier phase retrieval appear are X-ray crystallography, speech recognition, blind channel
estimation, astronomy, computational biology, alignment and blind deconvolution [10, 19, 54, 62, 100, 114, 125, 132, 137].
Fourier phase retrieval has been a long-standing problem since it raises
difficult challenges. In general, there is no unique mapping between a onedimensional signal and its Fourier magnitude and therefore the problem
is ill-posed. Additionally, while almost all multidimensional signals are
uniquely mapped to their Fourier magnitude, the performance and stability of existing algorithms is generally not well-understood. In particular,
it is not clear when given methods recover the true underlying signal. To
simplify the mathematical analysis, in recent years attention has been devoted to a family of related problems, frequently called generalized phase
retrieval. This refers to the setting in which the measurements are the phaseless inner products of the signal with known vectors. Particularly, the majority of works studied inner products with random vectors. Based on probabilistic considerations, a variety of convex and non-convex algorithms were
suggested, equipped with stability guarantees from near-optimal number of
measurements; see [3, 5, 30, 37, 44, 58, 124, 131, 133] to name a few works
along these lines.
Here, we focus on the original Fourier phase retrieval problem and study
it in detail. We begin by considering the ambiguities of Fourier phase retrieval [12, 15, 16]. We show that while in general a one-dimensional signal cannot be determined from its Fourier magnitude, there are several exceptional cases, such as minimum phase [66] and sparse signals [73, 101].
For general signals, one can guarantee uniqueness by taking multiple measurements, each one with a different mask. This setup is called masked

2

phase retrieval [30, 69] and has several interesting special cases, such as the
short-time Fourier transform (STFT) phase retrieval [22, 45, 71] and vectorial phase retrieval [82, 102, 103, 104]. For all aforementioned setups, we
present algorithms and discuss their properties. We also study the closely–
related Frequency-Resolved Optical Gating (FROG) methods [23] and multidimensional Fourier phase retrieval [78].
The outline of this chapter is as follows. In Section 2 we formulate the
Fourier phase retrieval problem. We also introduce several of its variants,
such as masked Fourier phase retrieval and STFT phase retrieval. In Section
3 we discuss the fundamental problem of uniqueness. Namely, conditions
under which there is a unique mapping between a signal and its phaseless
measurements. Section 4 is devoted to different algorithmic approaches to
recover a signal from its phaseless measurements. Section 5 concludes the
chapter and outlines some open questions. We hope that highlighting the
gaps in the theory of phase retrieval will motivate more research on these
issues.

2

Problem formulation

In this section, we formulate the Fourier phase retrieval problem and introduce notation.
Let x ∈ CN be the underlying signal we wish to recover. In Fourier phase
retrieval the measurements are given by
N−1

y[k] =

∑ x[n]e

2
−2π jkn/Ñ

,

k = 0, . . . , K − 1.

(2.1)

n=0

Unless otherwise mentioned, we consider the over-sampled Fourier transform, i.e., Ñ = K = 2N − 1, since in this case the acquired data is equivalent
to the auto-correlation of x as explained in Section 3.1. We refer to this case
as the classical phase retrieval problem. As will be discussed in the next
section, in general the classical phase retrieval problem is ill-posed. Nevertheless, some special structures may impose uniqueness. Two important
examples are sparse signals obeying a non-periodic support [73, 101] and
minimum phase signals [66]; see Section 3.2.
For general signals, a popular method to guarantee a unique mapping
between the signal and its phaseless Fourier measurements is by utilizing
several masks to introduce redundancy in the acquired data. In this case, the
measurements are given by
N−1

y[m, k] =

∑ x[n]dm [n]e

2
−2π jkn/Ñ

,

k = 0, . . . , K − 1,

m = 0, . . . , M − 1,

n=0

(2.2)

3

Figure 2.1: An illustration of a typical masked phase retrieval setup (courtesy
of [30]).
where dm are M known masks. In matrix notation, this model can be written
as
y[m, k] = | fk∗ Dm x|2 ,

k = 0, . . . , K − 1,

m = 0, . . . , M − 1,

(2.3)

where fk∗ is the kth row of the DFT matrix F ∈ CK×N and Dm ∈ CN×N is a
diagonal matrix that contains the entries of the mth mask. Classical phase
retrieval is a special case in which M = 1 and D0 = IN is the identity matrix.
There are several experimental techniques to generate masked Fourier
measurements in optical setups [30]. One method is to insert a mask or a
phase plate after the object [84]. Another possibility is to modulate the illuminating beam by an optical grating [85]. A third alternative is oblique illumination by illuminating beams hitting the object at specified angles [49].
An illustration of a masked phase retrieval setup is shown in Fig. 2.1.
An interesting special case of masked phase retrieval is signal reconstruction from phaseless STFT measurements. Here, all masks are translations of a reference mask, i.e., dm [n] = d[mL −n], where L is a parameter that
determines the overlapping factor between adjacent windows. Explicitly, the
STFT phase retrieval problem takes on the form
2

N−1

y[m, k] =

∑ x[n]d[mL − n]e

−2π jkn/Ñ

,

n=0

k = 0, . . . , K − 1,

(2.4)

m = 0, . . . , dN/Le − 1.

The reference mask d is referred to as STFT window. We denote the length
of the STFT window by W , namely, d[n] = 0 for n = W, . . . , N − 1 for some
W ≤ N.

4

Figure 2.2: An illustration of a conventional ptychography setup (courtesy
of [118]).
The problem of recovering a signal from its STFT magnitude arises in
several applications in optics and speech processing. Particularly, it serves
as the model of a popular variant of an ultra-short laser pulse measurement
technique called Frequency-Resolved Optical Gating (FROG) which is introduced in Section 3.5 (the variant is referred to as X-FROG) [23, 127]. Another application is ptychography in which a moving probe (pinhole) is used
to sense multiple diffraction measurements [87, 90, 106]. An illustration of
a conventional ptychography setup is given in Fig. 2.2. A closely-related
problem is Fourier ptychography [137].
The next section is devoted to the question of uniqueness. Namely, under what conditions on the signal x and the masks dm there exists a unique
mapping between the signal and the phaseless measurements. In Section 4
we survey different algorithmic approaches to recover the underlying signal
x from the acquired data.

3

Uniqueness guarantees

The aim of this section is to survey several approaches to ensure uniqueness
of the discrete phase retrieval problem. We begin our study in Section 3.1 by
considering the ambiguities arising in classical phase retrieval and provide a
complete characterization of the solution set. Although the problem is highly
ambiguous in general, uniqueness can be ensured if additional information
about the signal is available. In Section 3.2, we first consider uniqueness
guarantees based on the knowledge of the absolute value or phase of some
signal entries. Next, we study sparse and minimum phase signals, which are
uniquely defined by their Fourier magnitude and can be recovered by stable
algorithms. In Sections 3.3 and 3.4 we show that for general signals, the
ambiguities may be avoided by measuring the Fourier magnitudes of the interaction of the true signal with multiple deterministic masks or with several
shifts of a fixed window. In Section 3.5 we study uniqueness guarantees for

5

the closely–related FROG methods. Finally, in Section 3.6 we survey the
multidimensional phase retrieval problems and their properties that differ
significantly from the one-dimensional setting.

3.1

Trivial and non-trivial ambiguities

Considering the measurement model (2.1) of the classical phase retrieval
problem, we immediately observe that the true signal x ∈ CN cannot be recovered uniquely. For instance, the rotation (multiplication with a unimodular factor), the translation, or the conjugate reflection do not modify the
Fourier magnitudes. Without further a priori constraints, the unknown signal
x is hence only determined up to these so-called trivial ambiguities, which
are of minor interest. Beside the trivial ambiguities, the classical phase retrieval problem usually has a series of further non-trivial solutions, which
can strongly differ from the true signal. For instance, the two non-trivially
different signals
√
√
and
x2 = ((1 − 3), 0, 1, 0, (1 + 3))T
x1 = (1, 0, −2, 0, −2)T
yield the same Fourier magnitudes y[k] in (2.1); see [114].
To characterize the occurring non-trivial ambiguities, one can exploit the
close relation between the given Fourier magnitudes y[k] with k = 0, . . . , 2N −
2 in (2.1) and the autocorrelation signal
N−1

a[n] =

n = −N + 1, . . . , N − 1,

∑ x[m] x[m + n],

m=0

with x[n] = 0 for n < 0 and n ≥ N, [15, 27]. For this purpose, we consider
N−1
the product of the polynomial X(z) = ∑n=0
x[n] zn and the reversed polynomial X̃(z) = zN−1 X(z−1 ), where X denotes the polynomial with conjugate
coefficients. Note that X(z−1 ) coincides with the usual z-transform of the
signal x ∈ CN . Assuming that x[0] 6= 0 and x[N − 1] 6= 0, we have
N−1

X(z) X̃(z) = zN−1

2N−2

N−1

∑ x[n] zn · ∑ x[m] z−m = ∑

n=0

a[n − N + 1] zn =: A(z),

n=0

m=0

where A(z) is the autocorrelation polynomial of degree 2N − 2.
Since the Fourier magnitude (2.1) can be written as



y[k] = e2π jk(N−1)/Ñ X e−2π jk/Ñ X̃ e−2π jk/Ñ = e2π j(N−1)/Ñ A e−2π jk/Ñ ,
the autocorrelation polynomial A(z) is completely determined by the 2N − 1
samples y[k]. The classical phase retrieval problem is thus equivalent to the
recovery of X(z) from
A(z) = X(z) X̃(z).

6

Comparing the roots of X(z) and X̃(z), we observe that the roots of the autocorrelation polynomial A(z) occur in reflected pairs (γ j , γ −1
j ) with respect
to the unit circle. The main problem in the recovery of X(z) is now to decide whether γ j or γ −1
j is a root of X(z). On the basis of this observation,
all ambiguities – trivial and non-trivial – are characterized in the following
way.
Theorem 3.1. [15] Let x ∈ CN be a complex-valued signal with x[0] 6= 0
and x[N − 1] 6= 0 and with the Fourier magnitudes y[k], k = 0, . . . , 2N − 2, in
0
n
0
N
(2.1). Then the polynomial X 0 (z) = ∑N−1
n=0 x [n] z of each signal x ∈ C with
0
y [k] = y[k] can be written as
s
X 0 (z) = e jα

N−1

N−1

|a[N − 1] ∏ |βi |−1 · ∏ (z − βi ),
i=1

i=1

where α ∈ [−π, π), and where βi is chosen from the reflected zero pairs
(γi , γ i−1 ) of the autocorrelation polynomial A(z). Moreover, up to 2N−2 of
these solutions may be non-trivially different.
Since the support length N of the true signal x is directly encoded in the
degree of the autocorrelation polynomial, all signals x0 with y0 [k] = y[k] in
Theorem 3.1 have the same length, and the trivial shift ambiguity does not
occur. The multiplication by e jα is related to the trivial rotation ambiguity.
The trivial conjugate reflection ambiguity is also covered by Theorem 3.1,
since this corresponds to the reflection of all zeros βi at the unit circle and
to an appropriate rotation of the whole signal. Hence, at least two of the
2N−1 possible zero sets {β1 , . . . , βN−1 } always correspond to the same nontrivial solution, which implies that the number of non-trivial solutions of the
classical phase retrieval problem is bounded by 2N−2 .
The actual number of non-trivial ambiguities for a specific phase retrieval problem, however, strongly depends on the zeros of the true solution.
If L denotes the number of zero pairs (γ` , γ `−1 ) of the autocorrelation polynomial A(z) not lying on the unit circle, and m` the multiplicities of these zeros,
then the different zero sets {β1 , . . . , βN−1 } in Theorem 3.1 can consist of s`
roots γ` and (m` − s` ) roots γ `−1 , where s` is an integer between 0 and m` .
Due to the trivial conjugation and reflection ambiguity, the corresponding
phase retrieval problem has exactly
&
'
1 L
∏(m` + 1)
2 `=1
non-trivial solutions [12, 51]. If, for instance, all zero pairs (γ` , γ `−1 ) are
unimodular, then the problem is even uniquely solvable.

7

3.2

Ensuring uniqueness in classical phase retrieval

To overcome the non-trivial ambiguities, and to ensure uniqueness in the
phase retrieval problem, one can rely on suitable a priori conditions or further information about the true signal. For instance, if the sought signal represents an intensity or a probability distribution, then it has to be real-valued
and non-negative. Unfortunately, this natural contraint does not guarantee
uniqueness [13]. More appropriate priors like minimum phase or sparsity
ensure uniqueness for almost every or, even, for every possible signal. Additional information about some entries of the true signal like the magnitude
or the phase also guarantee uniqueness in certain settings.

3.2.1

Information about some entries of the true signal

One approach to overcome the non-trivial ambiguities is to use additional
information about some entries of the otherwise unknown signal x. For
instance, in wave front sensing and laser optics [111], besides the Fourier
intensity, the absolute values |x[0]|, . . . , |x[N − 1]| of the sought signal x are
available. Interestingly, already one absolute value |x[N − 1 − `]| within the
support of the true signal x almost always ensures uniqueness.
Theorem 3.2. [16] Let ` be an arbitrary integer between 0 and N − 1. Then
almost every complex-valued signal x ∈ CN with support length N can be
uniquely recovered from y[k], k = 0, . . . , 2N − 2, in (2.1) and |x[N − 1 − `]|
up to rotations if ` 6= (N −1)/2. In the case ` = (N −1)/2, the reconstruction
is almost surely unique up to rotations and conjugate reflections.
The uniqueness guarantee in Theorem 3.2 cannot be improved by the
knowledge of further or, even, all absolute values |x[0]|, . . . , |x[N − 1]| of
the true signal. More precisely, one can explicitly construct signals that
are not uniquely defined by their Fourier magnitudes y[k] and all temporal
magnitudes |x[n]| for every possible signal length [16]. In order to recover a
signal from its Fourier magnitudes and all temporal magnitudes numerically,
several multi-level Gauss-Newton methods have been proposed in [79, 80,
111]. Under certain conditions, the convergence of these algorithms to the
true solution is guaranteed, and they allow signal reconstruction from noisefree as well as from noisy data.
The main idea behind Theorem 3.2 exploits |x[N − 1 − `]| to show that
the zero sets {β1 , . . . , βN−1 } of signals that cannot be recovered uniquely
(up to trivial ambiguities) form an algebraic variety of lesser dimension.
This approach can be transferred to further kinds of information about some
entries of x. For instance, the knowledge of at least two phases of the true
signal also guarantees uniqueness almost surely.
Theorem 3.3. [16] Let `1 and `2 be different integers in {0, . . . , N − 1}.
Then almost every complex-valued signal x ∈ CN with support length N can

8

be uniquely recovered from y[k], k = 0, . . . , 2N − 2, in (2.1), arg x[N − 1 − `1 ],
and arg x[N − 1 − `2 ] whenever `1 + `2 6= N − 1. In the case `1 + `2 = N − 1,
the recovery is only unique up to conjugate reflection except for `1 = 0 and
`2 = N − 1, where the set of non-trivial ambiguities is not reduced at all.
As a consequence of Theorems 3.2 and 3.3, the classical phase retrieval
problem is almost always uniquely solvable if at least one entry of the true
signal x is known. Unfortunately, there is no algorithm that knows how
to exploit the given entries to recover the complete signal in a stable and
efficient manner.
Corollary 3.4. Let ` be an arbitrary integer between 0 and N − 1. Then
almost every complex-valued signal x ∈ CN with support length N can be
uniquely recovered from y[k], k = 0, . . . , 2N − 2, in (2.1) and x[N − 1 − `] if
` 6= (N − 1)/2. In the case ` = (N − 1)/2, the reconstruction is almost surely
unique up to conjugate reflection.
Corollary 3.4 is a generalization of [136], where the recovery of realvalued signals x ∈ RN from their Fourier magnitude y[k] and one of their end
points x[0] or x[N − 1] is studied. In contrast to Theorems 3.2 and 3.3, the
classical phase retrieval problem becomes unique if enough entries of the
true signal are known beforehand.
Theorem 3.5. [15, 94] Each complex-valued signal x ∈ CN with signal
length N is uniquely determined by y[k], k = 0, . . . , 2N − 2, in (2.1) and the
dN/2e left end points x[0], . . . , x[dN/2e − 1].

3.2.2

Sparse signals

In the last section, the true signal x could be any arbitrary vector in CN .
In the following, we consider the classical phase retrieval problem under the
assumption that the unknown signal is sparse, namely, that only a small number of entries are non-zero. Sparse signals have been studied thoroughly in
the last two decades, see for instance [32, 41, 43]. Phase retrieval problems
of sparse signals arise in crystallography [76, 101] and astronomy [27, 101],
for example. In many cases, the signal is sparse under an unknown transform. In the context of phase retrieval, a recent paper suggests a new technique to learn, directly from the phaseless data, the sparsifying transformation and the sparse representation of the signals simultaneously [126].
The union of all k-sparse signals in CN , which have at most k non-zero
entries, is here denoted by SkN . Since SkN with k < N is a k-dimensional
submanifold of CN and hence itself a Lebesgue null set, Theorem 3.2 and
Corollary 3.4 cannot be employed to guarantee uniqueness of the sparse
phase retrieval problem. Further, if the k non-zero entries lie at equispaced positions within the true signal x, i.e., the support is of the form

9

{n0 + Lm : m = 0, . . . , k − 1} for some positive integers n0 and L, this specific
phase retrieval problem is equivalent to the recovery of a k-dimensional vector from its Fourier intensity [73]. Due to the non-trivial ambiguities, which
are characterized by Theorem 3.1, the assumed sparsity cannot always avoid
non-trivial ambiguities.
In general, the knowledge that the true signal is sparse has a beneficial
effect on the uniquness of phase retrieval. Under the restriction that the
unknown signal x belongs to the class TkN of all k-sparse signals in CN
without equispaced support, which is again a k-dimensional submanifold,
the uniqueness is ensured for almost all signals.
Theorem 3.6. [73] Almost all signals x ∈ TkN can be uniquely recovered
from their Fourier magnitudes y[k], k = 0, . . . , 2N −2, in (2.1) up to rotations.
Although Theorem 3.6 gives a theoretical uniqueness guarantee, it is
generally a non-trivial task to decide whether a sparse signal is uniquely
defined by its Fourier intensity. However, if the true signal does not possess
any collisions, uniqueness is always given [101]. In this context, a sparse
signal x has a collision if there exists four indices i1 , i2 , i3 , i4 within the
support of x so that i1 − i2 = i3 − i4 . A sparse signal without collisions is
called collision-free. For instance, the signal
x = (0, 0, 1, 0, −2, 0, 1, 0, 0, 3, 0, 0)T ∈ R12
is not collision-free since the index difference 6 − 4 = 2 is equal to 4 − 2 = 2.
Theorem 3.7. [101] Assume that the signal x ∈ SkN with k < N has no
collisions.
• If k 6= 6, then x can be uniquely recovered from y[k], k = 0, . . . , 2N − 2,
in (2.1) up to trivial ambiguities;
• If k = 6 and not all non-zero entries x[n] have the same value, then x
can be uniquely recovered from y[k], k = 0, . . . , 2N − 2, in (2.1) up to
trivial ambiguities;
• If k = 6 and all non-zero entries x[n] have the same value, then x can be
uniquely recovered from y[k], k = 0, . . . , 2N − 2, in (2.1) almost surely
up to trivial ambiguities.
The uniqueness guarantees in Theorem 3.7 remain valid for k-sparse
continuous-time signals, which are composed of k pulses at arbitrary positions. More precisely, the continuous-time signal f is here given by f (t) =
∑k−1
i=0 ci δ (t −ti ), where δ is the Dirac delta function, ci ∈ C and ti ∈ R. In this
setting, the uniqueness can be guaranteed by O(k2 ) samples of the Fourier
magnitude [17].
In Section 4.4, we discuss different algorithms to recover sparse signals
x ∈ CN , that work well in practice.

10

3.2.3

Minimum phase signals

Based on the observation that each non-trivial solution of the classical phase
retrieval problem is uniquely characterized by the zero set {β1 , . . . , βN−1 } in
Theorem 3.1, one of the simplest ideas to enforce uniqueness is to restrict
these zeros in an appropriate manner. Under the assumption that the true signal x is a minimum phase signal, which means that all zeros βi chosen from
the reflected zero pairs (γi , γ i−1 ) of the autocorrelation polynomial A(z) lie
inside the unit circle, the corresponding phase retrieval problem is uniquely
solvable [64, 66].
Although the minimum phase constraint guarantees uniqueness, the question arises how to ensure that an unknown signal is minimum phase. Fortunately, each complex-valued signal x may be augmented to a minimum
phase signal.
Theorem 3.8. [66] For every x ∈ CN , the augmented signal
xmin = (δ , x[0], . . . , x[N − 1])T ,
with |δ | ≥ kxk1 is a minimum phase signal.
Consequently, if the Fourier intensity of the augmented signal xmin is
available, then the true signal x can always be uniquely recovered up to trivial ambiguities. Moreover, the minimum phase solution x can be computed
(up to rotations) from the Fourier magnitude y as in (2.1) by a number of efficient algorithms [66]. Due to the trivial conjugate reflection ambiguity, this
approach can be applied to maximum phase signals whose zeros lie outside
the unit circle.
The minimum phase solution of a given phase retrieval problem may be
determined in a stable manner using an approach by Kolmogorov [66]. For
simplicity, we restrict ourselves to the real case x ∈ RN with x[N − 1] > 0.
The main idea is to determine the logarithm of the reversed polynomial
−n from the given data y[k]. Under the assumpX̃(z) = zN−1 ∑N−1
n=0 x[n] z
tion that all roots of x strictly lie inside the unit circle, the analytic function
log X̃(z) may be written as
∞

log X̃(z) =

∑ αn zn ,

(αn ∈ R)

n=0

where the unit circle |z| = 1 is contained in the region of convergence. Substituting z = e− jω with ω ∈ R, we have


ℜ log X̃(e− jω ) =

∞

∑ αn cos ωn and

n=0

∞


ℑ log X̃(e− jω ) = − ∑ αn sin ωn,
n=0

where ℜ[·] and ℑ[·] denote the real and imaginary parts, respectively.
Since


the real and imaginary part are a Hilbert transform pair, ℑ log X̃(e− jω ) is

11



completely defined by ℜ log X̃(e− jω ) . Because of the identity |X̃(e− jω )|2 =
|A(e− jω )|, the real part may be computed from the autocorrelation polynomial A(z) by


ℜ log X̃(e− jω ) = 12 log |A(e− jω )|.
Finally, the autocorrelation polynomial A(z) is completely determined by the
Fourier magnitudes y[k], k = 0, . . . , 2N −2, leading to the recovery of the true
minimum phase signal x. Based on this idea, one can construct numerical
algorithms that guarantee stable signal recovery under the presence of noise
[66].

3.3

Phase retrieval with deterministic masks

A further possibility to obtain additional information about the underlying
signal x is to measure its Fourier magnitude with respect to different masks
as described in (2.2) and (2.3). Assuming that the masks are constructed
randomly, one can show that the corresponding phase retrieval problem has
a unique solution up to rotations almost surely or, at least, with high probability. Depending on the random model, the number of employed masks
to recover an one-dimensional signal x ∈ CN varies form O(log N) over
O((log N)2 ) to O((log N)4 ), see [6], [61], and [29] respectively. Moreover,
in the multidimensional case, two independent masks are sufficient to guarantee uniqueness of almost every signal up to rotations [48]. As the following results show, in the deterministic setup, already a very small number of
specifically constructed masks ensure uniqueness for most signals.
Theorem 3.9. [69] Almost all complex-valued signals x ∈ CN can be uniquely
recovered from y[m, k], m = 1, 2 and k = 0, . . . , 2N − 2, as in (2.2) up to rotations if the two masks d1 , d2 ∈ CN satisfy
• d1 [n] 6= 0 or d2 [n] 6= 0 for each 0 ≤ n ≤ N − 1,
• d1 [n]d2 [n] 6= 0 for some 0 ≤ n ≤ N − 1.
For some masks d1 and d2 , one can overcome the ‘almost all’ in Theorem 3.9 and obtain uniqueness of the corresponding phase retrieval problem.
Theorem 3.10. [69] If the diagonal matrices D1 , D2 correspond to the two
masks
(
0 n=0
d1 [n] = 1 (0 ≤ n ≤ N − 1)
and
d2 [n] =
1 1 ≤ n, ≤ N − 1,
(3.1)
N
then every complex-valued signal x ∈ C with x[0] 6= 0 can be uniquely recovered from y[m, k], m = 1, 2 and k = 0, . . . , 2N − 2, up to rotations.

12

A different approach to exploit deterministic masks in order to overcome
the ambiguity in phase retrieval is discussed in [72] and can be proven by
using the characterization in Theorem 3.1. More explicitly, here the two
masks
(
(
1, 0 ≤ n ≤ L − 1,
0, 0 ≤ n ≤ L − 1,
d1 [n] =
and
d2 [n] =
0, L ≤ n ≤ N − 1,
1, L ≤ n ≤ N − 1,
(3.2)
for some L between 1 and N − 2 are used. Pictorially, the mask d1 blocks
the right-hand side of the underlying signal x and d2 the left-hand side.
For the signals x, D1 x, and D2 x, where Di is the diagonal matrix with
respect to the mask di , we define the polynomials X, X1 , and X2 by
N−1

X(z) =

∑ x[n] zn ,

L−1

X1 (z) =

n=0

N−L−1

∑ x[n] zn

and

X2 (z) =

n=0

x[n + L] zn .

∑

n=1

Different from the autocorrelation functions of D1 x and D2 x, which are simply given by A1 (z) = X1 (z)X̃1 (z) and A2 (z) = X2 (z)X̃2 (z), the autocorrelation
function A(z) of the true signal x can be written as


A(z) = X1 (z) + zL X2 (z) zN−L−1 X̃1 (z) + X̃2 (z)
= zN−L−1 A1 (z) + X1 (z)X̃2 (z) + zN−1 X̃1 (z)X2 (z) + zL A2 (z),
since X(z) = X1 (z)+zL X2 (z). Due to the fact that X1 (z)X̃2 (z) and zN−1 X̃1 (z)X2 (z)
have no common monomials with the same degree, one can determine the
polynomials
X1 (z)X̃1 (z),

X1 (z)X̃2 (z),

X̃1 (z)X2 (z),

and X2 (z)X̃2 (z),

(3.3)

from the autocorrelation functions A(z), A1 (z) and A2 (z).
As mentioned before, the reversed polynomials X̃i (z) correspond to the
reflected zero set of Xi (z) with respect to the unit circle. Hence, assuming
that the zeros of D1 x and D2 x are pairwise different, one can determine both
zero sets by comparing the roots of the four polynomials (3.3), which yields
the following result.
Theorem 3.11. [72] Let x ∈ CN , and assume that the zeros ξi and η` of
L−1

X1 (z) = x[L − 1] ∏ (z − ξi ),

N−L−1

and

X2 (z) = x[N − 1]

∏

(z − η` ),

`=1

i=1

are pairwise different. Then the signal x can be uniquely recovered up to rotations from the Fourier magnitudes y[m, k], m = 0, 1, 2 and k = 0, . . . , 2N −
2, with the masks d0 ≡ 1 and d1 , d2 in (3.2).

13

The phase retrieval problem in Theorem 3.11 is equivalent to the recovery of x1 = D1 x and x2 = D2 x with support {0, . . . , L − 1} and {L, . . . , N − 1}
from the Fourier magnitudes of x1 , x2 , and x1 + x2 . More generally, the recovery of two arbitrary signals x1 , x2 ∈ CN from their Fourier magnitudes
and the Fourier magnitude of the interference x1 + x2 has been studied in
[15, 77]. Theorem 3.11 is a specific instance of the uniqueness guarantee
given in [15]. Furthermore, these problems are closely related to the vectorial phase retrieval problem introduced in [81, 102, 104], where the Fourier
magnitudes of a second interference x1 + jx2 are employed.
A further example for phase retrieval with deterministic masks is considered in [30], where the three masks are defined by
d2 [n] = 1 + e2π j(sn/N−1/4) ,
(3.4)
for a non-negative integer s. The masks d1 and d2 here interfere the unknown
signal x with a modulated version of the unknown signal itself, which yields
the Fourier magnitudes |x̂[k]+ x̂[k −s]|2 and |x̂[k]− j x̂[k −s]|2 . Together with
the Fourier magnitudes |x̂[k]|2 , for almost every signal, the relative phases
φ [k − s] − φ [k] of the Fourier transform x̂[k] = |x[k]| e jφ [k] can be determined.
If s is relatively prime with N, then the Fourier transform x̂ and thus the true
signal x are recovered up to rotations.
d0 [n] = 1,

d1 [n] = 1 + e2π jsn/N ,

and

Theorem 3.12. [30] Let x ∈ CN be a signal with non-vanishing DFT. Then
x is uniquely recovered from y[m, k] with K = Ñ = N and the masks in (3.4)
up to rotations if and only if the non-negative integer s is relatively prime
with N.
The masks in (3.4) as well as the uniqueness guarantee in Theorem 3.12
can be generalized to multidimensional phase retrieval [30]. If Ñ is replaced by 2N − 1, every signal x ∈ CN is uniquely recovered up to rotation from its Fourier magnitudes y[m, k] in (2.2) with masks d0 [n] = 1 and
di [n] = 1 + e jαi e2π jsn/N , i = 1, 2, where αi ∈ [−π, π), and where s can be
nearly every real number [14]. Several further examples of deterministic
masks which allow a unique recovery are detailed in [14, 30, 69, 72] and
references therein. In Section 4.2, we consider semidefinite relaxation algorithms which stably recover the unknown signal from its masked Fourier
magnitudes (2.2) under noise.

3.4

Phase retrieval from STFT measurements

We next consider uniqueness guarantees for the recovery of an unknown signal from the magnitude of its STFT as defined in (2.4). This problem can
be interpreted as a sequence of classical phase retrieval problems, where
some entries of the underlying signals have to coincide. Obviously, the

14

STFT phase retrieval problem cannot be solved uniquely if the parameter
L is greater than or equal to the window length W , since the classical problems are then independent from each other.
Under the assumption that the known window d does not vanish, i.e.,
d[n] 6= 0 for n = 0, . . . ,W − 1, some of the first uniqueness guarantees were
established in [94].
Theorem 3.13. [94] Let d be a non-vanishing window of length W > 2, and
let L be an integer in {1, . . . , bW /2c}. If the signal x ∈ CN with support
length N has at most W − 2L consecutive zeros between any two non-zero
entries, and if the first L entries of x are known, then x can be uniquely
recovered from y[m, k] with K = 2W − 1 in (2.4).
The main idea behind Theorem 3.13 is that the corresponding classical phase retrieval problems are solved sequentially. For instance, the case
m = 1 is equivalent to recovering a signal in CL+1 from its Fourier intensity and the first L entries. The uniqueness of this phase retrieval problem is
guaranteed by Theorem 3.5. Since the true signal x has at most W − 2L consecutive zeros, the remaining subproblems can also be reduced to the setting
considered in Theorem 3.5.
Knowledge of the first L entries of x in Theorem 3.13 is a strong restriction in practice. Under the a priori constraint that the unknown signal
is non-vanishing everywhere, the first L entries are not needed to ensure
uniqueness.
Theorem 3.14. [71] Let d be a non-vanishing window of length W satisfying L < W ≤ N/2. Then almost all non-vanishing signals can be uniquely
recovered up to rotations from their STFT magnitudes y[m, k] in (2.4) with
2W ≤ K ≤ N and Ñ = N.
For some classes of STFT windows, the uniqueness is guaranteed for
all non-vanishing signals [22, 45]. Both references use a slightly different
definition of the STFT, where the STFT window in (2.4) is periodically extended over the support {0, . . . , N − 1}, i.e., the indices of the window d are
considered as modulo the signal length N.
Theorem 3.15. [45] Let d be a periodic window with support length W ≥
2 and 2W − 1 ≤ N, and assume that the length-N DFT of |d[n]|2 is nonvanishing. If N and W − 1 are co-prime, then every non-vanishing signal
x ∈ CN can be uniquely recovered from its STFT magnitudes y[m, k] in (2.4)
with L = 1 and K = Ñ = N up to rotations.
Theorem 3.16. [22] Let d be a periodic window of length W , and assume
that the length-N DFT of |d[n]|2 and d[n]d[n − 1] are non-vanishing. Then
every non-vanishing signal x ∈ CN can be uniquely recovered from its STFT
magnitudes y[m, k] in (2.4) with L = 1 and K = Ñ = N up to rotations.

15

If we abandon the constraint that the underlying signal is non-vanishing,
then the behaviour of the STFT phase retrieval problem changes dramatically, and the recovery of the unknown signal becomes much more challenging. For example, if the unknown signal x possesses more than W − 1
consecutive zero entries, then the signal can be divided in two parts, whose
STFTs are completely independent. An explicit non-trivial ambiguity for
this specific setting is constructed in [45]. Depending on the window length,
there are thus some natural limitations on how far uniqueness can be ensured
for sparse signals.
Theorem 3.17. [71] Let d be a non-vanishing window of length W satisfying
L < W ≤ N/2. Then almost all sparse signals with less than min{W − L, L}
consecutive zeros can be uniquely recovered up to rotations from their STFT
magnitudes y[m, k] in (2.4) with 2W ≤ K ≤ N and Ñ = N.
In [25], the STFT is interpreted as measurements with respect to a Gabor
frame. Under certain conditions on the generator of the frame, every signal
x ∈ CN is uniquely recovered up to rotations. Further, the true signal x is
given as a closed form solution. For the STFT model in (2.4), this implies
the following uniqueness guarantee.
Theorem 3.18. [25] Let d be a periodic window of length W , and assume
that the length-N DFT of d[n]d[n − m] is non-vanishing for m = 0, . . . , N − 1.
Then every signal x ∈ C can be uniquely recovered from its STFT magnitudes
y[m, k] in (2.4) with L = 1 and K = Ñ = N up to rotations.
The main difference between Theorem 3.18 and the uniqueness results
before is that the unknown signal x ∈ CN can have arbitrarily many consecutive zeros. On the other hand, the STFT window must have a length of at
least N/2 in order to ensure that d[n]d[n − m] is not the zero vector. Thus,
the thm is only relevant for long windows. A similar result was derived in
[22], followed by a stable recovery algorithm; see Section 4.3.

3.5

FROG methods

An important optical application for phase retrieval is ultra-short laser pulse
characterization [127, 128]. One way to overcome the non-uniqueness of
Fourier phase retrieval in this application is by employing a measurement
technique called X-FROG (see also Section 2). In X-FROG, a reference
window is used to gate the sought signal, resulting in the STFT phase retrieval model (2.4). However, in practice it is quite hard to generate and
measure such a reference window. Therefore, in order to generate redundancy in ultra-short laser pulse measurements it is common to correlate the
signal with itself. This method is called Frequency-Resolved Optical Gating
(FROG).

16

Figure 3.1: Illustration of the SHG FROG technique (courtesy of [23]).
FROG is probably the most commonly used approach for full characterization of ultra-short optical pulses due to its simplicity and good experimental performance. A FROG apparatus produces a 2D intensity diagram
of an input pulse by interacting the pulse with delayed versions of itself
in a nonlinear-optical medium, usually using a second harmonic generation
(SHG) crystal [40]. This 2D signal is called a FROG trace and is a quartic function of the unknown signal. An illustration of the FROG setup is
presented in Fig. 3.1. Here we focus on SHG FROG but other types of
nonlinearities exist for FROG measurements. A generalization of FROG, in
which two different unknown pulses gate each other in a nonlinear medium,
is called blind FROG. This method can be used to characterize simultaneously two signals [135]. In this case, the measured data is referred to as a
blind FROG trace and is quadratic in both signals. We refer to the problems of recovering a signal from its blind FROG trace and FROG trace as
bivariate phase retrieval and quartic phase retrieval, respectively.
In bivariate phase retrieval we acquire, for each delay step m, the power
spectrum of
xm [n] = x1 [n] x2 [n + mL],
where L, as in the STFT phase retrieval setup, determines the overlap factor
between adjacent sections. The acquired data is given by
N−1

y [m, k] =

2
−2π jkn/N

∑ xm [n] e

n=0

=

(3.5)

2

N−1

∑ x1 [n] x2 [n + mL]e−2π jkn/N

.

n=0

Quartic phase retrieval is the special case in which x1 = x2 .
The trivial ambiguities of bivariate phase retrieval are described in the
following proposition.

17

Proposition 3.19. [23] Let x1 , x2 ∈ CN and let xm [n] := x1 [n]x2 [n + mL] for
some fixed L. Then, the following signals have the same phaseless bivariate
measurements y[m, k] as the pair x1 , x2 :
1. multiplication by global phases x1 e jψ1 , x2 e jψ2 for some ψ1 , ψ2 ∈ R,
2. the shifted signal x̃m [n] = xm [n − n0 ] for some n0 ∈ Z,
3. the conjugated and reflected signal x̀m [n] = xm [−n],
4. modulation, x1 [n]e−2π jk0 n/N , x2 [n]e2π jk0 n/N for some k0 ∈ Z.
The fundamental question of uniqueness for FROG methods has been
analyzed first in [112] for the continuous setup. The analysis of the discrete
setup appears in [23].
Theorem 3.20. [23] Let L = 1, and let x̂1 and x̂2 be the Fourier transforms of
x1 and x2 , respectively. Assume that x̂1 has at least d(N − 1)/2e consecutive
zeros (e.g., band-limited signal). Then, almost all signals are determined
uniquely, up to trivial ambiguities, from the measurements y[m, k] in (3.5)
and the knowledge of |x̂1 | and |x̂2 |. By trivial ambiguities we mean that x1
and x2 are determined up to global phase, time shift and conjugate reflection.
Several heuristic techniques have been proposed to estimate an underlying signal from its FROG trace. These algorithms are based on a variety of
methods, such as alternating projections, gradient descent and iterative PCA
[75, 121, 129].

3.6

Multidimensional phase retrieval

In a wide range of real-world applications like crystallography or electron
microscopy, the natural objects of interest correspond to two or three-dimensional
signals. More generally, the r-dimensional phase retrieval problem consists
of the recovery of an unknown r-dimensional signal x ∈ CN1 ×···×Nr from its
Fourier magnitudes
2

y[k] =

∑

x[n]e

−(2π)r j k·n/Ñ1 ...Ñr

,
(3.6)

n∈ZN

k ∈ {0, . . . , K1 − 1} × · · · × {0, . . . , Kr − 1},
with n = (n1 , . . . , nr )T and ZN = {0, . . . , N1 − 1} × · · · × {0, . . . , Nr − 1}. Unless otherwise mentioned, we assume Ñi = Ki = 2Ni − 1.
Clearly, rotations, transitions, or conjugate reflections of the true signal
lead to trivial ambiguities. Besides these similarities, the ambiguities of the
multidimensional phase retrieval problem are very different from those of its
one-dimensional counterpart. More precisely, non-trivial ambiguities occur

18

only in very rare cases, and almost every signal is uniquely defined by its
Fourier magnitude up to trivial ambiguities.
Similarly to Section 3.1, the non-trivial ambiguities can be characterized
by exploiting the autocorrelation. Here the related polynomial
I

X(z) =

∑ x[n] zn = ∏ Xi (z),
i=1

n∈Zn

with zn = zn1 · · · znr is uniquely factorized (up to multiplicative constants)
into irreducible factors Xi (z), which means that the Xi cannot be represented
as a product of multivariate polynomials of lesser degree. The main difference with the one-dimensional setup is that most multivariate polynomials
consists of only one irreducible factor Xi . Denoting the multivariate reversed
polynomial by
X̃i (z) = zM X i (z −1 ),
with zM = zM1 · · · zMr , where M` is the degree of Xi with respect to the variable
z` , the non-trivial ambiguities in the multidimensional setting are characterized as follows.
Theorem 3.21. [63] Let x ∈ CN1 ×···×Nr be the complex-valued signal related
to the polynomial X(z) = ∏Ii=1 Xi (z), where Xi (z) are non-trivial irreducible
polynomials. Then the polynomial X 0 (z) = ∑n∈ZN x0 [n] zn of each signal x0 ∈
CN1 ×···×Nr with Fourier magnitudes y0 [k] = y[k] in (3.6) can be written as
X 0 (z) = ∏ Xi (z) · ∏ X̃i (z),
i∈J

i∈J
/

for some index set J ⊂ {1, . . . , I}.
Thus, the phase retrieval problem is uniquely solvable up to trivial ambiguities if the algebraic polynomial X(z) of the true signal x is irreducible,
or if all but one factor Xi (z) are invariant under reversion [63]. In contrast
to the one-dimensional case, where the polynomial X(z) may always be factorized into linear factors with respect to the zeros βi , cf. Theorem 3.1, most
multivariate polynomials cannot be factorized as mentioned above.
Theorem 3.22. [65] The subset of the r-variate polynomials X(z1 , . . . , zr )
with r > 1 of degree M` > 1 in z` which are reducible over the complex
numbers corresponds to a set of measure zero.
Consequently, the multidimensional phase retrieval problem has a completely different behaviour than its one-dimensional counterpart.
Corollary 3.23. Almost every r-dimensional signal with r > 1 is uniquely
defined by its Fourier magnitudes y[k] in (3.6) up to trivial ambiguities.

19

Investigating the close connection between the one-dimensional and twodimensional problem formulations, the different uniqueness properties have
been studied in [78]. Particularly, one can show that the two-dimensional
phase retrieval problem corresponds to a one-dimensional problem with additional constraints, which almost always guarantee uniqueness. Despite
these uniqueness guarantees, there are no systematic methods to estimate an
r-dimensional signal from its Fourier magnitude [8, 78]. The most popular techniques are based on alternating projection algorithms as discussed in
Section 4.1.

4

Phase retrieval algorithms

The previous section presented conditions under which there exists a unique
mapping between a signal and its Fourier magnitude (up to trivial ambiguities). Yet, the existence of a unique mapping does not imply that we can
actually estimate the signal in a stable fashion. The goal of this section is to
present different algorithmic approaches for the inverse problem of recovering a signal from its phaseless Fourier measurements. In the absence of
noise, this task can be formulated as a feasibility problem over a non-convex
set
findz∈CN

subject to y[m, k] = | fk∗ Dm z|2 ,
k = 0, . . . , K − 1,

m = 0, . . . , M − 1.

(4.1)

Recall that (4.1) covers the classical and STFT phase retrieval problems as
special cases.
From the algorithmic point–of–view, it is often more convenient to formulate the problem as a minimization problem. Two common approaches
are to minimize the intensity–based loss function
minz∈CN

K−1 M−1 

∑ ∑

y[m, k] − | fk∗ Dm z|2

2

,

(4.2)

k=0 m=0

or the amplitude–based loss function (see for instance [52, 133, 130])
minz∈CN

K−1 M−1 p

∑ ∑

2
y[m, k] − | fk∗ Dm z| .

(4.3)

k=0 m=0

The chief difficulty arises from the non-convexity of these loss functions.
For example, if x is a real signal, then (4.2) is a sum of MK quartic polynomials. Hence, there is no reason to believe that a gradient algorithm will
converge to the target signal from an arbitrary initialization. To demonstrate
this behavior, we consider an STFT phase retrieval setup for which a unique

20

Figure 4.1: This figure examines the empirical success rate of a gradient algorithm (GD) that minimizes (4) and the Griffin-Lim algorithm (GLA) as presented
in Algorithm 2 for the STFT phase retrieval problem with a rectangular window.
For each value of W , 100 experiments were conducted with N = 23 and L = 1 in
a noise-free environment. Note that a unique solution is guaranteed according to
Theorem 3.16. The underlying signals and the initializations were drawn from an
i.i.d. normal distribution. A success was declared when the objective function is
below 10−4 .
solution is guaranteed (see Theorem 3.16). We attempt to recover the signal by employing two methods: a gradient descent algorithm that minimizes
(4.2) and the classical Griffin-Lim algorithm (see Section 4.1 and Algorithm
2). Both techniques were initialized from 100 different random vectors. As
can be seen in Fig. 4.1, even for long windows, the algorithms do not always
converge to the global minimum. Furthermore, the success rate decreases
with the window’s length. In what follows, we present different systematic
approaches to recover a signal from its phaseless Fourier measurements and
discuss their advantages and shortcomings.
The rest of this section is organized as follows. We begin in Section 4.1
by introducing the classical algorithms which are based on alternating projections. Then, we proceed in Section 4.2 with convex programs based on
semidefinite programming (SDP) relaxations. SDPs have gained popularity
in recent years as they provide good numerical performance and theoretical
guarantees. We present SDP-based algorithms for masked phase retrieval,
STFT phase retrieval, minimum phase and sparse signals. In Section 4.3, we
survey additional non-convex algorithms with special focus on STFT phase

21

retrieval. Section 4.4 presents several algorithms specialized for the case of
phase retrieval of sparse signals.

4.1

Alternating projection algorithms

In their seminal work [56], Gerchberg and Saxton considered the problem of
recovering a signal from its Fourier and temporal magnitude. They proposed
an intuitive solution which iterates between two basic steps. The algorithm
begins with an arbitrary initial guess. Then, at each iteration, it imposes
the known Fourier magnitude |x̂| and temporal magnitude |x| consecutively.
This process proceeds until a stopping criterion is attained.
The basic concept of the Gerchberg-Saxton algorithm was extended by
Fienup in 1982 to a variety of phase retrieval settings [52, 53]. Fienup suggested to replace the temporal magnitude constraint by other alternative constraints in the time domain. Examples for such constraints are the knowledge
of the signal’s support or few entries of the signal, non-negativity, or a known
subspace in which the signal lies. Recently, it was also suggested to incorporate sparsity priors [93]. These algorithms have the desired property of
error reduction. Let x̂(`) be the Fourier transform of the estimation in the `th
iteration. Then, it can be shown that the quantity E` := ∑k ||x̂[k]| − |x̂(`) [k]||2
is monotonically non-increasing. This class of methods is best understood
as alternating projection algorithms [46, 89, 97]. Namely, each iteration
consists of two consecutive projections onto sets defined by the spectral and
temporal constraints. As the first step projects onto a non-convex set (and
in some cases, the temporal projection is non-convex as well) the iterations
may not converge to the target signal. The method is summarized in Algorithm 1, where we use the definition
( z[n]
,
z[n] 6= 0,
sign(z[n]) := |z[n]|
0,
z[n] 6= 0.
Over the years, many variants of the basic alternating projection scheme
have been suggested. A popular algorithm used for CDI applications is the
hybrid input-output (HIO), which consists of an additional correction step
in the time domain [52]. Specifically, the last stage of each iteration is of the
form
(
z(`) [n],
n∈
/ γ,
x(`) [n] = (`−1)
(`)
x
[n] − β z [n],
n ∈ γ,
where γ is the set of indices for which z(`) violates the temporal constraint
(e.g., support constraint, non-negativity) and β is a small parameter. While
there is no proof that the HIO converges, it tends to avoid local minima in
the absence of noise. Additionally, it is known to be sensitive to the prior

22

Algorithm 1 General scheme of alternating projection algorithms
Input: Spectral magnitude |x̂| and additional temporal constraint on x
Output: xest - estimation of x
Initialization: random input vector x(0) , ` = 0
while halting criterion false do:
• ` ← `+1
• Compute the Fourier transform of current estimation x̂(`)
• Keep phase, update spectral magnitude ẑ(`) = |x̂| sign(x̂(`) )
• Compute z(`) , the inverse Fourier transform of ẑ(`)
• Impose temporal constraints on z(`) to obtain x(`)
end while
Return: xest ← x(`)
knowledge accuracy [114]. For additional alternating projection schemes,
we refer the interested reader to [9, 35, 47, 86, 91, 107].
Griffin and Lim proposed a modification of Algorithm 1 specialized for
STFT phase retrieval [60]. In this approach, the last step at each iteration
harnesses the knowledge of the STFT window to update the signal estimation. The Griffin-Lim heuristic is summarized in Algorithm 2.

4.2

Semidefinite relaxation algorithms

In recent years, algorithms based on convex relaxation techniques have attracted considerable attention [30, 131]. These methods are based on the
insight that while the feasibility problem (4.1) is quadratic with respect to x,
it is linear in the matrix xx∗ . This leads to a natural convex SDP relaxation
that can be solved in polynomial time using standard solvers like CVX [59].
In many cases, these relaxations achieve excellent numerical performance
followed by theoretical guarantees. However, the SDP relaxation optimizes
over N 2 variables and therefore its computational complexity is quite high.
SDP relaxation techniques begin by reformulating the measurement model
(2.3) as a linear function of the Hermitian rank–one matrix X := xx∗ :
y[m, k] = ( fk∗ Dm x)∗ ( fk∗ Dm x) = x∗ D∗m fk fk∗ Dm x = trace(D∗m fk fk∗ Dm X).
Consequently, the problem of recovering x from y can be posed as the feasibility problem of finding a rank–one Hermitian matrix which is consistent

23

Algorithm 2 Griffin-Lim algorithm
Input: STFT magnitude |x̂d [m, k]|
Output: xest - estimation of x
Initialization: random input vector x(0) , ` = 0
while halting criterion false do:
• ` ← `+1
(`)

• Compute the STFT of current estimation x̂d

(`)

• Keep phase, update STFT magnitudes ẑ(`) = |x̂d | sign(x̂d )
(`)

• For each fixed m, compute zm , the inverse Fourier transform of ẑ(`)
• Update signal estimate x(`) [n] =

(`)

∑m zm [n] d[mL−n]
∑m |d[mL−n]|2

end while
Return: xest ← x(`)
with the measurements:
find

X ∈H N

subject to X  0,

rank(X) = 1,

y[m, k] = trace(D∗m fk fk∗ Dm X),
k = 0, . . . , K − 1,

(4.4)

m = 0, . . . , M − 1,

where H N is the set of all N × N Hermitian matrices. If there exists a matrix X satisfying all the constraints of (4.4), then it determines x up to global
phase. The feasibility problem (4.4) is non-convex due to the rank constraint. A convex relaxation may be obtained by omitting the rank constraint
leading to the SDP [30, 57, 116, 131]:
find X ∈ H N

subject to X  0,
y[m, k] = trace(D∗m fk fk∗ Dm X),
k = 0, . . . , K − 1,

(4.5)

m = 0, . . . , M − 1.

If the solution of (4.5) happens to be of rank one, then it determines x
up to global phase. In practice, it is useful to promote a low rank solution
by minimizing an objective function over the constraints of (4.5). A typical
choice is the trace function, which is the convex hull of the rank function for
Hermitian matrices. The resulting SDP relaxation algorithm is summarized
in Algorithm 3.
The SDP relaxation for the classical phase retrieval problem (i.e., M = 1
and D0 = IN ) was investigated in [66]. It was shown that SDP relaxation
achieves the optimal cost function value of (4.2). However, recall that in
general the classical phase retrieval problem does not admit a unique solution. Minimum phase signals are an exception as explained in Section 3.2.3.

24

Algorithm 3 SDP relaxation for phase retrieval with masks
Input: Fourier magnitudes y[m, k] as given in (2.2) and the masks
Dm , m = 0, . . . , M − 1
Output: xest - estimation of x
Solve:
min trace(X) subject to X  0,

x∈H N

y[m, k] = trace(D∗m fk fk∗ Dm X),
k = 0, . . . , K − 1, m = 0, . . . , M − 1.

Return : xest - the best rank–one approximation of the SDP’s solution.
Let a be the autocorrelation sequence of the estimated signal from Algorithm 3. If x is minimum phase, then it can be recovered by the following
program:
maxX∈H N

X[0, 0] subject to X  0,

trace(Θk X) = a[k],

k = 0, . . . , N − 1,

(4.6)

where Θk is a Toeplitz matrix with ones in the kth diagonal and zero otherwise. The solution of (4.6), XMP , is guaranteed to be rank one so that
XMP = xx∗ . See Section 3.2.3 for a different algorithm to recover minimum
phase signals.
An SDP relaxation for deterministic masks was investigated in [69],
where the authors consider two types of masks. Here, we consider the two
masks, d1 and d2 , given in (3.1). Let D1 and D2 be the diagonal matrices
associated with d1 and d2 , respectively, and assume that each measurement
is contaminated by bounded noise ε. Then, it was suggested to estimate the
signal by solving the following convex program
minX∈H N

trace(X) subject to X  0,
|y[m, k] − trace(D∗m fk fk∗ Dm X)| ≤ ε,
k = 0, . . . , 2N − 1,

m = 0, 1.
(4.7)

This program achieves stable recovery in the sense that the recovery error
is proportional to the noise level and reduces to zero in the noise-free case.
Note however that in the presence of noise the solution is not likely to be
rank one.
Theorem 4.1. [69] Consider a signal x ∈ CN satisfying kxk1 ≤ β and |x[0]| ≥
γ > 0. Suppose that the measurements are taken with the diagonal matrices

25

D1 and D2 (masks) associated with d1 and d2 given in (3.1). Then, the solution Xe of the convex program (4.7) obeys
kXe − xx∗ k2 ≤ C(β , γ)ε
for some numerical constant C(β , γ).
Phase retrieval from STFT measurements using SDP was considered in
[71]. Here, SDP relaxation in the noiseless case takes on the form
minX∈H N

trace(X) subject to X  0,
y[m, k] = trace(D∗m fk fk∗ Dm X),
k = 0, . . . , K − 1,

m = 0, . . . , M − 1,
(4.8)

where M = dN/Le is the number of STFT windows and Ñ = N (see (2.4)). In
[71], it was proven that (4.8) recovers the signal exactly under the following
conditions.
Theorem 4.2. [71] The convex program (4.8) has a unique feasible matrix
X = xx∗ for almost all non-vanishing signals x if:
• d[n] 6= 0 for n = 0, . . . ,W − 1,
• 2L ≤ W ≤ N/2,
• 4L ≤ K ≤ N,
• x[n] is known apriori for 0 ≤ n ≤

L
2 ,

where W is the window’s length.
Note that for L = 1 no prior knowledge on the entries of x is required.
An interesting implication of this thm is that recovery remains exact even
if we merely have access to the low frequencies of the data. This property
is called super-resolution and will be discussed in more detail in the context
of sparse signals. Numerically, the performance of (4.8) is better than Theorem 4.2 suggests. Specifically, it seems that for W ≥ 2L, (4.8) recovers xx∗
exactly without any prior knowledge on the entries of x, as demonstrated in
Fig. 4.2 (a similar example is given in [71]). Additionally, the program is
stable in the presence of noise.

4.3

Additional non-convex algorithms

In this section, we present additional non-convex algorithms for phase retrieval with special focus on STFT phase retrieval. A naive way to estimate
the signal from its phaseless measurements is by minimizing the non-convex
loss functions (4.2) or (4.3) by employing a gradient descent scheme. However, as demonstrated in Fig. 4.1, this algorithm is likely to converge to a

26

1

1
0.9

2
0.8

3
0.7

4
0.6

L

5
0.5

6
0.4

7
0.3

8
0.2

9
0.1

10
0

5

10

15

20

W

Figure 4.2: The empirical success rate of the SDP relaxation for STFT phase
retrieval (4.8) with a rectangular window of length W , i.e., d[n] = 1 for n =
0, . . . ,W − 1. For each pair (W, L), 100 complex signals of length N = 40 were
drawn from an i.i.d. normal distribution. The figure presents the empirical success
rate. An experiment was declared as a success if the recovery error is below 10−4 .
local minimum due to the non-convexity of the loss functions. Hence, the
key is to introduce an efficient method to initialize the non-convex algorithm
sufficiently close to the global minimum.
A recent paper [22] suggests an initialization technique for STFT phase
retrieval, which we now describe. Consider the one-dimensional Fourier
transform of the data with respect to the frequency variable (see (2.4)), given
by
N−1

ỹ[m, `] =

∑ x[n]x[n + `]d[mL − n]d[mL − n − `],

n=0

where Ñ = N and both the signal and the window are assumed to be periodic.
For fixed `, we obtain the linear system of equations
ỹ` = G` x` ,

(4.9)

dN/Le−1

where ỹ` = {ỹ[m, `]}m=0 , x` ∈ CN is the `th diagonal of the matrix xx∗ and
G` ∈ CdN/Le×N is the matrix with (m, n)th entry given by d[mL−n]d[mL − n − `].
For L = 1, G` is a circulant matrix. Clearly, recovering x` for all ` is equivalent to recovering xx∗ . Hence, the ability to estimate x depends on the properties of the window which determines G` . To make this statement precise,
we use the following definition.
Definition 4.3. A window d is called an admissible window of length W
if for all ` = −(W − 1), . . . , (W − 1) the associated circulant matrices G` in
(4.9) are invertible.

27

Algorithm 4 Least-squares algorithm for STFT phase retrieval with L = 1
Input: The STFT magnitude y[m, k] as given in (2.4) with Ñ = N
Output: xest - estimation of x
1. Compute ỹ [m, `], the one-dimensional DFT of y[m, k] with respect to the
second variable.
2. Construct a matrix X0 such that
(
G†` ỹ` , ` = − (W − 1) , · · · , (W − 1) ,
diag (X0 , `) =
0,
otherwise,
where G` ∈ RN×N and ỹ` are given in (4.9).
Return:
xest =

r

∑ (G†0y0)[n]x p,

n∈P

where P := {n : (G†0 y0 )[n] > 0} and x p is the principle (unit-norm) eigenvector of
X0 .
An example of an admissible window is a rectangular window with W ≤
N/2 and N a prime number. If the STFT window is sufficiently long and
admissible, then the STFT phase retrieval has a closed-form solution. This
solution can be obtained by the principal eigenvector of a matrix, constructed
as the solution of a least-squares problem according to (4.9). This algorithm
is summarized in Algorithm 4.
Theorem 4.4. [22] Let
 L = 1 and suppose that d is an admissible window
N+1
of length W ≥ 2 (see Definition 4.3). Then, Algorithm 4 recovers any
complex signal up to global phase.


In many cases, the window is shorter than N+1
. However, the same
2
technique can be applied to initialize a refinement process, such as a gradient method or the Griffin-Lim algorithm (GLA). In this case, the distance
between the initial vector (the output of Algorithm 4) and the target signal
can be estimated as follows.
Theorem 4.5. [22] Suppose thatp
L = 1, kxk2 = 1, d is an admissible window
of length W ≥ 2 and that kxk∞ ≤ B/N for some 0 < B ≤ N/(2N − 4W + 2).
Then, the output x0 of Algorithm 4 satisfies
r
N − 2W + 1
jφ 2
min kx − x0 e k2 ≤ 1 − 1 − 2B
.
N
φ ∈[0,2π)
For L > 1, it is harder to obtain a reliable estimation of the diagonals
of xx∗ . Nevertheless, a simple heuristic is proposed in [22] based on the

28

1.2
L=1
L=2
L=4

1

0.2
0.18

GD
GLA

0.16
0.14
0.12

0.6

error

error

0.8

0.1
0.08

0.4

0.06
0.04

0.2

0.02

0
0

10

20

30

40

50

0
20

60

25

30

35

40

45

50

SNR [db]

W

Figure 4.3: (left) Average error (over 50 experiments) of the initialization method
of Algorithm 4 as a function of W and L. The experiments were conducted on a
2
2
signal of length N = 101 with a Gaussian window d[n] = e−n /2σ . The window
length was set to W = 3σ . (right) Average normalized recovery error (over 20
experiments) of the gradient descent (GD) and Griffin-Lim algorithm (GLA) in the
presence of normal i.i.d. noise. Both algorithms were initialized by Algorithm 4.
The experiments were conducted on signals of length N = 53 with a rectangular
window of length W = 19 and L = 2. The figures are taken from [22].
smoothing properties of typical STFT windows. Fig. 4.3 shows experiments
corroborating the effectiveness of this initialization approach for L > 1.
We have seen that under some conditions, the STFT phaseless measurements provide partial information on the matrix xx∗ . In some cases, the
main diagonal of xx∗ , or equivalently the temporal magnitude of x, are also
measured. Therefore, if the signal is non-vanishing, then all entries of the
matrix xx∗ can be normalized to have unit modulus. This in turn implies that
the STFT phase retrieval problem is equivalent to estimating the missing
entries of a rank–one matrix with unit modulus entries (i.e., phases). This
problem is known as phase synchronization. In recent years, several algorithms for phase synchronization were suggested and analyzed, among them
eigenvector-based methods, SDP relaxations, projected power methods and
approximate message passing algorithms [4, 7, 26, 36, 98, 122]. Recent
papers [67, 68] adopted this approach and suggested spectral and greedy
algorithms for STFT phase retrieval. These methods are accompanied by
stability guarantees and can be modified for phase retrieval using masks.
The main shortcoming of this approach is that it relies on a good estimation
of the temporal magnitudes which may not always be available.
Another interesting approach has been recently proposed in [99]. This
paper suggests a multi-stage algorithm based on spectral clustering and angular synchronization. It is shown that the algorithm achieves stable estimation (and exactness in the noise-free setting) with only O(N log N) phaseless

29

STFT measurements. Nevertheless, the algorithm builds upon random STFT
windows of length N while most applications use shorter windows.

4.4

Algorithms for sparse signals

In this section, we assume that the signal is sparse with a sparsity level defined as
s = {#n : x[n] 6= 0}.
In this case, the basic phase retrieval problem (4.2) can be modified to the
constrained least-squares problem
minz∈CN

K−1 M−1 

∑ ∑

y[m, k] − | fk∗ Dm z|2

2

subject to kzk0 ≤ s,

(4.10)

k=0 n=0

where we use k · k0 as the standard `0 pseudo-norm counting the non-zero
entries of a signal.
Many phase retrieval algorithms for sparse signals are modifications of
known algorithms for the non-sparse case. For instance, gradient algorithms
where modified to take into account the sparsity structure. The underlying
idea of these algorithms is to add a thresholding step at each iteration. Theoretical analysis of these algorithms for phase retrieval with random sensing
vectors is considered in [28, 134]. A similar modification for the HIO algorithm was proposed in [93]. Modifications of SDP relaxation methods for
phase retrieval with random sensing vectors were considered in [83, 95, 96].
Here, the core idea is to incorporate a sparse-promoting regularizer in the
objective function. However, this technique cannot be adapted directly to
Fourier phase retrieval because of the trivial ambiguities of translation and
conjugate reflection; see a detailed explanation in [70]. To overcome this
barrier, a Two-Stage Sparse Phase-Retrieval (TSPR) algorithm was proposed in [73]. The first stage of the algorithm involves estimating the support
of the signal directly from the support of its autocorrelation. This problem is
equivalent to the turnpike problem of estimating a set of integers from their
pairwise distances [123]. Once the support is known, the second stage involves solving an SDP to estimate the missing amplitudes. It was proven that
TSPR recovers signals exactly in the noiseless case as long as the sparsity
level is less than O(N 1/2 ). In the noisy setting, recovery is robust for sparsity
level lower than O(N 1/4 ). A different SDP-based approach was suggested
in [116]. This method proposes to promote a sparse solution by the log-det
heuristic [50] and an `1 − `2 constraint on the matrix xx∗ .
An alternative class of algorithms that has been proven to be highly effective for sparse signals is the class of greedy algorithms, see for instance
[11, 88]. For phase retrieval tasks, a greedy optimization algorithm called
GESPAR (GrEedy Sparse PhAse Retrieval) is proposed in [113]. The algorithm was applied for a variety of optical tasks, such as CDI and phase

30

Algorithm 5 A schematic outline of GESPAR algorithm; for details see [113]
Input: Fourier magnitude y as in (2.2) and sparsity level s
Output: xest - estimation of x
Initialization:
• Generate a random support set S(0) of size s
• Employ a damped Gauss-Newton method with support S(0) and obtain an
initial estimation x(0)
• Set ` = 0
while halting criterion false do:
• ` ← `+1
• Update support by swapping two entries, one in S(`−1) and one in the complementary set
• Minimize a non-convex objective with the given support S(`) using the
damped Gauss-Newton method to obtain x(`)
end while
Return: xest ← x(`)
retrieval through waveguide arrays [115, 117, 119, 120]. GESPAR is a local
search algorithm, based on iteratively updating the signal support. Specifically, two elements are being updated at each iteration by swapping. Then,
a non-convex objective function that takes the support into account is minimized by a damped Gauss-Newton method. The swap is carried out between
the support element corresponds to the smallest entry (in absolute value) and
the off-support element with maximal gradient value of the objective function. A modification of GESPAR for STFT phase retrieval was presented
in [45]. A schematic outline of GESPAR is given in Algorithm 5; for more
details, see [113].
In practice, many optical measurement processes blur the fine details of
the acquired data and act as low-pass filters. In these cases, one aims at estimating the signal from its low-resolution Fourier magnitudes. This problem
combines two classical problems: phase retrieval and super-resolution. In
recent years, super-resolution for sparse signals has been investigated thoroughly [2, 18, 20, 21, 31, 42]. In Theorem 4.2, we have seen that the SDP
(4.8) can recover a signal from its low-resolution STFT magnitude. The
problem of recovering a signal from its low-resolution phaseless measurements using masks was considered in [74, 108]. It was proven that exact
recovery may be obtained by only few1 carefully designed masks if the un1 Specifically,

several combinations of masks are suggested. Each combination consists of

31

derlying signal is sparse and its support is not clustered (this requirement
is also known as the separation condition). An extension to the continuous setup was suggested in [39]. A combinatorial algorithm for recovering
a signal from its low-resolution Fourier magnitude was suggested in [38].
The algorithm recovers an s-sparse signal exactly from 2s2 − 2s + 2 lowpass magnitudes. Nevertheless, this algorithm is unstable in the presence of
noise due to error propagation.

5

Conclusion

In this chapter, we studied the problem of Fourier phase retrieval. We focused on the question of uniqueness, presented the main algorithmic approaches and discussed their properties. To conclude the chapter, we outline
several fundamental gaps in the theory of Fourier phase retrieval.
Although many different methods have been proposed and analyzed in
the last decade for Fourier phase retrieval, alternating projection algorithms
maintained their popularity. Nevertheless, the theoretical understanding of
these algorithms is limited. Another fundamental open question regards
multidimensional phase retrieval. While almost all multidimensional signals are determined uniquely by their Fourier magnitude, there is no method
that provably recovers the signal.
In many applications in optics, the measurement process acts as a lowpass filter. Hence, a practical algorithm should recover the missing phases
(phase retrieval) and resolve the fine details of the data (super-resolution). In
this chapter, we surveyed several works dealing with the combined problem.
Nonetheless, the current approaches are based on inefficient SDP programs
[39, 71, 74, 108] or lack theoretical analysis [22, 116]. Additionally, even
if all frequencies are available, it is still not clear what is the maximal sparsity that enables efficient and stable recovery of a signal from its Fourier
magnitude.
In ultra short laser pulse characterization, it is common to use the FROG
methods that were introduced in Section 3.5. It is interesting to understand
the minimal number of measurements which can guarantee uniqueness for
FROG-type methods. Additionally, a variety of algorithms are applied to estimate signals from FROG-type measurements; a theoretical understanding
of these algorithms is required.

References
[1] https://www.nobelprize.org/nobel_prizes/
three to five deterministic masks.

32

medicine/laureates/1962/.
[2] Jean-Marc Azais, Yohann De Castro, and Fabrice Gamboa. Spike detection from inaccurate samplings. Applied and Computational Harmonic Analysis, 38(2):177–195, 2015.
[3] Radu Balan, Pete Casazza, and Dan Edidin. On signal reconstruction without phase. Applied and Computational Harmonic Analysis,
20(3):345–356, 2006.
[4] Afonso S. Bandeira, Nicolas Boumal, and Amit Singer. Tightness of
the maximum likelihood semidefinite relaxation for angular synchronization. Mathematical Programming, 163(1):145–167, 2017.
[5] Afonso S Bandeira, Jameson Cahill, Dustin G Mixon, and Aaron A
Nelson. Saving phase: Injectivity and stability for phase retrieval. Applied and Computational Harmonic Analysis, 37(1):106–125, 2014.
[6] Afonso S Bandeira, Yutong Chen, and Dustin G Mixon. Phase retrieval from power spectra of masked signals. Information and Interference: A Journal of the IMA, 3(2):83–102, 2014.
[7] Afonso S Bandeira, Yutong Chen, and Amit Singer. Non-unique
games over compact groups and orientation estimation in cryo-em.
arXiv preprint arXiv:1505.03840, 2015.
[8] Heinz H Bauschke, Patrick L Combettes, and D Russell Luke. Phase
retrieval, error reduction algorithm, and fienup variants: a view from
convex optimization. JOSA A, 19(7):1334–1345, 2002.
[9] Heinz H Bauschke, Patrick L Combettes, and D Russell Luke.
Hybrid projection–reflection method for phase retrieval. JOSA A,
20(6):1025–1034, 2003.
[10] Buyurman Baykal. Blind channel estimation via combining autocorrelation and blind phase estimation. IEEE Transactions on Circuits
and Systems I: Regular Papers, 51(6):1125–1131, 2004.
[11] Amir Beck and Yonina C Eldar. Sparsity constrained nonlinear optimization: Optimality conditions and algorithms. SIAM Journal on
Optimization, 23(3):1480–1509, 2013.
[12] Robert Beinert.
Ambiguities in one-dimensional phase retrieval from Fourier magnitudes.
PhD thesis, Georg-AugustUniversität, Göttingen, 2015.
http://hdl.handle.net/
11858/00-1735-0000-0028-8691-3.
[13] Robert Beinert. Non-negativity constraints in the one-dimensional
discrete-time phase retrieval problem. Information and Inference: A
Journal of the IMA, 2016. doi: 10.1093/imaiai/iaw018.

33

[14] Robert Beinert. One-dimensional phase retrieval with additional
interference measurements. Results in Mathematics, 2016. doi:
10.1007/s00025-016-0633-9.
[15] Robert Beinert and Gerlind Plonka. Ambiguities in one-dimensional
discrete phase retrieval from Fourier magnitudes. Journal of Fourier
Analysis and Applications, 21(6):1169–1198, 2015.
[16] Robert Beinert and Gerlind Plonka. Enforcing uniqueness in onedimensional phase retrieval by additional signal information in time
domain. Applied and Computational Harmonic Analysis, 2017. doi:
10.1016/j.acha.2016.12.002.
[17] Robert Beinert and Gerlind Plonka. Sparse phase retrieval of onedimensional signals by Prony’s method. Frontiers in Applied Mathematics and Statistics (Mathematics of Computation and Data Science), 3(5), 2017.
[18] Tamir Bendory. Robust recovery of positive stream of pulses. IEEE
Transactions on Signal Processing, 65(8):2114–2122, April 2017.
[19] Tamir Bendory, Nicolas Boumal, Chao Ma, Zhizhen Zhao, and Amit
Singer. Bispectrum inversion with application to multireference
alignment. arXiv preprint arXiv:1705.00641, 2017.
[20] Tamir Bendory, Shai Dekel, and Arie Feuer. Super-resolution on the
sphere using convex optimization. IEEE Transactions on Signal Processing, 63(9):2253–2262, 2015.
[21] Tamir Bendory, Shai Dekel, and Arie Feuer. Robust recovery of
stream of pulses using convex optimization. Journal of Mathematical Analysis and Applications, 442(2):511–536, 2016.
[22] Tamir Bendory and Yonina C Eldar. Non-convex phase retrieval from
STFT measurements. arXiv preprint arXiv:1607.08218, 2016.
[23] Tamir Bendory, Pavel Sidorenko, and Yonina C Eldar. On the uniqueness of FROG methods. IEEE Signal Processing Letters, 24(5):722–
726, 2017.
[24] Jacopo Bertolotti, Elbert G van Putten, Christian Blum, Ad Lagendijk, Willem L Vos, and Allard P Mosk. Non-invasive imaging
through opaque scattering layers. Nature, 491(7423):232–234, 2012.
[25] Irena Bojarovska and Axel Flinth. Phase retrieval from Gabor measurements. Journal of Fourier Analysis and Applications, 22(3):542–
567, 2016.
[26] Nicolas Boumal. Nonconvex phase synchronization. SIAM Journal
on Optimization, 26(4):2355–2377, 2016.
[27] Yu M Bruck and LG Sodin. On the ambiguity of the image reconstruction problem. Optics communications, 30(3):304–308, 1979.

34

[28] T Tony Cai, Xiaodong Li, Zongming Ma, et al. Optimal rates of
convergence for noisy sparse phase retrieval via thresholded wirtinger
flow. The Annals of Statistics, 44(5):2221–2251, 2016.
[29] Emmanual J Candès, Xiaodong Li, and Mahdi Soltanolkotabi. Phase
retrieval from coded diffraction patterns. Applied and Computational
Harmonic Analysis, 39(2):277–299, 2015.
[30] Emmanuel J Candès, Yonina C Eldar, Thomas Strohmer, and
Vladislav Voroninski. Phase retrieval via matrix completion. SIAM
review, 57(2):225–251, 2015.
[31] Emmanuel J Candès and Carlos Fernandez-Granda. Towards a mathematical theory of super-resolution. Communications on Pure and
Applied Mathematics, 67(6):906–956, 2014.
[32] Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 52(2):489–509, 2006.
[33] Henry N Chapman, Anton Barty, Michael J Bogan, Sébastien Boutet,
Matthias Frank, Stefan P Hau-Riege, Stefano Marchesini, Bruce W
Woods, Saša Bajt, W Henry Benner, et al. Femtosecond diffractive imaging with a soft-X-ray free-electron laser. Nature Physics,
2(12):839–843, 2006.
[34] Bo Chen, Ruben A Dilanian, Sven Teichmann, Brian Abbey, Andrew G Peele, Garth J Williams, Peter Hannaford, Lap Van Dao,
Harry M Quiney, and Keith A Nugent. Multiple wavelength diffractive imaging. Physical Review A, 79(2):023809, 2009.
[35] Chien-Chun Chen, Jianwei Miao, CW Wang, and TK Lee. Application of optimization technique to noncrystalline X-ray diffraction
microscopy: Guided hybrid input-output method. Physical Review B,
76(6):064113, 2007.
[36] Yuxin Chen and Emmanuel Candès. The projected power method:
An efficient algorithm for joint alignment from pairwise differences.
arXiv preprint arXiv:1609.05820, 2016.
[37] Yuxin Chen and Emmanuel J. Cands. Solving random quadratic systems of equations is nearly as easy as solving linear systems. Communications on Pure and Applied Mathematics, 70(5):822–883, 2017.
[38] Yuxin Chen, Yonina C Eldar, and Andrea J Goldsmith. An algorithm for exact super-resolution and phase retrieval. In 2014 IEEE
International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 754–758. IEEE, 2014.

35

[39] Myung Cho, Christos Thrampoulidis, Weiyu Xu, and Babak Hassibi.
Phaseless super-resolution in the continuous domain. arXiv preprint
arXiv:1609.08522, 2016.
[40] KW DeLong, Rick Trebino, J Hunter, and WE White. Frequencyresolved optical gating with the use of second-harmonic generation.
JOSA B, 11(11):2206–2215, 1994.
[41] David L Donoho. Compressed sensing. IEEE Transactions on information theory, 52(4):1289–1306, 2006.
[42] Vincent Duval and Gabriel Peyré. Exact support recovery for sparse
spikes deconvolution. Foundations of Computational Mathematics,
15(5):1315–1355, 2015.
[43] Yonina C Eldar. Sampling Theory: Beyond Bandlimited Systems.
Cambridge University Press, 2015.
[44] Yonina C Eldar and Shahar Mendelson. Phase retrieval: Stability and
recovery guarantees. Applied and Computational Harmonic Analysis,
36(3):473–494, 2014.
[45] Yonina C Eldar, Pavel Sidorenko, Dustin G Mixon, Shaby Barel, and
Oren Cohen. Sparse phase retrieval from short-time Fourier measurements. IEEE Signal Processing Letters, 22(5):638–642, 2015.
[46] Veit Elser. Phase retrieval by iterated projections. JOSA A, 20(1):40–
55, 2003.
[47] Veit Elser. Solution of the crystallographic phase problem by iterated projections. Acta Crystallographica Section A: Foundations of
Crystallography, 59(3):201–209, 2003.
[48] Albert Fannjiang. Absolute uniqueness of phase retrieval with random illumination. Inverse Problems, 28(7):20, 2012.
[49] Ahmad Faridian, David Hopp, Giancarlo Pedrini, Ulrike Eigenthaler,
Michael Hirscher, and Wolfgang Osten. Nanoscale imaging using deep ultraviolet digital holographic microscopy. Optics express,
18(13):14159–14164, 2010.
[50] Maryam Fazel, Haitham Hindi, and Stephen P Boyd. Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices. In American Control Conference, 2003.
Proceedings of the 2003, volume 3, pages 2156–2162. IEEE, 2003.
[51] Leopold Fejér. Über trigonometrische Polynome. Journal für die
reine und angewandte Mathematik, 146(2):53–82, 1916.
[52] James R Fienup. Phase retrieval algorithms: a comparison. Applied
optics, 21(15):2758–2769, 1982.

36

[53] James R Fienup. Reconstruction of a complex-valued object from the
modulus of its fourier transform using a support constraint. JOSA A,
4(1):118–123, 1987.
[54] James R Fienup and Chris Dainty. Phase retrieval and image reconstruction for astronomy. Image Recovery: Theory and Application,
pages 231–275, 1987.
[55] Laura Garwin and Tim Lincoln. A century of nature: twenty-one discoveries that changed science and the world. University of Chicago
Press, 2010.
[56] R.W. Gerchberg and W.O. Saxton. A practical algorithm for the determination of phase from image and diffraction plane pictures. Optik,
35:237, 1972.
[57] Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using
semidefinite programming. Journal of the ACM (JACM), 42(6):1115–
1145, 1995.
[58] Tom Goldstein and Christoph Studer. Phasemax: Convex phase retrieval via basis pursuit. arXiv preprint arXiv:1610.07531, 2016.
[59] Michael Grant, Stephen Boyd, and Yinyu Ye. CVX: Matlab software
for disciplined convex programming, 2008.
[60] D.W. Griffin and J.S Lim. Signal estimation from modified shorttime Fourier transform. Acoustics, Speech and Signal Processing,
IEEE Transactions on, 32(2):236–243, 1984.
[61] David Gross, Felix Krahmer, and Richard Kueng. Improved recovery
guarantees for phase retrieval form coded diffraction patterns. Applied and Computational Harmonic Analysis, 42(1):37–64, 2017.
[62] Robert W Harrison. Phase problem in crystallography. JOSA A,
10(5):1046–1055, 1993.
[63] Monson H Hayes. The reconstruction of a multidimensional sequence
from the phase or magnitude of its Fourier transform. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-30(2):140–
154, 1982.
[64] Monson H Hayes, Jae S Lim, and Alan V Oppenheim. Signal reconstruction from phase or magnitude. IEEE Transactions Acoustics,
Speech, and Signal Processing, ASSP-28(6):672–680, 1980.
[65] Monson H Hayes and James H McClellan. Reducible polynomials
in more than one variable. Proceedings of the IEEE (Proceedings
Letters), 70(2):197–198, 1982.

37

[66] Kejun Huang, Yonina C. Eldar, and Nikos D. Sidiropoulos. Phase
retrieval from 1D Fourier measurements: Convexity, uniqueness, and
algorithms. IEEE Transactions on Signal Processing, 64(23):6105–
6117, 2016.
[67] Mark A Iwen, Brian Preskitt, Rayan Saab, and Aditya Viswanathan.
Phase retrieval from local measurements: Improved robustness
via eigenvector-based angular synchronization.
arXiv preprint
arXiv:1612.01182, 2016.
[68] Mark A. Iwen, Aditya Viswanathan, and Yang Wang. Fast phase retrieval from local correlation measurements. SIAM Journal on Imaging Sciences, 9(4):1655–1688, 2016.
[69] Kishore Jaganathan, Yonina Eldar, and Babak Hassibi. Phase retrieval
with masks using convex optimization. In 2015 IEEE International
Symposium on Information Theory (ISIT), pages 1655–1659. IEEE,
2015.
[70] Kishore Jaganathan, Yonina C Eldar, and Babak Hassibi. Phase
retrieval: An overview of recent developments. arXiv preprint
arXiv:1510.07713, 2015.
[71] Kishore Jaganathan, Yonina C Eldar, and Babak Hassibi. STFT phase
retrieval: Uniqueness guarantees and recovery algorithms. IEEE
Journal of Selected Topics in Signal Processing, 10(4):770–781,
2016.
[72] Kishore Jaganathan and Babak Hassibi. Reconstruction of signals
from their autocorrelation and cross-correlation vectors, with applications to phase retrieval and blind channel estimation. Preprint,
arXiv:1610.02620v1, 2016.
[73] Kishore Jaganathan, Samet Oymak, and Babak Hassibi. Sparse phase
retrieval: Uniqueness guarantees and recovery algorithms. arXiv
preprint arXiv:1311.2745, 2013.
[74] Kishore Jaganathan, James Saunderson, Maryam Fazei, Yonina C Eldar, and Babak Hassibi. Phaseless super-resolution using masks. In
2016 IEEE International Conference on Acoustics, Speech and Signal
Processing (ICASSP), pages 4039–4043. IEEE, 2016.
[75] Daniel J Kane. Principal components generalized projections: a review [invited]. JOSA B, 25(6):A120–A132, 2008.
[76] Wooshik Kim and Monson H Hayes. The phase retrieval problem in
X-ray crystallography. In Proceedings : ICASSP 91 : 1991 International Conference on Acoustics, Speech and Signal Processing : May
14–17, 1991, volume 3, pages 1765–1768. IEEE Signal Processing
Society, 1991.

38

[77] Wooshik Kim and Monson H. Hayes. Phase retrieval using a window
function. IEEE Transactions on Signal Processing, 41(3):1409–1412,
1993.
[78] Dani Kogan, Yonina C Eldar, and Dan Oron.
On the 2D
phase retrieval problem. IEEE Transactions on Signal Processing,
65(4):1058–1067, 2016.
[79] Dirk Langemann and Manfred Tasche. Phase reconstruction by a
multilevel iteratively regularized Gauss-Newton method. Inverse
Problems, 24(3):035006(26), 2008.
[80] Dirk Langemann and Manfred Tasche. Multilevel phase reconstruction for a rapidly decreasing interpolating function. Results in Mathematics, 53(3–4):333–340, 2009.
[81] Ben Leshem, Oren Raz, Ariel Jaffe, and Boaz Nadler. The discrete
sign problem: uniqueness, recovery algorithms and phase retrieval
applications. Applied and Computational Harmonic Analysis, 2017.
[82] Ben Leshem, Rui Xu, Yehonatan Dallal, Jianwei Miao, Boaz Nadler,
Dan Oron, Nirit Dudovich, and Oren Raz. Direct single-shot phase retrieval from the diffraction pattern of separated objects. Nature communications, 7, 2016.
[83] Xiaodong Li and Vladislav Voroninski. Sparse signal recovery from
quadratic measurements via convex programming. SIAM Journal on
Mathematical Analysis, 45(5):3019–3033, 2013.
[84] YJ Liu, B Chen, ER Li, JY Wang, A Marcelli, SW Wilkins, H Ming,
YC Tian, KA Nugent, PP Zhu, et al. Phase retrieval in X-ray
imaging based on using structured illumination. Physical Review A,
78(2):023817, 2008.
[85] Erwin G Loewen and Evgeny Popov. Diffraction gratings and applications. CRC Press, 1997.
[86] D Russell Luke. Relaxed averaged alternating reflections for diffraction imaging. Inverse Problems, 21(1):37, 2004.
[87] Andrew M Maiden, Martin J Humphry, Fucai Zhang, and John M
Rodenburg. Superresolution imaging via ptychography. JOSA A,
28(4):604–612, 2011.
[88] Stéphane G Mallat and Zhifeng Zhang. Matching pursuits with timefrequency dictionaries. IEEE Transactions on signal processing,
41(12):3397–3415, 1993.
[89] Stefano Marchesini. Invited article: A unified evaluation of iterative
projection algorithms for phase retrieval. Review of scientific instruments, 78(1):011301, 2007.

39

[90] Stefano Marchesini, Yu-Chao Tu, and Hau-tieng Wu. Alternating
projection, ptychographic imaging and phase synchronization. Applied and Computational Harmonic Analysis, 2015.
[91] Andrew V Martin, Fenglin Wang, ND Loh, Tomas Ekeberg, Filipe RNC Maia, Max Hantke, Gijs van der Schot, Christina Y Hampton, Raymond G Sierra, Andrew Aquila, et al. Noise-robust coherent
diffractive imaging with a single diffraction pattern. Optics Express,
20(15):16650–16661, 2012.
[92] Jianwei Miao, Pambos Charalambous, Janos Kirz, and David
Sayre. Extending the methodology of x-ray crystallography to allow imaging of micrometre-sized non-crystalline specimens. Nature,
400(6742):342–344, 1999.
[93] Subhadip Mukherjee and Chandra Sekhar Seelamantula. An iterative
algorithm for phase retrieval with sparsity constraints: application
to frequency domain optical coherence tomography. In 2012 IEEE
International Conference on Acoustics, Speech and Signal Processing
(ICASSP), pages 553–556. IEEE, 2012.
[94] S Nawab, T Quatieri, and Jae Lim. Signal reconstruction from shorttime Fourier transform magnitude. IEEE Transactions on Acoustics,
Speech, and Signal Processing, 31(4):986–998, 1983.
[95] Henrik Ohlsson, Allen Y Yang, Roy Dong, and Shankar S Sastry.
Compressive phase retrieval from squared output measurements via
semidefinite programming. arXiv preprint arXiv, 1111, 2011.
[96] Samet Oymak, Amin Jalali, Maryam Fazel, Yonina C Eldar, and
Babak Hassibi. Simultaneously structured models with application
to sparse and low-rank matrices. IEEE Transactions on Information
Theory, 61(5):2886–2908, 2015.
[97] Edouard Pauwels, Amir Beck, Yonina C Eldar, and Shoham Sabach.
On fienup methods for regularized phase retrieval. arXiv preprint
arXiv:1702.08339, 2017.
[98] Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur
Moitra. Message-passing algorithms for synchronization problems
over compact groups. arXiv preprint arXiv:1610.04583, 2016.
[99] Goetz E Pfander and Palina Salanevich. Robust phase retrieval algorithm for time-frequency structured measurements. arXiv preprint
arXiv:1611.02540, 2016.
[100] Lawrence Rabiner and Biing-Hwang Juang. Fundamentals of speech
recognition. 1993.
[101] Juri Ranieri, Amina Chebira, Yue M Lu, and Martin Vetterli.
Phase retrieval for sparse signals: uniqueness conditions. Preprint,
arXiv:1308.3058v2, 2013.

40

[102] Oren Raz, Nirit Dudovich, and Boaz Nadler. Vectorial phase retrieval
of 1-D signals. IEEE Transactions on Signal Processing, 61(7):1632–
1643, 2013.
[103] Oren Raz, Ben Leshem, Jianwei Miao, Boaz Nadler, Dan Oron, and
Nirit Dudovich. Direct phase retrieval in double blind fourier holography. Optics express, 22(21):24935–24950, 2014.
[104] Oren Raz, Osip Schwartz, Dane Austin, AS Wyatt, Andrea Schiavi,
Olga Smirnova, Boaz Nadler, Ian A Walmsley, Dan Oron, and Nirit
Dudovich. Vectorial phase retrieval for linear characterization of attosecond pulses. Physical review letters, 107(13):133902, 2011.
[105] Ian K Robinson, Ivan A Vartanyants, GJ Williams, MA Pfeifer, and
JA Pitney. Reconstruction of the shapes of gold nanocrystals using
coherent X-ray diffraction. Physical review letters, 87(19):195505,
2001.
[106] JM Rodenburg. Ptychography and related diffractive imaging methods. Advances in Imaging and Electron Physics, 150:87–184, 2008.
[107] Jose A Rodriguez, Rui Xu, C-C Chen, Yunfei Zou, and Jianwei Miao.
Oversampling smoothness: an effective algorithm for phase retrieval
of noisy diffraction intensities. Journal of applied crystallography,
46(2):312–318, 2013.
[108] Fariborz Salehi, Kishore Jaganathan, and Babak Hassibi. Multiple
illumination phaseless super-resolution (MIPS) with applications to
phaseless DOA estimation and diffraction imaging. arXiv preprint
arXiv:1701.03515, 2017.
[109] Richard L Sandberg, Changyong Song, Przemyslaw W Wachulak,
Daisy A Raymondson, Ariel Paul, Bagrat Amirbekian, Edwin Lee,
Anne E Sakdinawat, La-O Chan, Mario C Marconi, et al. High numerical aperture tabletop soft X-ray diffraction microscopy with 70nm resolution. Proceedings of the National Academy of Sciences,
105(1):24–27, 2008.
[110] David Sayre. Some implications of a theorem due to Shannon. Acta
Crystallographica, 5(6):843–843, 1952.
[111] Birger Seifert, Heinrich Stolz, Marco Donatelli, Dirk Langemann,
and Manfred Tasche. Multilevel Gauss-Newton methods for phase
retrieval problems. Journal of Physics. A. Mathematical and General,
39(16):4191–4206, 2006.
[112] Birger Seifert, Heinrich Stolz, and Manfred Tasche. Nontrivial ambiguities for blind frequency-resolved optical gating and the problem
of uniqueness. JOSA B, 21(5):1089–1097, 2004.

41

[113] Yoav Shechtman, Amir Beck, and Yonina C Eldar. Gespar: Efficient
phase retrieval of sparse signals. IEEE transactions on signal processing, 62(4):928–938, 2014.
[114] Yoav Shechtman, Yonina C Eldar, Oren Cohen, Henry Nicholas
Chapman, Jianwei Miao, and Mordechai Segev. Phase retrieval with
application to optical imaging: a contemporary overview. IEEE signal processing magazine, 32(3):87–109, 2015.
[115] Yoav Shechtman, Yonina C Eldar, Oren Cohen, and Mordechai
Segev. Efficient coherent diffractive imaging for sparsely varying objects. Optics express, 21(5):6327–6338, 2013.
[116] Yoav Shechtman, Yonina C Eldar, Alexander Szameit, and
Mordechai Segev. Sparsity based sub-wavelength imaging with partially incoherent light via quadratic compressed sensing. Optics express, 19(16):14807–14822, 2011.
[117] Yoav Shechtman, Eran Small, Yoav Lahini, Mor Verbin, Yonina C
Eldar, Yaron Silberberg, and Mordechai Segev. Sparsity-based superresolution and phase-retrieval in waveguide arrays. Optics express,
21(20):24015–24024, 2013.
[118] Pavel Sidorenko and Oren Cohen. Single-shot ptychography. Optica,
3(1):9–14, 2016.
[119] Pavel Sidorenko, Avner Fleischer, Yoav Shechtman, Yonina C Eldar,
Moti Segev, and Oren Cohen. Sparsity-based super-resolution coherent diffractive imaging of (practically) 1D images using extreme UV
radiation. In CLEO: QELS Fundamental Science, pages QF1C–7.
Optical Society of America, 2013.
[120] Pavel Sidorenko, Ofer Kfir, Yoav Shechtman, Avner Fleischer, Yonina C Eldar, Mordechai Segev, and Oren Cohen. Sparsity-based
super-resolved coherent diffraction imaging of one-dimensional objects. Nature communications, 6, 2015.
[121] Pavel Sidorenko, Oren Lahav, Zohar Avnat, and Oren Cohen. Ptychographic reconstruction algorithm for frequency-resolved optical gating: super-resolution and supreme robustness. Optica, 3(12):1320–
1330, 2016.
[122] Amit Singer. Angular synchronization by eigenvectors and semidefinite programming. Applied and computational harmonic analysis,
30(1):20–36, 2011.
[123] Steven S Skiena, Warren D Smith, and Paul Lemke. Reconstructing
sets from interpoint distances. In Proceedings of the sixth annual
symposium on Computational geometry, pages 332–339. ACM, 1990.

42

[124] Mahdi Soltanolkotabi. Structured signal recovery from quadratic
measurements: Breaking sample complexity barriers via nonconvex
optimization. arXiv preprint arXiv:1702.06175, 2017.
[125] Mark Stefik. Inferring DNA structures from segmentation data. Artificial Intelligence, 11(1):85–114, 1978.
[126] Andreas M Tillmann, Yonina C Eldar, and Julien Mairal. DOLPHIndictionary learning for phase retrieval. IEEE Transactions on Signal
Processing, 64(24):6485–6500, 2016.
[127] Rick Trebino. Frequency-resolved optical gating: the measurement
of ultrashort laser pulses. Springer Science & Business Media, 2012.
[128] Rick Trebino, Kenneth W DeLong, David N Fittinghoff, John N
Sweetser, Marco A Krumbügel, Bruce A Richman, and Daniel J
Kane. Measuring ultrashort laser pulses in the time-frequency domain using frequency-resolved optical gating. Review of Scientific
Instruments, 68(9):3277–3295, 1997.
[129] Rick Trebino and Daniel J Kane. Using phase retrieval to measure the
intensity and phase of ultrashort pulses: frequency-resolved optical
gating. JOSA A, 10(5):1101–1111, 1993.
[130] Irène Waldspurger. Phase retrieval with random gaussian sensing
vectors by alternating projections. arXiv preprint arXiv:1609.03088,
2016.
[131] Irène Waldspurger, Alexandre dAspremont, and Stéphane Mallat.
Phase recovery, maxcut and complex semidefinite programming.
Mathematical Programming, 149(1-2):47–81, 2015.
[132] Adriaan Walther. The question of phase retrieval in optics. Journal
of Modern Optics, 10(1):41–49, 1963.
[133] Gang Wang, Georgios B Giannakis, and Yonina C Eldar. Solving
systems of random quadratic equations via truncated amplitude flow.
arXiv preprint arXiv:1605.08285, 2016.
[134] Gang Wang, Liang Zhang, Georgios B Giannakis, Mehmet
Akçakaya, and Jie Chen. Sparse phase retrieval via truncated amplitude flow. arXiv preprint arXiv:1611.07641, 2016.
[135] Tsz Chun Wong, Justin Ratner, Vikrant Chauhan, Jacob Cohen, Peter M Vaughan, Lina Xu, Antonio Consoli, and Rick Trebino. Simultaneously measuring two ultrashort laser pulses on a single-shot using
double-blind frequency-resolved optical gating. JOSA B, 29(6):1237–
1244, 2012.
[136] Lei Xu, Pingfan Yan, and Tong Chang. Almost unique specification of discrete finite length signal: from its end point and Fourier

43

transform magnitude. In Proceedings : ICASSP 87 : IEEE International Conference on Acoustics, Speech, and Signal, volume 12,
pages 2097–2100. IEEE, April 1987.
[137] Li-Hao Yeh, Jonathan Dong, Jingshan Zhong, Lei Tian, Michael
Chen, Gongguo Tang, Mahdi Soltanolkotabi, and Laura Waller. Experimental robustness of Fourier ptychography phase retrieval algorithms. Optics express, 23(26):33214–33240, 2015.

44

