1

Phase Retrieval Without
Small-Ball Probability Assumptions

arXiv:1604.07281v3 [] 11 Sep 2017

Felix Krahmer

Abstract—In the context of the phase retrieval problem, it is
known that certain natural classes of measurements, such as
Fourier measurements and random Bernoulli measurements, do
not lead to the unique reconstruction of all possible signals,
even in combination with certain practically feasible random
masks. To avoid this difficulty, the analysis is often restricted
to measurement ensembles (or masks) that satisfy a small-ball
probability condition, in order to ensure that the reconstruction
is unique.
This paper shows a complementary result: for random
Bernoulli measurements, there is still a large class of signals
that can be reconstructed uniquely, namely those signals that
are non-peaky. In fact, this result is much more general: it holds
for random measurements sampled from any subgaussian distribution D, without any small-ball conditions. This is demonstrated
in two ways: first, a proof of stability and uniqueness, and second,
a uniform recovery guarantee for the PhaseLift algorithm. In all
of these cases, the number of measurements m approaches the
information-theoretic lower bound.
Finally, for random Bernoulli measurements with erasures, it
is shown that PhaseLift achieves uniform recovery of all signals
(including peaky ones).
Index Terms—Phase retrieval, random measurements,
PhaseLift, inverse problems, reconstruction algorithms,
sampling methods, convex optimization

I. I NTRODUCTION
A. Ambiguities in Phase Retrieval
Phase retrieval is the problem of recovering an unknown
vector x ∈ Cn from measurements of the form
2

yi = |aTi x| + wi

(for i = 1, . . . , m),

(1)

where the vectors ai ∈ Cn are known, and the wi ∈ R
represent additive noise which is unknown. (The name phase
retrieval refers to the fact that the measurements reveal the
magnitudes, but not the phases, of the aTi x.) Phase retrieval
has numerous applications including X-ray crystallography
[1], [2], astronomy [3], ptychography and coherent diffractive
imaging [4], [5], and quantum state tomography [6].
A typical experiment setup is that one places a detector
far from the object being imaged, and the detector records
F. Krahmer is with Research Unit M15, Department of Mathematics,
Technische Universität München (e-mail: felix.krahmer@tum.de).
Y.-K. Liu is with the National Institute of Standards and Technology,
Gaithersburg, MD, USA, and also with the Joint Center for Quantum
Information and Computer Science, University of Maryland (e-mail: yikai.liu@nist.gov).
This paper was presented in part at the 11th International Conference on
Sampling Theory and Applications (SampTA 2015), Washington, DC, May
25–29, 2015.
Copyright 2017 IEEE. Personal use of this material is permitted. However,
permission to use this material for any other purposes must be obtained from
the IEEE by sending a request to pubs-permissions@ieee.org.

Yi-Kai Liu

the intensity of the light field, but not its phase. To a first
approximation, this situation can be described by phaseless
measurements where the ai are Fourier basis vectors. It is
well known that such phaseless measurements can give rise
to ambiguities, in the sense that the solution is not uniquely
determined. These ambiguities may include spatial shifts and
conjugate inversion. Especially in the one dimensional case,
larger classes of ambiguities can arise [7].
One way to ensure solution uniqueness is to consider a setup
with random illuminations, which mathematically corresponds
to multiplying each of the image pixels with a randomly chosen factor [8]. As argued in [8], a feasible setup is to consider
phase modulations, where each of these factors lies on the
unit circle in the complex plane. Solution uniqueness is then
shown in the two-dimensional case, under the assumption that
the image has support of rank 2. These additional assumptions
are necessary to exclude simple counterexamples. Namely, any
configuration of phase modulations yields measurements of the
form ai = (ai1 , ai2 , . . . , ain ) where
|ai1 | = |ai2 | = · · · = |ain | = 1.

(2)

Using such measurements, it is always impossible to distinguish between the vectors x = (1, 0, 0, . . . , 0) and x̃ =
2
2
(0, 1, 0, . . . , 0), since |aTi x| = 1 = |aTi x̃| .
Motivated by the uniqueness results of [8], a number of
follow-up works studied tractable reconstruction algorithms
for phase retrieval with random diffraction patterns (cf. Section I-B below). In contrast to [8], however, these works do
not restrict the signal class, but rather avoid the ambiguity
problems by considering random masks that also vary in
amplitude, which arguably are more difficult to realize in
experiments.
The main goal of this paper is to combine these approaches,
studying recoverability under mild assumptions on the class
of signals, without requiring measurement vectors of varying
amplitude. We focus on the simplest class of measurements
with property (2), namely random Bernoulli measurements,
where the ai are sampled independently and uniformly at
n
random from {1, −1} . We see our results as a proof of
concept that measurements of constant amplitude are tractable
and expect that this will lay the foundation to study the case
of phase modulated Fourier measurement, but we will leave
this case for future work.
For random Bernoulli measurements, we show that a surprisingly large class of vectors x can be recovered: one can
recover all vectors x ∈ Rn that are µ-flat, in the sense that
they satisfy
kxk∞ ≤ µkxk2 ,
(3)

2

for some constant µ ∈ (0, 1) that is independent of the
dimension n. Intuitively, this condition says that x is not too
peaky, in the sense that at most a constant fraction of its mass
is concentrated on any one coordinate.
Our result for random Bernoulli measurements is a special
case of a more general result that applies whenever the
measurement vectors ai are sampled independently at random
from some subgaussian distribution D. In the following sections, we will describe this more general setting, and state our
results in detail.
B. Gaussian and Subgaussian Measurements
The scenario in which the measurement vectors ai are
chosen at random according to certain distributions has been
investigated intensively over the last few years, with the
Gaussian distribution being the paradigmatic example. Two
main viewpoints have been taken, focusing either on stable
uniqueness, or on recovery via computationally tractable algorithms. The first viewpoint asks when x is uniquely determined
from the measurements (1) (up to sign ambiguity and a
small reconstruction error resulting from the noise) [17]. Such
stability results are known in rather general settings, where x
is promised to lie in some known set T ⊂ Rn (for instance, the
set of k-sparse vectors), and one wants to bound the number of
measurements m as a function of some complexity parameter
of the set T .
(Note, however, that these stability results [17] were shown
in the real case, where the signal x and the measurements ai
are in Rn , rather than Cn . For simplicity, in this paper we will
likewise focus on the real case.)
The second viewpoint aims at finding tractable algorithms
with provable recovery guarantees. A well-known example
is PhaseLift, which reduces the problem to one of low-rank
matrix recovery, and then solves a convex relaxation [9], [10],
[11]. In particular, these works show that PhaseLift can recover
any vector x ∈ Cn using m = O(n) noisy measurements.
The initial works from both of these viewpoints were specific to Gaussian random measurement vectors ai . Subsequent
work (mainly from the recovery viewpoint) succeeded in
partially derandomizing these results, using techniques such
as spherical designs [12], [6] and coded diffraction patterns
[13], [14]. In addition, stable uniqueness results have been
shown for ai chosen from subgaussian distributions, subject to
additional assumptions on their small ball probabilities or their
fourth moments [17]. Nonetheless, even these assumptions on
the distribution of the ai ’s are somewhat restrictive.
It is natural to ask whether these stability analyses and recovery guarantees can be extended to the most straightforward
generalization of the Gaussian measurement setup, namely
subgaussian measurement vectors ai sampled from a product
distribution (i.e., each entry aij is sampled independently
from a subgaussian distribution D on R). However, this opens
the door to measurements such as random Bernoulli vectors
n
ai ∈ {1, −1} , where phase retrieval is not always possible.
Previous work on subgaussian phase retrieval has therefore
imposed certain restrictions on the distribution of the ai , such
as small-ball and fourth moment assumptions [17], which
exclude these pathological cases.

C. Our Results
In this paper we show that a large class of vectors x can
be recovered uniquely from subgaussian measurements ai ,
without imposing any additional conditions on the distribution
of the ai . In particular, we show that one can recover all
vectors x ∈ Rn that are µ-flat in the sense of (3), where
µ ∈ (0, 1) is a constant that depends on D, but not on the
dimension n.
In particular, our results apply to Bernoulli measurements
ai . Also, note that the µ-flatness requirement does not rule
out all sparse vectors. For instance, a vector that has support
of size 1/µ2 (i.e., constant size), and that does not have any
unusually large entries, will still satisfy equation (3), and hence
will still be recoverable.
To some extent, our results are analogous to a recent result
on one-bit compressed sensing [18]. Subgaussian measurements also fail in that context, and this issue can be overcome
by restricting to the case of signals which are not too peaky.
However, the techniques used there are somewhat different.
Our results can also be compared with recent work on phase
retrieval using local correlation measurements, which also
imposed a “flatness” condition on the signal x [19]. However,
the flatness condition in that paper is more elaborate than ours,
as it depends not only on the magnitudes of the entries in the
vector x = (x1 , . . . , xn ), but also on their ordering.1
We prove three main results. First, we consider stable
uniqueness, as in [17].2 We show that the results of [17], on
phase retrieval of signals x belonging to some set T ⊂ Rn ,
can be generalized to the setting of subgaussian measurements
ai (with independent entries aij ), provided that all signals
in the set T are µ-flat (for some constant µ). We emphasize
that the ai need not satisfy any small-ball or fourth-moment
assumptions.
In particular, we show that the number of measurements m
scales with the complexity of the set T in the same way as in
[17]. For instance, where [17] showed results on phase retrieval
of k-sparse vectors in Rn , we obtain comparable results on
phase retrieval of µ-flat k-sparse vectors in Rn . (Note that a
vector can be both k-sparse and µ-flat, as long as k ≥ 1/µ2 .)
Second, we prove that the PhaseLift convex program
achieves uniform recovery of all µ-flat vectors in Rn , using
m = O(n) subgaussian measurements, in the presence of
noise.3 This extends the work of Candès and Li, who showed
a similar statement for the recovery of all vectors x ∈ Rn ,
when the ai are Gaussian distributed [11].
Here, uniform recovery means that, with high probability,
a random choice of the ai will allow correct recovery of all
possible vectors x; in contrast, a non-uniform guarantee states
that for any particular vector x, with high probability over the
choice of the ai , x will be recovered correctly. Note that the
1 Essentially, the flatness condition in that paper ensures that the vector
x does not contain long strings of consecutive 0’s. This ensures that, after
recovering different pieces of the vector x from different sets of local
measurements, one can estimate the relative phase-differences among these
pieces, in order to “stitch them together” and recover x.
2 A conference version of this first part has appeared in [15].
3 This second part also extends a conference version, which has appeared
in [16].

3

use of m = O(n) measurements is optimal up to a constant
factor.
Our proof follows a similar approach as Candès and Li
[11], but we encounter some technical differences, since in our
setting the vectors ai do not have the convenient properties of
Gaussian random vectors, and at several points we need to
exploit the µ-flatness of the vector x.
Third, we consider a special class of subgaussian measurements, sometimes called random Bernoulli vectors with
erasures. Roughly speaking,4 these are random vectors ai
whose entries aij are chosen independently from some symmetric distribution on {1, 0, −1}. Intuitively, phase retrieval
works well with these kinds of measurement vectors, because
the presence of zeroes (“erasures”) prevents the pathological
behavior that occurs with Bernoulli vectors. Indeed, this idea
was used previously in work on phase retrieval using coded
diffraction patterns [13], [14].
We show that PhaseLift can recover all vectors in Rn
(without any restriction to non-peaky or µ-flat vectors), using
m = O(n) random Bernoulli measurements with erasures (using a particular choice p = 2/3 for the “erasure probability”).
Our recovery guarantee holds uniformly over all signals in Rn ,
with noisy measurements.
This gives a new example of a class of non-Gaussian
measurements where PhaseLift works nearly as well as it
does in the case of Gaussian measurements. We remark that
while stability and uniqueness in this setting were previously
known (since the aij satisfy Eldar and Mendelson’s fourthmoment conditions) [17], there is hardly any previous work
involving PhaseLift in this situation. (The only exception
we know is [22], which uses Bernoulli measurements with
erasures in an experimental procedure for characterizing linear
optical circuits, which have applications in quantum information processing. Ref. [22] also proves recovery guarantees for
PhaseLift with this particular class of measurements, but using
a different technique from ours.)
Overall, we see our work as a proof of concept that
shows that recovery guarantees are possible for many kinds of
random measurements that were not previously considered to
be suitable. This is useful in certain situations. For instance, the
authors of [22] remark that in their optical devices, Bernoulli
measurements with erasures can be implemented more easily
than Gaussian measurements, because they use fewer levels of
quantization.
An important next step will be to carry over this approach to
more realistic and practical scenarios, such as measurements
using coded diffraction patterns [13], [14]. Previous work in
this area uses measurements that involve random masks that
are generated from a very specific distribution. We think it
is an interesting question whether one can make a tradeoff,
similar to that shown in the present paper, which would allow
more flexibility in the choice of masks, at the expense of
slightly restricting the class of signals.

4 In the precise definition, the a
ij are multiplied by a normalization factor,
so that the distribution has variance 1.

D. Outline of the Paper, and Notation
We introduce some basic definitions in Section II. We state
and prove our results on stable uniqueness in Sections III and
IV. We then present our results on PhaseLift in Sections V
through IX. Finally, we describe some directions for future
work in Section X.
We let [m] denote the set {1, 2, . . . , m}. We write vectors
in boldface, and matrices in boldface capital letters. kxkp
denotes the ℓp norm of a vector x. kXkF and kXk denote
the Frobenius and operator (spectral) norms of a matrix X,
respectively.
II. P RELIMINARIES
In this paper, we will consider phaseless measurements of
the form (1). Following [17], we will consider the real case,
where the signal x and the measurement vectors ai are real
(rather than complex).
Also following [17], we will suppose that the measurement
vectors ai ∈ Rn are sampled independently from some
subgaussian distribution. We recall that a random vector in Rn
is called L-subgaussian if all of its one-dimensional marginals
are L-subgaussian in the following sense:
Definition II.1. (cf. [21]) A real valued random variable X
is subgaussian with parameter L, if for every u ≥ 1, one has
Pr[|X| ≥ Lu] ≤ 2 exp(−u2 /2).
Here we will consider the (more specific) situation where
each ai consists of independent subgaussian entries aij ∈ R,
each sampled from some distribution D.
The main results in [17] concern measurements ai that are
subgaussian and satisfy a small-ball probability assumption:
there exists some constant c > 0 such that, for all vectors
t ∈ Rn and for all ε > 0,
Pr[|aTi t| ≤ εktk2 ] ≤ cε.

(4)

In addition, some results are shown in [17] for measurements
that satisfy a fourth-moment condition: the aij are symmetric,
with variance E(a2ij ) = 1, and fourth moment E(a4ij ) > 1.
In contrast, here we will make no such assumptions on
the ai . In particular, our results will hold for Bernoulli
measurements ai , which are sampled uniformly from the set
n
{1, −1} , and which violate both the small-ball assumption5
and the fourth-moment condition.
Our results will apply to signals x ∈ Rn that are not too
peaky, in the following sense. Let µ ∈ (0, 1) be a constant
that depends on D, but not on the dimension n.
Definition II.2. We say that a vector x ∈ Rn is µ-flat if it
satisfies
kxk∞ ≤ µkxk2 ,

(5)

A set T ⊂ Rn is called µ-flat if all its elements are µ-flat.
5 This

can be seen by setting t = (1, 1, 0, . . . , 0).

4

III. S TABLE U NIQUENESS
Our first main result concerns stable uniqueness, and follows the approach taken by Eldar and Mendelson [17]. That
is, the goal will be to find conditions to ensure that if the
measurements y1 and y2 are close, then the underlying signals
x1 and x2 must also be close (up to sign ambiguity, i.e., either
x1 − x2 or x1 + x2 must be small).
For conciseness, we write the phaseless measurement operation as
y = φ(Ax) + w,
(6)
where A ∈ Rm×n is the matrix whose i’th row is the
measurement vector ai , and φ : Rm → Rm is the function
that maps
2

2

2

φ : (s1 , s2 , . . . , sm ) 7→ (|s1 | , |s2 | , . . . , |sm | ).

(7)

A. The Noise-Free Case
We begin by considering the noise-free case. Here the notion
of stability is formalized in the following definition. One
assumes that the signal x lies in some known set T ⊂ Rn , in
order to address situations where the signal has some known
structure, such as sparsity.
Definition III.1 (Definition 2.3 in [17]). The mapping φ(Ax)
is stable with constant C > 0 in a set T ⊂ Rn if for every
s, t ∈ T ,
kφ(As) − φ(At)k1 ≥ Cks − tk2 ks + tk2 .
One then shows that, if the number of measurements m
is sufficiently large (with respect to certain parameters that
quantify the complexity of the set T ), then the mapping φ(Ax)
is stable. In particular, Eldar and Mendelson [17] proved
results of this type, for several natural choices of the set T ,
where the measurements ai are subgaussian and satisfy smallball or fourth-moment assumptions. They showed that stability
is achieved with a number of measurements m that is only
slightly larger than the information-theoretic lower bound.
We show analogous results, for the same choices of the set T
as in [17], but restricted to µ-flat vectors with constant µ, and
where the measurements ai are subgaussian with independent
coordinates, but without any small-ball or fourth-moment
assumptions. In particular, we consider the set Tµ ⊂ Rn of
all µ-flat vectors, and the set Tµ,k ⊂ Rn of all vectors which
are both k-sparse and µ-flat. We find that stability holds with
a number of measurements m that scales in the same way as
in [17].
Theorem III.2. For every L > 0, there exist constants
1
,
c1 , . . . , c8 for which the following holds. Let 0 < µ < 2√
2
n
and let Tµ,k ⊂ Tµ ⊂ R be as in the preceding paragraph.
Consider a random vector a ∈ Rn with independent Lsubgaussian entries aj with mean zero and unit variance. Let
A ∈ Rm×n be a matrix whose rows are independent copies
of this vector. Then:
n
(a) for u ≥ c1 and m ≥ c2 u3 1−8µ
2 , one has with probability
2
at least 1 − 2 exp(−c3 u n) that the mapping φ(Ax) is
stable with constant c4 (1 − 8µ2 )1/2 in Tµ .

(b) for u ≥ c5 and m ≥ c6 u3 k log(en/k)
1−8µ2 , one has with
probability at least 1−2 exp(−c7 u2 k log(en/k)) that the
mapping φ(Ax) is stable with constant c8 (1 − 8µ2 )1/2
in Tµ,k .
To summarize, in these two instances of the phase retrieval
problem, most assumptions on the distribution of the measurement vectors ai can be dropped if µ-flatness is introduced
as an additional condition on the signal x, while leaving the
other parts of the result unchanged. As we will see, the proof
is quite general, and likely applies to many other instances of
the problem.
B. Proof Outline
We now sketch the proof of Theorem III.2. This uses the
framework introduced in [17], with some technical modifications to take advantage of the µ-flatness property of the signals.
First, we define the complexity parameter ρT,m as follows. We
define T+ and T− via
s−t
T− := { ks−tk

T+ :=

: s, t ∈ T, t 6= −s}

2

s+t
{ ks+tk
2

and then we set ρT,m =

: s, t ∈ T, t 6= s}

√E
m

E = max E sup

+

n
X

E2
m,

where

gi vi , E sup

n
X

gi wi

w∈T+ i=1

v∈T− i=1



with gi independent centered Gaussian random variables of
unit variance.
For technical reasons, we will slightly modify the definition
of the second complexity parameter κ that was used in [17].
Namely, in our definition of κ we restrict to S n−1 , setting for
any v, w ∈ S n−1
κ(v, w) = E |ha, viha, wi|.

(8)

In this modified notation and restricted to our measurement
setup, the main result of [17] for the noiseless case reads as
follows.
Theorem III.3 (Theorem 2.4 in [17]). For every L ≥ 1 and
T ⊂ Rn , there exist constants c1 , c2 , c3 that depend only on
L such that the following holds.
Let a ∈ Rn be a random vector with independent, Lsubgaussian entries with mean zero and unit variance. Consider a matrix A ∈ Rm×n whose rows are independent copies
of this vector.
Then, for u ≥ c1 , with probability ≥ 1 −
2 exp(−c2 u2 min(m, E 2 )), the mapping φ(Ax) is stable in
T with constant
s−t
s+t
C = inf κ( ks−tk
, ks+tk
) − c3 u3 ρT,m .
s,t∈T

2

(9)

2

Thus in addition to bounding ρT,m from above, it suffices
to estimate the infimum of κ over the set
s−t
s+t
T∓ = {( ks−tk
, ks+tk
) : s, t ∈ T, t 6= s, t 6= −s}. (10)
2

2

As it turns out, this refined infimum allows for sharper
bounds when the set under consideration consists of not too

5

peaky vectors. Our technical contribution consists of a lower
bound on κ, which holds for µ-flat sets:
Proposition III.4. For each L > 0 there exists a constant
c > 0 such that the following holds. Consider a random vector
a with independent L-subgaussian entries ai with mean zero
and unit variance. Let T∓ and κ be defined as in equations
1
(10) and (8). Then if T ⊂ Rn is µ-flat for some µ < 2√
, one
2
has
(11)
inf κ(v, w) ≥ c(1 − 8µ2 )1/2 .

A. Proof of Proposition III.5
By the µ-flatness assumption and as v, w ∈ S n−1 , one has
kvk∞ ≤ µ or kwk∞ ≤ µ
and thus
n
X
i=1

vi2 wi2 ≤ µ2 max(kvk22 , kwk22 ) = µ2 .

(13)

Set
Z = ha, viha, wi

(v,w)∈T∓

(14)

Proof of Theorem III.2:: We seek to apply Theorem III.3, and observe that
thus we need to bound the right hand side of (9) from
kZk2L2 = E |ha, viha, wi|2
below. Applying Proposition III.4 yields a lower bound of
n
X
c(1−8µ2 )1/2 for the first summand. For the second summand,
=E
ai aj ak aℓ vi vj wk wℓ
we ignore the µ-flatness, which can only make ρT,m larger
i,j,k,ℓ=1
and hence the bound smaller. The resulting setup is exactly
n
n
n
i
h X
X
X
the same as in [17], so the bounds from Sections 3.3.1 and
a2i a2k vi2 wk2 + a4i vi2 wi2
= E 2 a2i a2j vi vj wi wj +
3.3.2 in [17] directly imply
i=1
i,j=1
i,k=1
q
q
i6=j
i6=k
k log(en/k) k log(en/k)
n
n
n
n
ρTµ ,m . m + m and ρTµ,k ,m .
+
.
X
X
m
m
2
(E a4i − 1)vi2 wi2
vi2 wi2 +
= 1 + 2hv, wi − 2
Noting that in both cases, for our choice of m, the square root
i=1
i=1
is of leading order, (9) yields the result.
≥ 1 − 2µ2 .
(15)
C. The Noisy Case
In [17], also an analysis of the case of phase retrieval
with noise is presented. The results are technically somewhat
more involved. It should be noted, however, that again the
only place where additional assumptions on the measurement
vectors enter is that they ensure a lower bound of κ.
A minor difference from the noise-free case is that in this
s
, t ), s, t ∈ T
framework, one needs a bound on κ( ksk
2 ktk2
s−t
rather than κ( ks−tk
, s+t ) (both in terms of the definition
2 ks+tk2
of κ given above, which is slightly different from the one in
[17]). We obtain the following bound for the noisy case:
Proposition III.5. For each L > 0 there exists a constant
c > 0 such that the following holds. Consider a random vector
a with independent L-subgaussian entries ai with mean zero
and unit variance. Let κ be defined as in equation (8). Then
if v, w ∈ S n−1 and at least one of them is µ-flat for some
µ < √12 , one has
κ(v, w) ≥ c(1 − 2µ2 )1/2 .

(12)

s
t
Taking the infimum over all v = ksk
, w = ktk
for
2
2
s, t ∈ T yields analogous results to those in [17] for the noisy
case with independent measurement entries, where no small
ball probability or moment assumptions are required provided
T is µ-flat. Again, the stability constant has an additional
factor of (1−8µ2)1/2 . To prove the proposition, the ingredients
necessary in addition to the proof in [17] are exactly the same
as in the noise-free case discussed in Theorem III.2 above. We
thus refrain from repeating these details.

IV. L OWER - BOUNDS ON κ
Here we prove the lower-bounds on κ that are used to show
stable uniqueness. We will first prove Proposition III.5, then
use it to show Proposition III.4.

Here the third equality uses that due to the independence
assumption, all summands where an ai appears in first power
have zero mean, so only those terms with two different ai ’s
appearing as a square or just one ai appearing in fourth power
contribute to the sum. The fourth equality uses that the ai ’s
are all unit variance, and in the last inequality we use (13)
as well as the fact that a random variable’s fourth moment
always dominates its variance.
The result now follows tracing exactly the steps of Corollary
3.7 in [17].
B. Proof of Proposition III.4
Consider (v, w) ∈ T∓ . Then by definition, there exist
s−t
s+t
vectors s, t ∈ T such that v = ks−tk
and w = ks+tk
.
2
2
Using the triangle inequality, and the fact that s, t are µ-flat,
we have that:
ks + tk∞ ≤ µ(ksk2 + ktk2 ),

ks − tk∞ ≤ µ(ksk2 + ktk2 ).

(16)
(17)

Also, using the triangle inequality,
ks + tk2 + ks − tk2 ≥ k2sk2 ,
ks + tk2 + ks − tk2 ≥ k2tk2 ,

(18)
(19)

hence
ksk2 + ktk2 ≤ ks + tk2 + ks − tk2

≤ 2 max {ks + tk2 , ks − tk2 }.

(20)

Combining all of the above, we see that at least one of the
following inequalities must hold:
ks + tk∞ ≤ 2µks + tk2 ,
ks − tk∞ ≤ 2µks − tk2 .

(21)
(22)

This shows that at least one of s + t and s − t is 2µ-flat. The
result follows by applying Proposition III.5.

6

V. P HASE L IFT
Our second main result concerns the PhaseLift algorithm
[9], [10], [11]. PhaseLift (in the noiseless case) is based on a
matrix reformulation of the problem in terms of the rank one
matrix X = xxT , namely
find X ∈ Rn×n
such that X  0, rank(X) = 1,
tr(ai aTi X)

= yi

(23)

(∀i = 1, . . . , m).

Then one solves a convex relaxation of this problem:
find X ∈ Rn×n that minimizes tr(X)
such that X  0,
tr(ai aTi X) = yi

(24)

(∀i = 1, . . . , m).

b from which one extracts the leading
This yields a solution X,
eigenvector x̂; one hopes that x̂ ≈ x.
PhaseLift can be modified to handle noise in different ways;
in particular, one can solve the following convex program [11]:
find
s.t.

X ∈ Rn×n that minimizes

m
X
i=1

|tr(ai aTi X) − yi |

X  0.

(25)

A. Recovery of Non-Peaky Signals from Subgaussian Measurements
We assume that each measurement vector ai ∈ Rn is chosen
by sampling its entries aij (j = 1, 2, . . . , n) independently
from some subgaussian distribution D on R. We assume that
D has mean zero and variance 1. Also, we let C4 and Cψ2
denote its fourth moment and ψ2 -norm, respectively:6
E aij = 0,
C4 := E(a4ij ) ≥ 1,

E(a2ij ) = 1,
Cψ2 := kaij kψ2 .

(26)

We are interested in recovering signals that are non-peaky,
or µ-flat in the sense of Definition II.2. We show that, for any
choice of D, there is a constant µ ∈ (0, 1) such that, for all
sufficiently large n, PhaseLift achieves uniform recovery of
all µ-flat vectors in Rn , using m = O(n) measurements, in
the presence of noise.
This extends the order-optimal results of Candès and Li [11]
to a larger class of measurement distributions, at the expense
of a mild non-peakiness restriction on the class of vectors to
be recovered. We emphasize that there is no dependence of µ
on the dimension n.
More precisely, we prove:
Theorem V.1. Consider PhaseLift with noisy measurements,
as shown in equations (1) and (25). Let D be any subgaussian
distribution on R, with mean 0, variance 1, and parameters C4
and Cψ2 as shown in equation (26). Then there exist constants
0 < µ < 1 and κ0 > 1 such that the following holds.
For all n sufficiently large, and for all m ≥ κ0 n, with probability at least 1−e−Ω(n) (over the choice of the measurement
6 For

the definition of the ψ2 -norm, see, e.g., [21].

vectors ai ), PhaseLift achieves uniform recovery of all µ-flat
b
vectors in Rn : for all µ-flat vectors x ∈ Rn , the solution X
to equation (25) obeys

kwk1
,
(27)
m
where k·kF is the Frobenius norm, C0 is a universal constant,
b be the
and w is the noise term in equation (1). If we let x
b then x
b satisfies the bound
leading eigenvector of X,


kwk1
,
(28)
kb
x − eiφ xk2 ≤ C0 min kxk2 ,
mkxk2
b − xxT k ≤ C0
kX
F

for some φ ∈ [0, 2π].

Note that here the success probability is 1 − e−Ω(n) , rather
than 1−e−Ω(m) as in [11]. This is due to a technical difference
in the proof: in our setting, the sampling operator A satisfies
the desired injectivity properties with probability 1 − e−Ω(n) ,
rather than 1 − e−Ω(m) . However, note that the construction of
the dual certificate still succeeds with probability 1 − eΩ(m) ,
as needed in order to use the union bound over Rn . (See the
following section for details.)
B. Recovery of Arbitrary Signals from Bernoulli Measurements with Erasures
Next we consider a special class of subgaussian measurements, namely Bernoulli measurements with erasure probability p ∈ [0, 1]. We let each measurement vector ai ∈ Rn have
iid entries chosen from the following distribution:
 √

with probability (1 − p)/2,
1/ 1 − p
(29)
aij = 0
with probability p,

√

−1/ 1 − p with probability (1 − p)/2.
This distribution has the following properties:
E aij = 0,
C4 := E(a4ij ) =

1
1−p ,

E(a2ij ) = 1,
Cψ2 := kaij kψ2 ≤

√1 .
1−p

(30)

We consider the phase retrieval problem using these types of
measurements, for arbitrary signals x ∈ Rn (without any µflatness assumption). The basic question of stable uniqueness
was already settled by Eldar and Mendelson [17]: whenever
p > 0, the distribution of the aij satisfies their fourth-moment
condition, hence stable uniqueness holds. However, no recovery guarantees using PhaseLift were previously known.
Here we show that, in the particular case where p = 2/3,
PhaseLift achieves uniform recovery of all vectors in Rn , using
m = O(n) measurements, in the presence of noise.
Theorem V.2. Consider PhaseLift with noisy measurements,
as shown in equations (1) and (25). Let the ai ∈ Rn be
Bernoulli random vectors with erasure probability p = 2/3, as
shown in equation (29). Then there exists a constant κ0 > 1
such that the following holds.
For all n sufficiently large, and for all m ≥ κ0 n, with
probability at least 1 − e−Ω(n) (over the choice of the ai ),
PhaseLift achieves uniform recovery of all vectors in Rn .
b satisfies
Furthermore, for all x ∈ Rn , the PhaseLift solution X
the same error bounds as in Theorem V.1.

7

VI. P ROOF O UTLINE
We begin by describing the proof of Theorem V.1. (We
will prove Theorem V.2 later, in Section IX.) Our proof uses
the same overall strategy as in previous work on PhaseLift
[9], [10], [11], though new techniques are needed in several
places.
We begin by showing an injectivity
property of the sampling

operator A : X 7→ tr(ai aTi X) i∈[m] , but while this follows
from relatively straightforward arguments in [11], [10], [9], in
our setting we need to use more sophisticated arguments due
to Eldar and Mendelson [17] (including a bound on empirical
processes from [20]).
To characterize the solution of the PhaseLift convex program, we construct a dual certificate Y, which is similar to that
of Candès and Li [11] (see also similar work by Demanet and
Hand [10]). Because the ai are no longer Gaussian distributed,
our proofs are somewhatmore involved: we use various fourthmoment estimates, and large-deviation bounds for sums of
independent subgaussian and sub-exponential random vectors
[21].
A. Injectivity of the sampling operator
We define the sampling operator A : Rn×n → Rm as
follows:

(31)
A(X) = tr(ai aTi X) i∈[m] .

We will prove that A satisfies certain injectivity properties.
First, we need an upper bound on kA(X)k1 , which is a
straightforward generalization of the first half of Lemma 2.1
in [11], and of Lemma 3.1 in [9]:

Lemma VI.1. Let D be as in Theorem V.1. Then there exist
constants C > 0 and c > 0 such that the following holds.
Fix any 0 < δ < 12 , and assume that m ≥ 20(C/δ)2 n.
Let ε > 0 be the positive root of 14 δ = ε2 + ε, that is, ε =
√
1
−cmε2
2 (−1 + 1 + δ). Then with probability at least 1 − 2e
(over the choice of the ai ), the sampling operator A has the
property that:
1
m kA(X)k1

≤ (1 + δ) tr(X),

∀X  0.

(32)

The proof is identical to that of Lemma 3.1 in [9], but using
bounds on the singular values of random matrices whose rows
are independent subgaussian vectors (rather than Gaussian
vectors), as in Theorem 5.39 in [21].
Next we prove a lower bound on kA(X)k1 , which resembles
the second half of Lemma 2.1 in [11], and Lemma 3.2 in [9].
Our lemma differs from these previous works in that it only
applies to matrices X that lie in the tangent spaces T (x0 )
associated with µ-flat vectors x0 , rather than all matrices
X that are symmetric with rank 2. However, this lemma is
sufficient for our purposes.
Formally, fix some µ ∈ (0, 1), and let S(µ) be the set of
all µ-flat vectors:
S(µ) = {x ∈ Rn | kxk∞ ≤ µkxk2 }.

(33)

For any vector x0 ∈ S, define T (x0 ) to be the following
subspace of Rn×n :
T (x0 ) = {X ∈ Rn×n | X = xxT0 + x0 xT , x ∈ Rn }. (34)

We will prove:
Lemma VI.2. Let D be as in Theorem V.1. Then there exist
constants 0 < µ < 1, κ0 > 1, c > 0 and α > 0 such that the
following holds.
For all n sufficiently large, and for all m ≥ κ0 n, with probability at least 1 − e−cn (over the choice of the measurement
vectors ai ), the sampling operator A satisfies:
1
m kA(X)k1

≥ αkXk,

∀x0 ∈ S(µ)\{0},

∀X ∈ T (x0 )\{0}.
(35)

Note that here the constant α > 0 may be quite small, in
contrast to previous work [11] where this constant was close to
1. Because of this difference, we will have to construct a dual
certificate Y that satisfies kYT kF ≤ εT (for a small constant
3
as in [11]. (See Sections
εT > 0), rather than kYT kF ≤ 20
VI-B and VI-C for details.)
The proof of this lemma is different from [11], [9]. It uses
arguments due to Eldar and Mendelson, in particular a PaleyZygmund argument for lower-bounding an expectation value
of the form E |Z| (Lemma 3.6 in [17]), and a bound on the
suprema of certain empirical processes (Theorem 2.8 in [17],
see also [20]). The proof of this lemma is given in Section
VII.
Remark VI.3. Note that Lemma VI.2 crucially relies on
the assumption that x0 is µ-flat. For example, let the ai be
n
random Bernoulli measurements in {1, −1} , choose x0 =
T
T
T
(1, 1, 0, . . . , 0) , and let X = xx0 + x0 x ∈ T (x0 ) where
x = (1, −1, 0, . . . , 0)T . This yields A(X) = 0 (this follows
from (38) below, as for each of the ai , either aTi x or aTi x0
vanishes), so the conclusion of the Lemma does not hold.
B. Approximate dual certificates
Following [11], we will use approximate dual certificates
to characterize the solutions to the PhaseLift convex program.
First, we will show that, for any µ-flat vector x0 , with high
probability (over the choice of the measurement vectors ai ),
there exists an approximate dual certificate Y (for the vector
x0 ). We will then use the union bound over an ǫ-net on the
unit sphere S n−1 in Rn , together with a continuity argument
(which shows that any vector in S n−1 can be approximated
by a vector in the ε-net). This will prove a uniform guarantee:
with high probability (over the choice of the ai ), for all µ-flat
vectors x0 , there is a dual certificate Y.
For the first claim, we will prove a variant of Lemma 2.3
in [11]:
Lemma VI.4. Let D be as in Theorem V.1. Let 0 < εT ⊥ ≤ 1
and 0 < εT ≤ 1 be any constants. Then there exist constants
0 < µ < 1, κ0 > 1, c > 0 and B0 > 0 such that the following
holds.
For all sufficiently large n, and for all m ≥ κ0 n, let x0 ∈
S(µ) be any µ-flat vector, and let T = T (x0 ) be the tangent
space. Then with probability at least 1−e−cm (over the choice
of the measurement vectors ai ), there exists a dual certificate
Y ∈ Rn×n , which has the form Y = A∗ (λ), where kλk∞ ≤
B0
m , and which satisfies
kYT ⊥ + 2IT ⊥ k ≤ εT ⊥ ,

kYT kF ≤ εT .

(36)

8

Here, A∗ : Rm → Rn×n denotes the adjoint of the linear
operator A, YT denotes the projection of Y onto the subspace
T , and YT ⊥ denotes the projection of Y onto the subspace
T ⊥ , which is the orthogonal complement of T in Rn×n .
The proof of this lemma is given in Section VIII. The dual
certificate is constructed in a similar way to [11], but the
analysis is more involved. In particular, unlike the Gaussian
case studied in [11], here the distribution of the vectors ai
is not rotationally invariant. We use vector analogues of Hoeffding’s inequality and Bernstein’s inequality [21], combined
with fourth-moment estimates which depend on the µ-flatness
of the vector x0 .
From the above lemma, one concludes a uniform guarantee
on the existence of dual certificates for all µ-flat vectors x0 .
To see this, one first constructs a dual certificate for all points
x0 in an ǫ-net, via a union bound; second, one shows that this
dual certificate works well for all points x0 , using a continuity
argument. This part of the proof is identical to the proof of
Corollary 2.4 in [11], so we refrain from repeating the details.

comes from the Paley-Zygmund argument from reference [17]
(see equation (45)).
VII. I NJECTIVITY

OF THE SAMPLING OPERATOR

We now prove Lemma VI.2:
For any x0 ∈ S(µ) \ {0}, and any X ∈ T (x0 ) \ {0}, we
can write X = xxT0 + x0 xT . Since all the variables are real,
we can write
m
m
X
X
T
1
1
2
|tr(ai ai X)| = m
|aTi x||aTi x0 |.
m kA(X)k1 = m
i=1

i=1

(38)
Next we reduce to the case where kxk2 = kx0 k2 = 1. Let
S n−1 denote the unit sphere in Rn . For any v ∈ S n−1 , and
any v0 ∈ S(µ) ∩ S n−1 , define
Γ(v, v0 ) :=

1
m

m
X
i=1

|aTi v||aTi v0 |.

(39)

Then we can write
1
m kA(X)k1

C. Combining the pieces
We can characterize the solution of the PhaseLift convex
program, using the injectivity of the sampling operator A, and
the existence of a dual certificate Y. We restate the bound
proved in Section 2.3 in [11] (with more general choices for
the parameters):
Lemma VI.5. Suppose that the sampling operator A satisfies
equations (32) and (35), with parameters δ and α. Let x0
b be the solution of
be any µ-flat vector in Rn , and let X
the PhaseLift convex program with noisy measurements, as
in equations (1) and (25).
Suppose that there exists a dual certificate Y ∈ Rn×n
that satisfies YT ⊥  −IT ⊥ and kYT kF ≤ εT , where
α√
. Also suppose that Y has the form Y = A∗ (λ),
εT < (1+δ)
2
b must satisfy
where kλk ≤ B0 . Then X
∞

m

b − x0 xT k ≤ 2C0
kX
0 F

where C0 = (1 + εT )

α√
(1+δ) 2

− εT

kwk1
,
m

−1

(37)

1
( 1+δ
+ B0 ) + B0 .

The proof of this lemma is identical to that in [11]. By
combining this with the preceding lemmas, we prove Theorem
V.1.
Remark VI.6. Theorem V.1 shows that there exists some
constant µ > 0 such that PhaseLift succeeds in recovering
all µ-flat vectors. The specific value of µ depends on a few
factors. First, in Lemma VI.2, in order to show
√ injectivity of
the sampling operator, we must have µ < 1/ 2 (see equation
(45)). More importantly, in Lemma VI.4,p
in order to construct
the dual certificate, we need to set µ ≤ ε1 /|C4 − 3|, where
1
min {εT ⊥ , εT } (see equations (51) and (52)). The
ε1 = 20
specific values of εT ⊥ and εT are determined by Lemma VI.5:
α√
. The most important
they are εT ⊥ = 1 and εT < (1+δ)
2
factor in determining these values is α, which describes the
injectivity of the sampling operator in Lemma VI.2. This can
be estimated as α ≈ c1 , where c1 is a numerical constant that

x
= 2kxk2 kx0 k2 Γ( kxk
, kxx00k )
2

2

x
, kxx00k )kXk,
≥ Γ( kxk
2

(40)

2

where we used the fact that kXk ≤ kxxT0 k + kx0 xT k ≤
2kxk2 kx0 k2 .
Furthermore, define
κ(v, v0 ) := EA Γ(v, v0 )

(41)

and
δ :=

sup
v∈S n−1 , v0 ∈S(µ)∩S n−1

|Γ(v, v0 ) − EA Γ(v, v0 )|. (42)

Then we have
1
m kA(X)k1


x
≥ κ( kxk
, kxx00k ) − δ kXk.
2

2

(43)

We now proceed to bound κ(v, v0 ), using a version of the
Paley-Zygmund argument from Corollary 3.7 in [17]. We note
that κ(v, v0 ) can be written in terms of a single measurement
vector a, as follows:
κ(v, v0 ) = Ea |aT v||aT v0 | = E |Z|,
T

(44)

T

where Z := (a v)(a v0 ). Using (15), we have that kZkL2 ≥
p
1 − 2µ2 .
Now fix any q > 2. Using the same argument as in Corollary
3.7 in [17], we have that kZkLq ≤ Cq , where Cq < ∞
depends only on the parameter q and the distribution D (and
not on the dimension n). Finally, using Lemma 3.6 in [17],
we get that
p
κ(v, v0 ) = E |Z| ≥ c1 kZkL2 ≥ c1 1 − 2µ2 ,
(45)
where c1 > 0 depends only on the choice of q and the
distribution D (and not on the dimension
n). We assume that
√
µ is a constant satisfying µ < 1/ 2; then κ(v, v0 ) is lowerbounded by a constant that is strictly greater than 0.
Next, we will upper-bound δ, by bounding the supremum
of an empirical process, using Theorem 2.8 in [17] (see also
[20]). Here the empirical process is indexed by two sets T1 =

9

S n−1 and T2 = S(µ) ∩ S n−1 . We define the diameter of a
set T ⊂ Rn to be d(T ) = supt∈T ktk2 . So for the sets T1
and T2 , we have d(T1 ) = d(T2 ) = 1. We define the Gaussian
complexity of a set T ⊂ Rn to be ℓ(T ) = Eg supt∈T |gT t|,
where g is a Gaussian random vector in Rn with mean 0 and
covariance matrix I. The Gaussian complexities
of T1 and T2
√
can be bounded by ℓ(T2 ) ≤ ℓ(T1 ) ≤ n (see, e.g., Section
3.3.1 in [17]).
Now Theorem 2.8 in [17] implies that there exist constants
c1 , c2 > 0 and c3 (which depend on the distribution D, but
not on the dimension n) such that the following holds: for all
u ≥ c1 , with probability at least 1 − 2 exp(−c2 u2 min {m, n})
(over the choice of the measurement vectors ai ), we have that
q
n
n
+m
).
(46)
δ ≤ c3 u 3 ( m
Now set u to be constant, and set m ≥ κ0 n. Then we have
δ ≤ c3 u3 ( √1κ0 + κ10 ). By choosing κ0 large, we can make δ
arbitrarily small.
Now substitute equations (45) and 46 into (43). This completes the proof of Lemma VI.2. 
VIII. C ONSTRUCTING

We now prove Lemma VI.4:
Part 1: We first show some properties of the distribution D.
We claim that for any δct > 0, we can define a cutoff radius
Rct > 0 such that, for any x ∈ S n−1 , we have

where c > 0 is an absolute constant. Then set Rct to be:
(49)

We will set δct small enough to satisfy various bounds that
are needed in the proof, in particular, equations (84), (89) and
(110).
We now calculate certain fourth moments of the ai , namely
E[(aTi x0 )4 ], E[(aTi x0 )2 (aTi v)2 ] and E[(aTi x0 )3 (aTi v)] (where
v ∈ Rn is a unit vector orthogonal to x0 ). We show that when
the vector x0 is µ-flat, these moments have approximately the
same values as if ai were a Gaussian random vector. This is
the key fact that allows us to apply the proof techniques from
[11] in this more general setting.
First, let x0 be a “µ-flat” signal, and assume without loss
of generality that kx0 k2 = 1. We consider the 4th moment of
aTi x0 , and we write
E[(aTi x0 )4 ] = E
=

X

n
 X
j=1

E[a4ij ]x40j

+3

j

=

X
j

=

X
j

aij x0j
X

4 

(C4 −

+3

X

(C4 − 3)x40j + 3.

jk

(50)
x20j x20k

n

min {εT ⊥ , εT }.

(52)

Next, let v ∈ R be a unit vector orthogonal to x0 , i.e.,
kvk2 = 1 and vT x0 = 0. We calculate the following mixed
4th moment of ai :
E[(aTi x0 )2 (aTi v)2 ]
X
E[a4ij ]x20j vj2 +
=
j

X

E[a2ij ] E[a2ik ](x20j vk2 + x0j x0k vj vk + x0j x0k vk vj )

j6=k

= (C4 − 3)
= (C4 − 3)

X

x20j vj2 +

j

X

(x20j vk2 + 2x0j x0k vj vk )

jk

X

x20j vj2

j

X

2

2

+ kx0 k2 kvk2 + 2(xT0 v)2

x20j vj2 + 1.

j

(53)
In the special case where ai is a Gaussian random vector, we
have C4 = 3 and E[(aTi x0 )2 (aTi v)2 ] = 1. In general, we have
2

2

|E[(aTi x0 )2 (aTi v)2 ] − 1| ≤ |C4 − 3| kx0 k∞ kvk2
≤ |C4 − 3| µ2 = ε1 .

(54)

Finally, we calculate another mixed 4th moment of ai :
E[(aTi x0 )3 (aTi v)]
X
X
E[a4ij ]x30j vj + 3
E[a2ij ] E[a2ik ]x20j x0k vk
=
j

= (C4 − 3)
= (C4 − 3)
= (C4 − 3)

X

j6=k

x30j vj

+3

j

X

x20j x0k vk

jk

x30j vj

+

j

X

X

(55)

2
3kx0 k2 (xT0 v)

x30j vj .

j

In the special case where ai is a Gaussian random vector, we
have C4 = 3 and E[(aTi x0 )3 (aTi v)] = 0. In general, we have
2

|E[(aTi x0 )3 (aTi v)]| ≤ |C4 − 3| kx0 k∞ kx0 k2 kvk2
≤ |C4 − 3| µ2 = ε1 .

E[a2ij ] E[a2ik ]x20j x20k

j6=k

3)x40j

1
20

ε1 =

(47)

To see this, use a Hoeffding-type inequality (Prop. 5.10 in
[21]):
(48)
Pr[|aTi x| ≥ Rct ] ≤ e · exp(−cRct2 /Cψ2 2 ),
Rct = ( 1c ln( δect ))1/2 Cψ2 .

Note that we can choose µ > 0 to be small, in order to make
ε1 an arbitrarily small constant. In particular, let us choose µ
small enough so that:

= (C4 − 3)

THE DUAL CERTIFICATE

Pr[|aTi x| ≥ Rct ] ≤ δct .

In the special case where ai is a Gaussian random vector, we
have C4 = 3 and E[(aTi x0 )4 ] = 3. In the general case, we
can use the µ-flatness of x0 to show that E[(aTi x0 )4 ] ≈ 3, as
follows:
|E[(aTi x0 )4 ] − 3| ≤ |C4 − 3| kx0 k2∞ kx0 k22
(51)
≤ |C4 − 3| µ2 =: ε1 .

(56)

Part 2: We now construct the dual certificate Y, following
the same approach as [11]. Without loss of generality, we can
assume kx0 k2 = 1. We construct Y as follows:
Y :=

m
X
i=1

λi ai aTi ,


1 T
λi :=
(ai x0 )2 1[|aTi x0 | ≤ Rct ] − β0 ,
m

(57)

10

where we set
β0 := E[(aT1 x0 )4 1[|aT1 x0 | ≤ Rct ]].

(58)

This choice of β0 ensures that E xT0 Yx0 = 0, which will be
useful later.
Note that β0 ≈ E[(aT1 x0 )4 ] ≈ 3, and note that this implies
1
1
(Rct2 + β0 ) ≤ O( m
). In order to make this rigorous,
|λi | ≤ m
we can bound β0 as follows. First define
=

≤
≤
≤

1

(59)

1
20 εT ⊥ .

1
10 εT ⊥ .

1 X T
(a x0 )2 1[|aTi x0 | ≤ Rct ] ai aTi ,
m i=1 i
m

Y

1 X
β0 ai aTi .
:=
m i=1

(61)

(62)

Part 3: First, we want to show that YT ⊥ + 2IT ⊥ is small.
We can write
(0)

(1)

kYT ⊥ + 2IT ⊥ k ≤ kYT ⊥ − IT ⊥ k + kYT ⊥ − 3IT ⊥ k. (63)
(1)

We begin by showing that YT ⊥ − 3IT ⊥ is small — this is
the second term in (63). This uses a similar argument to [11],
with more general bounds for subgaussian random matrices
[21]. We can write
Y

(1)

=

√C
κ0

≤

1
15 εT ⊥ .

(68)

(1)

kYT ⊥ − 3IT ⊥ k ≤ kYT ⊥ − β0 IT ⊥ k + ε1 + εct
≤ kY(1) − β0 Ik + ε1 + εct

≤

≤

≤

1
15 εT ⊥ β0 + ε1 + εct
1
15 εT ⊥ (3 + ε1 + εct )
1
1
5 εT ⊥ + (1 + 15 )(ε1

+ ε1 + εct

(69)

+ εct )

< (0.31) εT ⊥ .
(0)

m

(1)

(67)

(60)

We now show that Y has the desired properties. To do this,
it is convenient to write Y = Y(0) − Y(1) , where
Y(0) :=

1
km
AT A − Ik ≤ 3 max {2ε0 , (2ε0 )2 } ≤ 6ε0 =

(1)

Combining with equation (51), we see that
|β0 − 3| ≤ ε1 + εct ≤

1
km
AT A − Ik ≤ 3 max { √Cκ0 + ε0 , ( √Cκ0 + ε0 )2 }.

This implies

where we used the Cauchy-Schwarz inequality and standard
properties of subgaussian random variables, and where C0 is
some universal constant (see Lemma 5.9 in [21]). Note that,
by choosing Rct sufficiently large, we can make δct , and hence
εct , an arbitrarily small constant. In particular, let us choose
Rct large enough so that
εct =

1 − C √1κ0 − ε0 ≤ smin ( √Am ) ≤ smax ( √Am ) ≤ 1 + C √1κ0 + ε0 .
(66)
This implies (using Lemma 5.36 in [21]) that

1
εT ⊥ , and set κ0 large enough so that
Now set ε0 = 90
ε0 . Then we have

β01 := E[(aT1 x0 )4 ] − β0

E[(aT1 x0 )4 [|aT1 x0 | > Rct ]]
E[(aT1 x0 )8 ]1/2 Pr[|aT1 x0 | > Rct ]1/2
4 √ 4 1/2
kaT1 x0 kψ2 8 δct
1/2
C02 Cψ4 2 · 64δct =: εct ,

√
We restate this as follows, substituting t = ε0 m: for all
ε0 ≥ 0, with probability ≥ 1 − 2 exp(−cε20 m), A satisfies

T
1
m β0 A A,

Next, we will show that YT ⊥ − IT ⊥ is small — this is the
first term in (63). This requires a more involved argument. We
(0)
can write YT ⊥ in the form:
m

(0)

YT ⊥ =

ξ i := (aTi x0 )1[|aTi x0 | ≤ Rct ](Π0 ai ),

(70)
where Π0 = I − x0 xT0 is the projector onto the subspace
orthogonal to x0 . As in [11], the random variables ξi are
subgaussian, but now there is an added complication, because
the ξ i may have nonzero mean and may not be isotropic. We
will show that the contributions due to the nonzero means and
anisotropy are small, hence the argument from [11] can be
adapted to this situation.
We first shift the ξ i , in order to get centered random
variables ζ i with E ζ i = 0, that is:
ζ i := ξ i − µi ,
We then define

µi := E ξ i .

(71)

m

Z :=

(64)

where A is a random m-by-n matrix whose i’th row is the
vector aTi . Note that E Y(1) = β0 I and E A = 0. Using
standard bounds on the singular values of random matrices
with independent subgaussian rows (Lemma 5.39 in [21]), we
get that there exist constants C > 0 and c > 0 (which depend
only on the subgaussian norm of the rows, given by C4 ), such
that for all t ≥ 0, with probability ≥ 1 − 2 exp(−ct2 ), A
satisfies
√
√
√
√
m − C n − t ≤ smin (A) ≤ smax (A) ≤ m + C n + t,
(65)
where smax (A) and smin (A) denote the largest and smallest
singular values of A.

1 X
ξ ξT ,
m i=1 i i

1 X
ζ ζT .
m i=1 i i

(72)
(0)

We claim, first, that Z is a good approximation to YT ⊥ ;
second, that the ζ i are approximately isotropic, so E Z will
be close to IT ⊥ ; and third, that Z is concentrated around its
expectation E Z. Finally, we will use these claims to upper(0)
bound YT ⊥ − IT ⊥ , as follows:
(0)

(0)

kYT ⊥ − IT ⊥ k ≤ kYT ⊥ − Zk + kZ − E Zk + kE Z − IT ⊥ k
(73)
(0)
We begin by upper-bounding YT ⊥ − Z (the first term in
(73)). The first step is to upper-bound the µi . We write
ξi = θi − ν i ,

(74)

11

where θi = (aTi x0 )(Π0 ai ) and ν i = (aTi x0 )1[|aTi x0 | >
Rct ](Π0 ai ). For any v ∈ S n−1 such that vT x0 = 0, we have
E[vT θ i ] = E[(aTi x0 )(vT ai )] = vT E[ai aTi ]x0 = vT x0 = 0,
(75)
and using equation (54), we have


|vT E ν i | = E (aTi x0 )1[|aTi x0 | > Rct ](vT ai )

≤ E[(aTi x0 )2 (vT ai )2 ]1/2 Pr[|aTi x0 | > Rct ]1/2
p
√
≤ 1 + ε1 δct ,
(76)
√
√
hence we conclude that E θi = 0, kE ν i k2 ≤ 1 + ε1 δct ,
and
p
√
kµi k2 ≤ 1 + ε1 δct .
(77)
(0)

We can now bound YT ⊥ − Z as follows:
(0)
kYT ⊥

− Zk =
=

1
km

m
X

(ζ i µTi

i=1
m
X

1
k( m

1
≤ 2 km

ζ i )µT1

i=1
m
X
i=1
m
X

1
≤ 2 km

+

i=1

µi ζ Ti

+

+

1
µ1 ( m

T

ζ i) +

µ1 µT1 k

2

1 + ε1

p
δct + (1 + ε1 )δct .

(78)

1 Pm
We will bound k m
i=1 ζ i k2 using a Hoeffding-type inequality for subgaussian random vectors (Lemma A.1). Note
that the ζ i are independent, centered random variables taking
values in span(x0 )⊥ ⊂ Rn , and they are subgaussian with
norm

kζ i kψ2 ≤ kξ i kψ2 + kµi kψ2
p
√
≤ Rct CCψ2 + 1 + ε1 δct =: K.

(79)

Using Lemma A.1, we have that there exists a universal
constant c > 0 such that, for all t ≥ 0 and all 0 < ε < 1,
1
Pr[k m

m
X
i=1

ζ i k2 ≥

1
1−ε t]

≤ e · exp n ln( 3ε ) −

ct2
K2 m


. (80)

Setting ε = 12 and t = K(1 − ε), and recalling that m ≥ κ0 n,
we get that:
1
Pr[k m

m
X
i=1

ζ i k2 ≥ K] ≤ e · exp

ln(6)
κ0 m

E Z = E ζ i ζ Ti = E ξ i ξ Ti − µi µTi ,

(85)

E ξ i ξ Ti = E θ i θTi − E θ i ν Ti − E ν i θ Ti + E ν i ν Ti

ζ i k2 kµ1 k2 + kµ1 k2
√

Next, we show that E Z is close to IT ⊥ (corresponding to
the third term in (73)). First we write

2

i=1

ζ i k2

This quantity can be made arbitrarily small, by choosing δct to
be a sufficiently small constant. In particular, we set δct small
enough that
(0)
1
kYT ⊥ − Zk ≤ 10
εT ⊥ .
(84)

and note that kµi µTi k = kµi k2 ≤ (1 + ε1 )δct . Next we write

µi µTi )k

m
X

the definition of K in equation (79), and setting Rct as a
function of δct as specified in equation (49), we get that
p
√
(0)
kYT ⊥ − Zk ≤ 2K 1 + ε1 δct + (1 + ε1 )δct
p
√
≤ 2Rct CCψ2 1 + ε1 δct + 3(1 + ε1 )δct
p
√
≤ 2( 1c ln( δect ))1/2 Cψ2 2 C 1 + ε1 δct + 3(1 + ε1 )δct .
(83)


− 4c m .

ln(6)
κ0

<
By setting κ0 is sufficiently large so that
that:
m
X
1
ζ i k2 ≥ K] ≤ exp(−Ω(m)).
Pr[k m

c
4,

(81)

= E θ i θTi − E ν i ν Ti ,

(86)

using the fact that θ i ν Ti = ν i θTi = ν i ν Ti . For any v ∈ S n−1
such that vT x0 = 0, we have
vT E[θi θTi ]v = E[(aTi x0 )2 (vT ai )2 ] ∈ [1 − ε1 , 1 + ε1 ], (87)
and using the same argument as in equation (59), we have


|vT E[ν i ν Ti ]v| = E (aTi x0 )2 1[|aTi x0 | > Rct ](vT ai )2

≤ E[(aTi x0 )4 (vT ai )4 ]1/2 Pr[|aTi x0 | > Rct ]1/2
1/2

≤ E[(aTi x0 )8 ]1/4 E[(vT ai )8 ]1/4 δct
1/2

≤ C02 Cψ4 2 · 64δct

≤ εct ,

(88)

hence we conclude that kE θi θTi − IT ⊥ k ≤ ε1 and
kE ν i ν Ti k ≤ εct . Combining these pieces, and setting δct
sufficiently small, we get that
kE Z − IT ⊥ k ≤ ε1 + εct + (1 + ε1 )δct
≤

≤

1
10 εT ⊥
1
5 εT ⊥ .

+ (1 + ε1 )δct

(89)

Finally, we will upper-bound Z − E Z (the second term in
(73)). To accomplish this, we will whiten the random variables
ζ i , to make them isotropic. We consider the covariance matrix
of the ζ i , and we compute its spectral decomposition,
E Z = E ζ i ζ Ti =: QDQT .

(90)

we get

Then we transform each ζ i to get an isotropic random variable
ϕi :
ϕi := D−1/2 QT ζ i ,
(91)

(82)

where Q, D and D−1/2 are understood to act on the subspace
orthogonal to x0 . We also define

i=1

Thus,
Pm with probability ≥ 1 − exp(−Ω(m)), we have that
1
km
i=1 ζ i k2 ≤ K. Plugging this into equation (78), using

m

F :=

1 X
ϕ ϕT ,
m i=1 i i

(92)

12

so we have E F = IT ⊥ . We can then upper-bound Z − E Z as
follows:

is bounded by Rct4 , and the second term is the square of a
subgaussian random variable. In particular, we can write

kZ − E Zk = kQD1/2 (F − IT ⊥ )D1/2 QT k
≤ kDk kF − IT ⊥ k

kξi kψ1 ≤ Rct4 + β0 k(aTi x0 )2 kψ1

≤ (1 +

1
5 εT ⊥ ) kF

(93)

− IT ⊥ k,

where we used equation (89).
1 Pm
T
We can now bound F = m
i=1 ϕi ϕi as follows. Note
that the ϕi are subgaussian, with norm
kϕi kψ2 ≤ kD−1/2 kkζ i kψ2
kξ i kψ + kµi kψ2
≤ q2
1 − 15 εT ⊥
√
√
Rct CCψ2 + 1 + ε1 δct
q
≤
,

which is constant with respect to n. We bound F using the
same argument that led to equation (69). We get that there exist
constants C > 0 and c > 0 (which depend only on kϕi kψ2 ),
such that for all ε0 ≥ 0, with probability ≥ 1−2 exp(−cε20 m),
F satisfies
kF − IT ⊥ k ≤ 6ε0 .
(95)
1
30 εT ⊥ .

(96)

≤ (0.24) εT ⊥ .

Combining equations (73), (84), (89) and (96), we see that
with probability ≥ 1 − e−Ω(m) , we have
(0)

1
εT ⊥ + 15 εT ⊥ + (0.24) εT ⊥
kYT ⊥ − IT ⊥ k ≤ 10
= (0.54) εT ⊥ .

(97)

kYT ⊥ + 2IT ⊥ k ≤ (0.31) εT ⊥ + (0.54) εT ⊥ = (0.85) εT ⊥ ,
(98)
as desired.
Part 4: We now want to bound YT . Following [11], we
can write
2

where we used Lemmas 5.14 and 5.24 in [21], and C is
some universal constant. Thus we can use a Bernstein-type
inequality (Cor. 5.17 in [21]) to bound xT0 Yx0 . We get that
there exists a universal constant c > 0 such that, for all ε ≥ 0,
ε
Pr[|xT0 Yx0 | ≥ ε] ≤ 2 exp(−c min { K
2,

2

kYT kF = |xT0 Yx0 | + 2kΠ0 Yx0 k2 ,

(99)

where Π0 = I − x0 xT0 is the projector onto span(x0 )⊥ , and
we assume (without loss of generality) that kx0 k2 = 1. We
will bound each term in equation (99) separately.
For the first term in (99), we use same argument as in [11].
We can write
m
1 X
ξi ,
(100)
xT0 Yx0 =
m i=1
where ξi := (aTi x0 )4 1[|aTi x0 | ≤ Rct ] − β0 (aTi x0 )2 . Note that
E ξi = 0, by our choice of β0 in equation (58). Furthermore,
ξi is a sub-exponential random variable, since the first term

ε
K }m).

(102)

Now set ε = 12 εT . Then, with probability ≥ 1 − exp(−Ω(m)),
we have
|xT0 Yx0 | < 21 εT .
(103)
For the second term in (99), we need to use a different
argument. The proof in [11] uses the fact that aTi x0 and Π0 ai
are independent random variables, when ai is sampled from a
spherical Gaussian distribution; but this no longer holds in our
setting. Instead, we give a more general argument. We write
m

1 X
si − ti ,
Π0 Yx0 =
m i=1

(104)

where si := (aTi x0 )3 1[|aTi x0 | ≤ Rct ](Π0 ai ), and ti :=
β0 (aTi x0 )(Π0 ai ). We note that si is a subgaussian random
vector and ti is a sub-exponential random vector. We then use
a Bernstein-type inequality (for vectors rather than scalars) to
bound Π0 Yx0 .
To make this precise, we define centered random variables
ui = si − ti − E si + E ti , and we write
m

Finally, combining equations (63), (69) and (97), we see
that with probability ≥ 1 − e−Ω(m) ,

2

=: K,

This implies the

kZ − E Zk ≤ 51 εT ⊥ (1 + 15 εT ⊥ )

(101)

≤ Rct4 + 2β0 C 2 Cψ2 2

2

(94)

4
5

In particular, we can set ε0 =
following bound on Z − E Z:

2

≤ Rct4 + 2β0 kaTi x0 kψ2

Π0 Yx0 =

m

1 X
1 X
ui +
(E si − E ti ).
m i=1
m i=1

(105)

We begin by calculating E si and E ti . Let us write si as a
difference of two terms,
si = si0 − si1 ,

(106)

where we define si0 := (aTi x0 )3 (Π0 ai ) and si1 :=
(aTi x0 )3 1[|aTi x0 | > Rct ](Π0 ai ). Now consider any vector
v ∈ S n−1 such that vT x0 = 0. We have the following bounds:
|vT (E si0 )| = |E[(aTi x0 )3 (vT ai )]| ≤ ε1 ,

(107)

where we used equation (56);
|vT (E si1 )| = |E[(aTi x0 )3 (vT ai )1[|aTi x0 | > Rct ]]|

≤ E[(aTi x0 )6 (vT ai )2 ]1/2 Pr[|aTi x0 | > Rct ]1/2
1/2

≤ E[(aTi x0 )12 ]1/4 E[(vT ai )4 ]1/4 δct
√
√
1/2
≤ (kaTi x0 kψ2 12)3 (kvT ai kψ2 4) δct
√
1/2
≤ (CCψ2 )4 (48 3) δct ,

(108)

13

where we used standard properties of subgaussian random
variables, with C a universal constant; and
vT (E ti ) = E[β0 (vT ai )(aTi x0 )]
= β0 vT E[ai aTi ]x0 = β0 vT x0 = 0.

(109)

≤

=

1
20 εT
1
4 εT ,

+ 51 εT

(110)

(111)

Next, we note that si and ti are sub-exponential random
vectors, whose norms are bounded by:
ksi kψ1 = sup kvT si kψ1 ≤ sup kvT si kψ2
v∈S n−1

v∈S n−1
3
T
Rct kv Π0 ai k ≤ Rct3 CCψ2 ,

(118)

Finally we combine equations (105), (110), (111) and
(118) to get a bound on Π0 Yx0 : with probability ≥ 1 −
exp(−Ω(m)), we have

where we chose δct sufficiently small; and we conclude that
E ti = 0.

m

 1 X
ui k2 ≥ 14 εT ≤ exp(−Ω(m)).
Pr k m
i=1

Thus we conclude that E si is bounded as follows:
kE si k2 ≤ kE si0 k2 + kE si1 k2
√
1/2
≤ ε1 + (CCψ2 )4 (48 3) δct

Now set t = 14 εT . Then there exists some (sufficiently large)
constant κ0 > 0 such that

kΠ0 Yx0 k2 ≤ 14 εT + 41 εT = 21 εT .

(119)

Combining equations (99), (103) and (119), we get the
following bound on YT : with probability ≥ 1 − e−Ω(m) ,
kYT k2F ≤ 41 ε2T + 2 · 14 ε2T = 43 ε2T .

(120)

This completes the proof. 
IX. P ROOF

OF

T HEOREM V.2

(112)

To prove Theorem V.2, we follow the same strategy used
to prove Theorem V.1, as described in the preceding sections.
Now the measurement vectors ai ∈ Rn are Bernoulli random
and
vectors with erasures, which are a special case of the subgauskti kψ1 = sup kvT ti kψ1
sian random vectors considered previously; hence most of the
v∈S n−1
proof goes through in the same way as before.
T
T
(113)
≤ sup 2β0 kai x0 kψ2 kv Π0 ai kψ2
The present situation is different, however, in that the signal
v∈S n−1
x ∈ Rn is no longer assumed to be µ-flat. This affects Lemma
2
≤ 2(3 + ε1 + εct )(CCψ2 ) ,
VI.2 (injectivity of the sampling operator) and Lemma VI.4
where C is a universal constant, and we used standard prop- (construction of the dual certificate). We claim that, if the ai
erties of sub-exponential random variables. 7
are Bernoulli random vectors with erasure probability p =
This implies that the ui are sub-exponential, with norm
2/3, then we can set µ = 1 in both of these lemmas, so that
both
lemmas now apply to all x (as the µ-flatness condition
kui kψ1 ≤ ksi kψ1 + kti kψ1 + kE si k2
is
trivially
satisfied).
≤ Rct3 CCψ2 + 2(3 + ε1 + εct )(CCψ2 )2 + εcolumn1
In the original proofs of these two lemmas, the µ-flatness
=: K.
conditions are used via equations (15), (51), (54) and (56),
(115) which bound certain 4th moments of the ai , involving proP
jections onto vectors v that are µ-flat. We claim that similar
m
1
We will now bound m
i=1 ui , using a Bernstein-type inequality (Lemma A.2). We get that, for any t ≥ 0 and any bounds hold in our new situation (where the ai are Bernoulli
random vectors with erasure probability p = 2/3, and we
0 < ε < 1,
allow the vector v to be arbitrary).
m


 1 X
2
To see this, note that when p = 2/3, the aij have mean
1
ui k2 ≥ 1−ε
t ≤ 2 exp n ln( 3ε )−c min { Kt 2 , Kt }m ,
Pr k m
2
E
a
ij = 0, variance E(aij ) = 1 and fourth moment C4 :=
i=1
1
4
(116) E(aij ) = 1−p = 3, which are the same as the moments of
where c > 0 is a universal constant. We set ε = 12 , substitute the Gaussian distribution. Intuitively, this means that the ai
behave like Gaussian random vectors, which are rotationally
t 7→ t(1 − ε), and recall that m ≥ κ0 n; this gives
symmetric in Rn . Thus, there is no pathological behavior in
m


 1 X
1
t2
t
ui k2 ≥ t ≤ 2 exp κ0 ln(6)m−c min { 4K 2 , 2K }m the
. 4th moments of the ai , when one projects onto a direction
Pr k m
v that is not µ-flat.
i=1
(117)
To make this rigorous, we can redo the calculation of
equation (15) as follows: for any v, w ∈ S n−1 ,
7 In particular, note that for any two scalar-valued random variables X and
≤ sup

v∈S n−1

Y,

p 1/p

kXY kψ1 = sup

1
p

E[|XY | ]

≤ sup

1
p

E[|X|2p ]1/2p E[|Y |2p ]1/2p

p≥1

p≥1

≤ 2 sup
p≥1

(114)
√1
2p

2p 1/2p

E[|X| ]

≤ 2kXkψ2 kY kψ2 .

sup
q≥1

√1
2q

2q 1/2q

E[|Y | ]

E[(aTi v)2 (aTi w)2 ]
n
X
X
X
vi2 wi2 +
vi2 wj2 + 2
(vi wi )(vj wj )
= C4
i=1

= (C4 − 3)

n
X

i6=j

i6=j

vi2 wi2

kvk22 kwk22

i=1
T
2

= 1 + 2(v w) .

+

T

2

+ 2(v w)

(121)

14

Note that this bound holds for arbitrary unit vectors v and w,
which need not be µ-flat. This bound serves the same purpose
as equation (15). When we set v = w, this bound serves the
same purpose as equation (51). When we choose v and w
that are orthogonal, this bound serves the same purpose as
equation (54).
Finally, we can redo the calculation of equation (56) as
follows: for any v, w ∈ S n−1 ,
E[(aTi v)3 (aTi w)]
X
X
vj3 wj + 3
vj2 vk wk
= C4
j

= (C4 − 3)
= (C4 − 3)

X
j

X

j6=k

vj3 wj

+3

X

vj2 vk wk

(122)

jk

vj3 wj + 3kvk22 (vT w)

j

T

= 3(v w).
Again, this holds for arbitrary unit vectors v and w, which
need not be µ-flat. When we choose v and w that are
orthogonal, this bound serves the same purpose as equation
(56).
Following these changes, the rest of the proof goes through
as before.
X. D ISCUSSION
Broadly speaking, in this paper we have investigated the
power of subgaussian measurements for phase retrieval. It is
known that for certain natural classes of subgaussian measurements, such as Bernoulli random vectors, phase retrieval is
impossible, in that certain signals can never be distinguished
without unambiguity. We have shown that a large class of
signals, namely those that are “non-peaky” (more precisely,
those that are µ-flat), can still be recovered in this setting. This
µ-flatness condition, where µ can be a constant independent
of the dimension n, is surprisingly weak. We have extended
recent results on stable uniqueness [17] and PhaseLift [11] to
this setting.
In addition, we have shown that for one particular example
of a subgaussian measurement distribution, namely Bernoulli
random vectors with erasures, one does not need any µ-flatness
restriction at all: PhaseLift can recover all vectors in Rn , using
m = O(n) measurements. This is close to the informationtheoretic lower-bound.
Our proof is based on a dual certificate argument, and it is an
interesting question whether similar or better results could be
derived using Mendelson’s small ball method [6]. Indeed, the
small ball method is known to yield stronger results in other
scenarios, especially when the measurements are affected by
noise. However, it is not a priori clear how to incorporate our
non-peakiness condition into the framework of the small ball
method. The small ball method analyzes the measurements
corresponding to a matrix X that lies in the descent cone
of the nuclear norm, rather than the tangent space. Thus X
need not be of the form xxT0 + x0 xT , and it may have rank
greater than two. Hence it is difficult to even precisely capture
the µ-flatness assumption in this framework. In our opinion,

formulating and applying the small ball method for non-peaky
signals is a very interesting direction for follow-up work. With
such an approach, it may even be possible to generalize our
strategy to measurements with non-vanishing mean, such as
0/1 Bernoulli measurements, as has been successfully done in
the context of sparse recovery [23].
It would also be interesting to understand better what
conditions on the measurements ai and the signal x are
necessary and sufficient for phase retrieval. For example, Eldar
and Mendelson’s small-ball and fourth-moment conditions
involve the ai , while our µ-flatness condition involves x.
Both of these seem to be special cases of some more general
conditions that involve the ai and x jointly. In particular,
these conditions seem to involve certain fourth moments of
the ai projected onto directions that depend on x, as seen
in equations (15), (51), (54) and (56). Understanding these
conditions may be helpful for generalizing our results to other
types of measurements, and other classes of signals.
Acknowledgements: Our work on this paper was stimulated
by the Oberwolfach mini-workshop Mathematical Physics
meets Sparse Recovery in April 2014, and in parts performed
during the ICERM semester program High-dimensional Approximation in September 2014. We thank Shahar Mendelson
and the anonymous reviewers of the SampTA 2015 conference
for several helpful comments, and Richard Kueng for his
suggestion to consider random Bernoulli measurements with
erasures. Finally, we thank the reviewers of this journal for a
number of insightful comments and perspectives.
Felix Krahmer’s work on this topic was supported by the
German Science Foundation (DFG) in the context of the
Emmy Noether Junior Research Group KR4512/1-1 (RaSenQuaSI) and Project KR4512/2-1 as well as by the German
Israeli Foundation (Grant no. 1266). Contributions to this work
by NIST, an agency of the US government, are not subject to
US copyright law.
R EFERENCES
[1] R. W. Harrison, “Phase problem in crystallography,” JOSA A, 10(5),
pp.1046-1055, 1993.
[2] R. P. Millane, “Phase retrieval in crystallography and optics,” JOSA A,
7(3), pp.394-411, 1990.
[3] J. C. Dainty and J. R. Fienup, “Phase retrieval and image reconstruction
for astronomy,” in Image Recovery: Theory and Application, H. Stark
(ed.), pp.231-275, Academic Press, 1987.
[4] J.M. Rodenburg, “Ptychography and Related Diffractive Imaging Methods,” Advances in Imaging and Electron Physics 150, pp.87-184 (2008).
[5] Y. Shechtman, Y. C. Eldar, O. Cohen, H. N. Chapman, J. Miao and
M. Segev, “Phase retrieval with application to optical imaging,” IEEE
Signal Proc. Mag., 32(3), pp. 87–109, 2015.
[6] R. Kueng, H. Rauhut and U. Terstiege, “Low rank matrix recovery from
rank one measurements,” Appl. Comput. Harmonic Analysis, to appear.
[7] R. Beinert, G. Plonka-Hoch, “Ambiguities in one-dimensional discrete
phase retrieval from Fourier magnitudes,” J. Fourier Anal. Appl. 21(6),
1169–1198, 2015
[8] A. Fannjiang, “Absolute uniqueness in phase retrieval with random
illumination,” Inverse Prob. 28, 075008, 2012.
[9] E. J. Candes, T. Strohmer and V. Voroninski, “PhaseLift: exact and
stable signal recovery from magnitude measurements via convex programming,” Commun. Pure Appl. Math. 66, pp.1241–1274.
[10] L. Demanet and P. Hand, “Stable optimizationless recovery from phaseless linear measurements,” J. Fourier Anal. Appl., 20(1), pp.199-221,
2014.

15

[11] E. J. Candes and X. Li, “Solving quadratic equations via PhaseLift when
this to get |Nε | ≤ ( 3ε )n . Taking the union bound over all
there are about as many equations as unknowns,” Found. Comput. Math.,
w ∈ Nε , we get that
14(5), pp.1017–1026, 2014
[12] D. Gross, F. Krahmer, and R. Kueng, “A partial derandomization of
N
X


phaselift using spherical designs,” J. Fourier Anal. Appl., 21(2), pp.229–
T
ai xi | ≥ t
Pr
∃w
∈
N
s.t.
|w
ε
266, 2015
i=1
[13] E. J. Candes, X. Li and M. Soltanolkotabi, “Phase retrieval from coded

2
diffraction patterns,” Appl. Comput. Harmonic Analysis, 39(2), pp.277–
≤ e · exp n ln( 3ε ) − K 2ctkak2 . (125)
299, 2015.
2
[14] D. Gross, F. Krahmer and R. Kueng, “Improved recovery guarantees for
Finally, a standard argument (similar to Lemma 5.3 in [21])
phase retrieval from coded diffraction patterns,” Appl. Comput. Harmon.
Anal., 42(1), pp.37–64, 2017
shows that, for any vector v ∈ Rn ,
[15] F. Krahmer and Y.-K. Liu, “Phase retrieval without small-ball probabil1
ity assumptions: Stability and uniqueness,” 2015 Intl. Conf. Sampling
max vT x ≤ kvk2 ≤ 1−ε
max vT x.
(126)
x∈Nε
x∈Nε
Theory Appl., pp.411–414.
[16] F. Krahmer and Y.-K. Liu, “Phase retrieval without small-ball probaP
1
Thus, if k N
bility assumptions: Recovery guarantees for phaselift,” 2015 Intl. Conf.
i=1 ai xi k2 ≥ 1−ε t, then there must exist some
P
Sampling Theory Appl., pp.622–626.
w ∈ Nε such that |wT N
i=1 ai xi | ≥ t. Combining this with
[17] Y. C. Eldar and S. Mendelson, “Phase retrieval: stability and recovery
equation
(125)
completes
the
proof. 
guarantees,” Appl. Comput. Harmonic Analysis, 36(3), pp.473–494.
[18] A. Ai, A. Lapanowski, Y. Plan, and R. Vershynin. “One-bit compressed
sensing with non-gaussian measurements,” Lin. Alg. Appl. 441, pp.22–
Lemma A.2 (Vector Bernstein inequality). Let x1 , . . . , xN
239, 2014.
be
independent, centered, sub-exponential random variables
[19] M. Iwen, A. Viswanathan and Y. Wang, “Fast Phase Retrieval from
taking values in Rn , and let K = maxi∈[N ] kxi kψ1 . Fix some
Local Correlation Measurements,” arXiv:1501.02377.
[20] S.
Mendelson,
“Oracle
inequalities
and
the
isoa = (a1 , . . . , aN ) ∈ RN . Let 0 < ε < 1 and t ≥ 0. Then
morphic
method,”
manuscript,
2012,
available
at:
http://maths-people.anu.edu.au/∼mendelso/papers/subgaussian-12-01-2012.pdf.
N
 X

[21] R. Vershynin, “Introduction to the non-asymptotic analysis of random
1
ai xi k2 ≥ 1−ε
Pr
k
t
matrices,” chapter 5 in Y. Eldar and G. Kutyniok (eds.), Compressed
i=1
Sensing, Theory and Applications, Cambridge Univ. Press, 2012.

2
[22] D. Suess, R. Kueng and D. Gross, “Certifying linear optical circuits
t
≤ 2 exp n ln( 3ε ) − c min { K 2tkak2 , Kkak
} , (127)
via phaseless estimation techniques,” poster presentation, Conference on
∞
2
Quantum Information Processing (QIP 2016), Jan. 10-15, 2016, Banff,
where c > 0 is a universal constant.
Alberta, Canada.
[23] R. Kueng and P. Jung, “Robust Nonnegative Sparse Recovery and the
Proof: We use the same argument as for Lemma A.1, but
Nullspace Property of 0/1 Measurements”, arXiv preprint 1603.07997.

starting from a scalar Bernstein inequality (Prop. 5.16 in [21]).


A PPENDIX
The following variants of the Hoeffding and Bernstein
inequalities, for sums of independent subgaussian and subexponential random vectors, are straight-forward generalizations
of the standard results.
Lemma A.1 (Vector Hoeffding inequality). Let x1 , . . . , xN be
independent, centered, subgaussian random variables taking
values in Rn , and let K = maxi∈[N ] kxi kψ2 . Fix some a =
(a1 , . . . , aN ) ∈ RN . Let 0 < ε < 1 and t ≥ 0. Then
N
 X
ai xi k2 ≥
Pr k
i=1

1
1−ε t




2
≤ e·exp n ln( 3ε )− K 2ctkak2 , (123)
2

Felix Krahmer received his BSc in Mathematics from International University Bremen and his MSc as well as his PhD in Mathematics from New York
University under the supervision of Percy Deift and Sinan Güntürk. He was a
postdoctoral fellow in the group of Holger Rauhut at the University of Bonn,
Germany, from 2009-2012. In 2012 he joined the University of Göttingen as an
assistant professor for mathematical data analysis, where he has been awarded
an Emmy Noether Junior Research Group. Since 2015 he has been a tenure
track assistant professor for optimization and data analysis in the department
of mathematics at the Technical University of Munich. His research interests
include mathematical signal and data processing, applied harmonic analysis,
and random matrix theory.

where c > 0 is a universal constant.
Proof: We use the Hoeffding inequality for scalar random
variables, together with a covering argument over the unit
sphere.
For any vector w ∈ S n−1 , we have kwT xi kψ2 ≤ K. Using
the scalar Hoeffding inequality (Prop. 5.10 in [21]), we get
that
N
X



2
ai xi | ≥ t ≤ e · exp − K 2ctkak2 .
Pr |wT
i=1

(124)

2

Using Lemma 5.2 in [21], we know that there is an ε-net for
S n−1 , with respect to the ℓ2 norm, with cardinality (1 + 2ε )n ;
call this set Nε . Note that when 0 < ε < 1, we can simplify

Yi-Kai Liu received his bachelors degree in Mathematics at Princeton University in 2002. He received his PhD in Computer Science at the University of
California, San Diego, in 2007. He was the recipient of an NSF Mathematical
Sciences Postdoctoral Research Fellowship, and a postdoctoral researcher at
Caltech and at the University of California, Berkeley. In 2011 he joined the
US National Institute of Standards and Technology (NIST). In addition, he is
currently a Fellow at the Joint Center for Quantum Information and Computer
Science (QuICS) at the University of Maryland. His research interests include
quantum computation, cryptography, and machine learning.

