Improved Recovery Guarantees for Phase Retrieval from Coded Diffraction Patterns

Introduction

In this work we are interested in the problem of phase retrieval which is of considerable importance in many different areas of science, where capturing phase information is hard or even infeasible. Problems of this kind occur, for example, in X-ray crystallography, diffraction imaging, and astronomy.

Approaches based on algebraic geometry (for example ) have established that for determining $x$, $4d+{o}(1)$ generic measurements are sufficient and $4d-\mathcal{O}(\log d)$ such observations are necessary. Here, “generic” means that the measurement ensembles for which the property fails to hold lie on a low-dimensional subvariety of the algebraic variety of all tight measurement frames.

This notion of generic success, however, is mainly of theoretical interest. Namely, injectivity alone neither gives an indication on how to recover the unique solution, nor is there any chance to directly generalize the results to the case of noisy measurements. It should be noted, however, that recently the notion of injectivity has been refined to capture aspects of stability with respect to noise .

Paralleling these advances, there have been various attempts to find tractable recovery algorithms that yield recovery guarantees. Many of these approaches are based on a linear reformulation in matrix space, which is well-known in convex programming. The crucial underlying observation is that the quadratic constraints (1) on $x$ are linear in the outer product $X=xx^{*}$:

Balan et al. observed that for the right choice of $d^{2}$ measurement vectors $a_{i}$, this linear system in the entries of $X$ admits for a unique solution, so the problem can be explicitly solved using linear algebra techniques. This approach, however, does not make use of the low-rank structure of $X$, which is why the required number of measurements is so much larger than what is required for injectivity.

The PhaseLift algorithm proposed by Candès et al. uses in addition the property that $X$ is of rank one, so even when the number of measurements is smaller than $d^{2}$ and there is an entire affine space of matrices satisfying (1.1), $X$ is the solution of smallest rank. While finding the smallest rank solution of a linear system is, in general, NP hard, there are a number of algorithms known to recover the smallest rank solution provided the system satisfies some regularity conditions. The first such results were based on convex relaxation (see, for example, ). PhaseLift is also based on this strategy. For measurement vectors drawn independently at random from a Gaussian distribution, the number of measurements required to guarantee recovery with high probability was shown to be of optimal order, scaling linearly in the dimension – see also for a comparable statement valid for recovering matrices of arbitrary rank. A generalized version of this result—valid for projective measurements onto random subspaces rather than random vectors—was established in . Moreover, Ref. even identifies a deterministic, explicitly engineered set of $4d-4$ measurement vectors and proves that PhaseLift will successfully recover generic signals from the associated measurements. Conversely, any complex vector is uniquely determined by $4d-4$ generic phaseless measurements .

Since these first recovery guarantees for the phase retrieval problem, recovery guarantees have been proved for a number of more efficient algorithms closer to the heuristic approaches typically used in practice. For example, in , an approach based on polarization is analyzed and in , the authors study an alternating minimization algorithm. In both works, recovery guarantees are again proved for Gaussian measurements. Further numerical approaches have been proposed and studied in .

To relate all these results to practice, the structure of applications needs to be incorporated into the setup, which corresponds to reducing randomness and considering structured measurements. For PhaseLift, the first partial derandomization has been provided by the authors of this paper, considering measurements sampled from spherical designs, that is, polynomial-size sets which generalize the notion of a tight frame to higher-order tensors . Recently, this result has been considerably improved in . Arguably, these derandomized measurement setups are still mainly of theoretical interest.

A structured measurement setup closer to applications is that of coded diffraction patterns. These correspond to the composition of diagonal matrices and the Fourier transform and model the modified application setup where diffraction masks are placed between the object and the screen as originally proposed in . The first recovery guarantees from masked Fourier measurements were provided for polarization based recovery , where the design of the masks is very specific and intimately connected to the recovery algorithm. The required number of masks is $\mathcal{O}(\log d)$, which corresponds to $\mathcal{O}(d\log d)$ measurements.

For the PhaseLift algorithm, recovery guarantees from masked Fourier measurements were first provided in . The results require ${\mathcal{O}}(d\log^{4}d)$ measurements and hold with high probability when the masks are chosen at random, which is in line with the observation from that random diffraction patterns are particularly suitable.

In this paper, we consider the same measurement setup as , but improve the bound on the required number of measurements to ${\mathcal{O}}(d\log^{2}d)$.

Problem Setup and Main Results

As in , we will work with the following setup:

the $k$-th discrete Fourier vector, normalized so that each entry has unit modulus. Furthermore, consider the diagonal matrix

where the $\epsilon_{l,i}$’s are independent copies of a real-valued Ref. also included a strongly related model where $\epsilon$ is a complex random variable. We have opted to keep $\epsilon$ real, which implies that the $D_{l}$ are hermitian. This, in turn, has allowed us to slightly simplify notation throughout. random variable $\epsilon$ which obeys

It turns out (Lemma 7 below) that condition (5) on $\epsilon$ ensures that the measurement ensemble forms a spherical $2$-design, which draws a connection to and .

As an example, the criteria above include the model

which has been discussed in . In this case, each modulation is given by a Rademacher vector with random erasures.

2. Convex Relaxation

Following , we rewrite the measurement constraints as the inner product of two rank $1$ matrices, one representing the signal, the other one the measurement coefficients. In the coded diffraction setup, we obtain, as in , that the inner product of (6) can be translated into matrix form by applying the following “lifts”:

Occasionally, we will make use of the representation with respect to the standard basis, which reads

With these definitions, the $dL$ individual linear measurements assume the following form

and the phase retrieval problem thus becomes the problem of finding rank 1 solutions $X=xx^{*}$ compatible with these affine constraints. Rank-minimization over affine spaces is NP-hard in general. However, it is now well-appreciated that nuclear-norm based convex relaxations solve this problems efficiently in many relevant instances. Applied to phase retrieval, the relaxation becomes

which has been dubbed Phaselift by its inventors . For this convex relaxation, recovery guarantees are known for measurement vectors drawn i.i.d. at random from a Gaussian distribution , $t$-designs , or in the masked Fourier setting .

3. Our contribution

In this paper, we adopt the setup from . Our main message is that recovery of $x$ can be guaranteed already for

Thus there cannot be a recovery algorithm requiring fewer than $O(\log d)$ masks and there is only a single $\log$-factor separating our results from an asymptotically tight solution.

More precisely, our version of [1, Theorem 1.1] reads:

Here, $\omega\geq 1$ is an arbitrary parameter and $C$ a dimension-independent constant that can be explicitly bounded.

For the benefit of the technically-minded reader, we briefly sketch the relation between the proof techniques used here, as compared to References and .

The general structure of this document closely mimics (which bears remarkable similarity to , even though the papers were written completely independently and with different aims in mind).

From we borrow the use of Hoeffding’s inequality to bound the probability of “the inner product between the measurement vectors and the signal becoming too large”. This is Lemma 13 below. Our previous work also bounded the probability of such events [19, Lemma 13]—however in a weaker way (relying only on certain $t$th moments as opposed to a Hoeffding bound).

Both as well as the present paper estimate the condition number of the measurement operator restricted to the tangent space at $xx^{*}$ (“robust injectivity”). Our Proposition 8 improves over [1, Section 3.3] by using an operator Bernstein inequality instead of a weaker operator Hoeffding bound.

Finally, we use a slightly refined version of the golfing scheme to construct an approximate dual certificate (following [11, Section III.B]).

4. More general bases and outlook

The result allows for a fairly general distribution of the masks $D_{l}$, but refers specifically to the Fourier basis. An obvious question is how sensitively the statements depend on the properties of this basis.

We begin by pointing out that Theorem 1 immediately implies a corollary for higher-dimensional Fourier transforms. In diffraction imaging applications, for example, one would naturally employ a 2-D Fourier basis

with $d_{x}$ and $d_{y}$ the horizontal and vertical resolution respectively, $\omega_{d}:=\exp\left(\frac{2\pi i}{d}\right)$, and $e_{i,j}$ the position space basis vector representing a signal located at coordinates $(i,j)$. Superficially, (11) looks quite different from the one-dimensional case (2). However, a basic application of the Chinese Remainder Theorem shows that if $d_{x}$ and $d_{y}$ are co-prime, then the 2-D transform reduces to the 1-D one for dimension $d_{x}d_{y}$ (in the sense that the respective bases agree up to relabeling) . An analogous result holds for higher-dimensional transforms , proving the following corollary.

Assume $d=\prod_{i=1}^{k}d_{i}$ is the product of mutually co-prime odd numbers greater than $3$. Then Theorem 1 remains valid for the $k$-dimensional Fourier transform over $d_{1},\dots,d_{k}$.

More generally speaking, our argument employs the particular properties of Fourier bases in two places: Lemma 7 and Lemma 9.

The former lemma shows that the measurements are drawn from an isotropic ensemble (or tight frame) in the relevant space of hermitian matrices. A similar condition is frequently used in works on phase retrieval, low-rank matrix completion, and compressed sensing (e.g. ). Properties of the Fourier basis are used in the proof of Lemma 7 only for concreteness. Using relatively straight-forward representation theory, one can give a far more abstract version of the result which is valid for any basis satisfying two explicit polynomial relations (cf. the remark below the lemma). The combinatorial structure of Fourier transforms is immaterial at this point.

This contrasts with Lemma 9 which currently prevents us from generalizing the main result to a broader class of bases. Its proof uses explicit coordinate expressions of the Fourier basis to facilitate a series of simplifications. Identifying the abstract gist of the manipulations is the main open problem which we hope to address in future work.

We make use of the condition that $d$ be odd only for Lemma 7. While that particular Lemma fails to hold for even dimensions, we find it plausible that the result as a whole remains essentially true for even dimensions.

It would also be interesting to use the techniques of the present paper to re-visit the problem of quantum state tomography (which was the initial motivation for one of the authors to become interested in low-rank recovery methods). Indeed, the original work on quantum state tomography and low-rank recovery was based on a model where the expectation value of a Pauli matrix is the elementary unity of information exctractable from a quantum experiment. While this correctly describes some experiments, it is arguably more common that the statistics of the eigenbasis of an observable are the objects that can be physically directly accessed. For this practically more relevant case, no recovery guarantees seem to be currently known and the methods used here could be used to amend that situation.

Technical Background and Notation

On the level of matrices we will exclusively encounter $d\times d$ hermitian matrices and denote them by capital Latin characters. Endowed with the Hilbert-Schmidt (or Frobenius) scalar product

the space $H^{d}$ of all $d\times d$ hermitian matrices becomes a Hilbert space itself. In addition to that, we will require three different operator norms

In the definition of the trace norm, $|Z|$ denotes the unique positive semidefinite matrix obeying $|Z|^{2}=Z^{2}$ (or equivalently $|Z|=\sqrt{Z^{2}}$ which is unique). For arbitrary matrices $Z$ of rank at most $r$, the norms above are related via the inequalities

Finally, we will also encounter matrix-valued operators acting on the matrix space $H^{d}$. Here, we will restrict ourselves to operators that are hermitian with respect to the Hilbert-Schmitt inner product. We label such objects with calligraphic letters. The operator norm becomes

It turns out that only two classes of such operators will appear in our work, namely the identity map

and (scalar multiples of) projectors onto some matrix $Y\in H^{d}$ as given by

An important example of the latter class is

The notion of positive-semidefiniteness directly translates to matrix valued operators. It is easy to check that all the operators introduced so far are positive semidefinite. From (15) we obtain the ordering

2. Tools from Probability Theory

In this section, we recall some concentration inequalities which will prove useful for our argument. Our first tool is a slight extension of Hoeffding’s inequality .

Secondly, we will require two matrix versions of Bernstein’s inequality. Such matrix valued large deviation bounds have been established first in the field of quantum information by Ahlswede and Winter and introduced to sparse and low-rank recovery in . We make use of refined versions from , see also [30, Chapter 8.5] for the former. Note that as $H^{d}$ is a finite dimensional vector space, the results also apply to matrix valued operators as introduced in section 3.1.

Finally, we are also going to require a type of vector Bernstein inequality. Note that, since $H^{d}$ is a $d^{2}$-dimensional real vector space, the statement remains valid for a sum of random hermitian matrices.

This particular vector-valued Bernstein inequality is based on the exposition in [34, Chapter 6.3, equation (6.12)] and a direct proof can be found in .

Proof Ingredients

In this section we study the measurement operator We are going to use the notations $\mathcal{M}(Z)$ and $\mathcal{M}Z$ equivalently.

which just corresponds to $\mathcal{R}=\frac{1}{\nu^{2}dL}\mathcal{A}^{*}\mathcal{A}$, where $\nu$ was defined in (5).

The following result shows that this operator is near-isotropic in the sense of .

The operator $\mathcal{R}$ defined in (19) is near-isotropic in the sense that

A proof of Lemma 7 can be found in . However, we still present a proof – which is of a slightly different spirit – in the appendix for the sake of being self-contained.

Two remarks are in order with regard to the previous lemma.

First, it is worthwhile to point out that near-isotropicity of $\mathcal{R}$ is equivalent to stating that the set of all possible realizations of $D_{l}f_{k}$ form a 2-design. This has been made explicit recently in [35, Lemma 1]. The notion of higher-order spherical designs is the basic mathematical object of our previous work on phase retrieval.

which is the tangent space of the manifold of all rank-1 hermitian matrices at the point $X=xx^{*}$. The orthogonal projection onto this space can be given explicitly:

The Frobenius inner product allows us to define an ortho-complement $T^{\perp}$ of $T$ in $H^{d}$. We denote the projection onto $T^{\perp}$ by $\mathcal{P}_{T}^{\perp}$ and decompose any matrix $Z\in H^{d}$ as

holds for any $Z\in H^{d}$. The first fact follows by direct calculation, while the second one comes from

where the last estimate used the pinching inequality (Problem II.5.4).

2. Well-posedness/Injectivity

In this section, we follow in order to establish a certain injectivity property of the measurement operator $\mathcal{A}$.

Our Proposition 8 is the analogue of Lemma 3.7 in . The latter contained a factor of $\mathcal{O}(\log^{2}d)$ in the exponent of the failure probability, which does not appear here. The reason is that we employ a single-sided Bernstein inequality, instead of a symmetric Hoeffding inequality.

With probability of failure smaller than $d^{2}\exp\left(-\frac{\nu^{4}L}{C_{1}b^{8}}\right)$ the inequality

is valid for all matrices $Z\in T$ simultaneously. Here $b$ and $\nu$ are as in (4, 5) and $C_{1}$ is an absolute constant.

We require bounds on certain variances for the proof of this statement. The technical Lemma 9 serves this purpose.

Let $Z\in T$ be an arbitrary matrix and let $\mathcal{M}_{l}$ be as in (20). Then it holds that

The symbols $\oplus$ and $\ominus$ denote addition and subtraction modulo $d$.

where in (4.2) we have inserted the definition of $\mathcal{M}_{l}$, in (31) have made use of (29), and in (32) we have eliminated $i_{1}$. We now make the crucial observation that the expectation

where the three inequalities follow, in that order, by realizing that making individual coefficients of $e_{i_{2}}$ larger will increase the norm; restricting to non-zero expectation values as per the discussion above; and using the assumed bound $|\epsilon|\leq b$.

Now fix a matching $E$. Let $x^{(1)}$ be the vector in $\{v,\bar{y},y,\bar{z},z\}$ whose index in (34) is paired with $i_{2}$. Label the remaining four vectors in that set by $x^{(2)},\dots,x^{(5)}$, in such a way that $x^{(2)}$ and $x^{(3)}$ are paired and the same is true for $x^{(4)}$ and $x^{(5)}$. Then the summand corresponding to that matching becomes

by the Cauchy-Schwarz inequality and the fact that all the $x^{(i)}$ are of length one. As there are $15$ possible matchings of $6$ indices, we arrive at

The upper bound in (28) is thus implied by (27). ∎

With Lemma 9 at hand, we can proceed to the lower bound on robust injectivity.

We strongly follow the ideas presented in [19, Proposition 9] and aim to show the more general statement

Pick $Z\in T$ arbitrary and use near isotropicity (21) of $\mathcal{R}$ in order to write

where $\mathcal{M}_{l}$ was defined in (20). Note that these summands have mean zero by construction. Furthermore (25) implies

where the last inequality follows from $\widetilde{\mathcal{M}}_{l}\geq 0$. This yields an a priori bound

For the variance we use the standard identity

for any $0\leq\delta\leq 1<60b^{8}/\nu^{2}=\sigma^{2}/\underline{R}$ and $\widetilde{C}_{1}$ is an absolute constant. This gives a suitable bound on the probability of the undesired event

for all matrices $Z\in T$ simultaneously. This proves (35) and setting $\delta=3/4$ yields Proposition 8 (with $C_{1}=\frac{16}{9}\widetilde{C}_{1}$). ∎

Let $\mathcal{A}$ be as above. Then the statement

holds with probability 1 for all matrices $Z\in H^{d}$ simultaneously.

where the first inequality holds because the $f_{k}f_{k}^{*}$’s are mutually orthogonal. The second inequality follows from the fact that the Frobenius norm (and more generally: any unitarily invariant norm) is symmetric [39, Proposition IV.2.4] – i.e., $\|ABC\|_{2}\leq\|A\|_{\infty}\|B\|_{2}\|C\|_{\infty}$ for any $A,B,C\in H^{d}$ – and the last one is due to the a-priori bound $\|D_{l}\|_{\infty}\leq b$. ∎

Proof of the Main Theorem / Convex Geometry

In this section, we will prove that the convex program (9) indeed recovers the signal $x$ with high probability. A common approach to prove recovery is to show the existence of an approximate dual certificate, which in our problem setup can be formalized by the following definition.

The following proposition, showing that the existence of such a dual certificate indeed guarantees recovery, is just a slight variation of Proposition 12 in . For completeness, we have nevertheless included a proof in the appendix.

Proposition 12 proves the Main Theorem of this paper, provided that an approximate dual certificate exists. A first approach to construct an approximate dual certificate is to set

A main difference between our approach and the approach in is that the authors of that paper use Hoeffding’s inequality in the golfing scheme, while we employ Bernstein’s inequality. The resulting bounds are sharper, but require to estimate an additional variance parameter.

An issue that remains is that such bounds heavily depend on the worst-case operator norm of the individual summands. In this framework these are proportional to $|\langle f_{k},D_{l}x\rangle|^{2}$, which a priori can reach $b^{2}d$ (recall that $\|f_{k}\|_{2}^{2}=d$). To deal with this issue, we follow the approach from to condition on the event that their maximal value is not too large.

For $Z\in T$ abitrary and a parameter $\gamma\geq 1$ we introduce the event

If $D_{l}$ is chosen according to (3) it holds that

In the following, we refer to $\gamma$ as the truncation rate (cf. ). Here, we fix

for reasons that shall become clear in the proofs of Propositions 16 and 17. Here $b$ and $\nu$ are as in (4) and (5).

Fix $Z\in T$ arbitrary and apply an eigenvalue decomposition

where the last inequality uses a union bound. The desired statement thus follows from

This result will be an important tool to bound the probability of extreme operator norms.

For $Z\in T$ arbitrary and the corresponding $U_{k,l}$ introduced in (40) we define the truncated measurement operator

where $1_{U_{k,l}}$ denotes the indicator function associated with the event $U_{k,l}$.

We now show that in expectation, this truncated operator is close to the original one.

Fix $Z\in T$ arbitrary and let $\mathcal{R}_{Z}$ and $\mathcal{M}_{l}^{Z}$ be as in (42). Then

Here we have used $|\operatorname{tr}(F_{k,l}W)|\leq b^{2}d\|W\|_{\infty}$ for any $W\in H^{d}$ and $\|F_{k,l}\|_{\infty}\leq b^{2}d$ (both estimates are direct consequences of the definition of $F_{k,l}$). Finally

We will now establish two technical ingredients for the golfing scheme.

Assume $d\geq 3$, fix $Z\in T$ arbitrary and let $\mathcal{R}_{Z}$ be as in (42). Then

for any $t\geq 1/4$ and $\gamma$ defined in (41). Here $C_{2}$ denotes an absolute constant.

Assume w.l.o.g. that $\|Z\|_{2}=1$. By Lemma 7,

because $Z\in T$ by assumption. We can thus rewrite the desired expression as

In the third line, we have used that $\|\mathcal{P}_{T}^{\perp}W\|\leq\|W\|$ for any $W\in H^{d}$ and any unitarily invariant norm $\|\cdot\|$ (pinching, cf. (Problem II.5.4)). The last inequality follows from

which in turn follows from Lemma 15 and the assumptions on $d$, $t$ and $\gamma$. By (44), it remains to bound the probability of the complement of the event

To this end, we use the Operator Bernstein inequality (Theorem 4). We decompose

where $\mathcal{M}_{l}^{Z}$ was defined in (42). To find an a priori bound for the individual summands, we write, using that $F_{k,l}\geq 0$ holds for all $1\leq k\leq d$,

where we have used Lemmas 15 and 9. Using $\|Z\|_{\infty}\leq\|Z\|_{2}=1$ and noting that $\nu\leq b^{2}$ entails $\gamma=8+2\log_{2}(b^{2}/\nu)\geq 8$ we conclude

Our choice for $\overline{R}$ now guarantees $\sigma^{2}/\overline{R}=3/(16\gamma\log d)\leq 3t/4$ for any $t\geq 1/4$ (here we have used $\gamma\geq 1$ and our assumption $d\geq 3$ which entails $\log d\geq 1$). Consequently

with $C_{2}$ an absolute constant. This completes the proof. ∎

Assume $d\geq 2$ and fix $Z\in T$ arbitrary and let $\mathcal{R}_{Z}$ be as in (42) with $\gamma$ defined in (41). Then

holds for any $1/(2\log d)\leq c\leq 1$. Here, $C_{3}$ is again an absolute constant.

Similar to the previous proof, we start by assuming $\|Z\|_{2}=1$ and using near-isotropy of $\mathcal{R}$ to bound the desired expression by

Here, we have used $\|\mathcal{P}_{T}W\|_{2}\leq\|W\|_{2}$ for any matrix $W$ (this follows e.g. from the entry-wise definition of the Frobenius norm) and a calculation similar to (45):

where we have used $d\geq 2$, $\gamma\geq 8$ and the assumption $c\geq 1/(2\log d)$. Paralleling our idea from the previous proof, we define the event

which guarantees that the desired inequality is valid. However, in order to bound the probability of $(E^{\prime})^{c}$, this time we are going to employ the vector Bernstein inequality—Theorem 6. Decompose

Applying $b^{2}\geq\nu$, $\operatorname{tr}(Z)^{2}\leq 2\|Z\|_{2}^{2}=2$ and $d^{4-\gamma}\leq 1$ (because we choose $\gamma\geq 8$) allows us to upper-bound (47) by $71b^{8}/(\nu^{4}L^{2})$ and set

Again, the last estimate is far from tight, but assures $\sigma^{2}/B=b^{4}/\nu^{2}\geq 1$. Applying the vector Bernstein inequality—Theorem 6—for $t=3c/4$ yields the desired bound on the probability of $(E^{\prime})^{c}$ occurring.

We are now ready to construct a suitable approximate dual certificate in the sense of Definition 11. The key idea here is an iterative procedure – dubbed the golfing scheme – that was first established in (see also ).

Assume $d\geq 3$ and let $\omega\geq 1$ be arbitrary. If the total number of $L$ of diffraction patterns fulfills

To be concrete, the constant $C$ depends on the truncation rate $\gamma$ – which we have fixed in (41) – and the a-priori bound $b$ and $\nu$ of the random variable $\epsilon$ used to generate the diffraction patterns $D_{l}$:

This construction is inspired by and . As in , our construction of $Y$ follows a recursive procedure of $w$ iterations which can be summarized in the pseudo-code described in Algorithm 1. It depends on a number of parameters – $w,L_{i},r$, c.f. Input section of the algorithm – the values of which will be chosen below. If this algorithm succeeds, it outputs three lists

They obey iterative relations of the following form (c.f. [24, Lemma 14]):

This choice, together with the validity of properties (43) and (46) for $t=1/8$, $c=1/\sqrt{2\log d}$ in the first two steps and for $t=\log d/4$, $c=1/2$ in each remaining update ($Y_{i}\to Y_{i+1}$ and $Q_{i}\to Q_{i+1}$, respectively) together with $Q_{0}=X$ then guarantee

which are precisely the requirements (38) on $Y$.

or fewer than $r$ of the remaining ones succeed

We start by estimating the probability of (50) occuring. Setting

for a sufficiently large absolute constant $C_{5}$, and using the union bound over Propositions 16 and 17 (for $Z=X$), one obtains

An analogous bound holds for the probability of $\xi_{2}=0$.

We turn to (51). Our aim is to bound $\Pr\left[\sum_{i=3}^{w+2}\xi_{i}<r\right]$ by a similar expression involving independent Bernoulli variables $\xi_{i}^{\prime}$. To achieve this, we observe

is valid, provided that $\xi_{w+1}^{\prime}$ is an independent $p^{\prime}$-Bernoulli distributed random variable with

A combination of Propositions 16 and 17 provides a uniform lower bound on $p\left(\xi_{w+1},\dots,\xi_{3}\right)$. Indeed, setting $Z=Q_{w}$ and invoking them with

– where $C_{4}$ is a sufficiently large constant – assures a probability of success of at least $9/10$ for any $Q$. This estimate is in particular independent of $\xi_{w+1},\dots,\xi_{3}$. Consequently, by choosing $p^{\prime}=9/10$ and $L_{i}=L$ for all $3\leq i\leq w+2$, we can iterate the estimate (53) and arrive at

where the $\xi_{i}^{\prime}$’s on the right hand side are independent Bernoulli variables with parameter $9/10$. A standard one-sided Chernoff bound (e.g. e.g [42, Section Concentration: Theorem 2.1]) gives

Setting the number of iterations generously to

where we have used $\omega\geq 1$ in the first and last step. From this estimate we can conclude

Finally we note that with our construction the total amount of masks obeys

We now have all the ingredients for the proof of our main result, Theorem 1.

DG and RK are grateful to the organizers and participants of the Workshop on Phaseless Reconstruction, held as part of the 2013 February Fourier Talks at the University of Maryland, where they were introduced to the details of the problem. This extends, in particular, to Thomas Strohmer. RK is pleased to acknolwedge extremely helpful advice he received from Johan Aberg troughout the course of the project. FK thanks the organizers and participants of the AIM workshop “Frame theory intersects geometry”, in particular Thomas Strohmer, Götz Pfander, and Nate Strawn, for stimulating conversations on the topic of this paper. The authors also acknowledge inspiring discussions with Emmanuel Candès, Yonina Eldar, and David James. We would also like to thank the anonymous referees for extremely helpful comments and suggestions which allowed us to further improve the presentation of our results.

The work of DG and RK is supported by the Excellence Initiative of the German Federal and State Governments (Grants ZUK 43 & 81), by scholarship funds from the State Graduate Funding Program of Baden-Württemberg, by the US Army Research Office under contracts W911NF-14-1-0098 and W911NF-14-1-0133 (Quantum Characterization, Verification, and Validation), and the DFG (GRO 4334 & SPP 1798). FK acknowledges support from the German Federal Ministry of Education and Reseach (BMBF) through the cooperative research project ZeMat.

References

Appendix

We prove formula (21) in a way that is slightly different from the proof provided in . We show that the set of all possible $D_{l}f_{k}$’s is in fact proportional to a 2-design and deduce near-isotropicity of $\mathcal{R}$ from this. We refer to for further clarification of the concepts used here. Concretely, for $1\leq l\leq L$ we aim to show

where we have used the moment condition (5) in the last step. This however is equivalent to the action of $2P_{\operatorname{Sym}^{2}}$ on symmetric basis states.

Let us now focus on the second case, namely $i\neq j$. A similar calculation then yields

Let $X^{\prime}$ be an arbitrary feasible point of (9) and we decompose it as $X^{\prime}=X+\Delta$, where $\Delta$ is a feasible displacement. Feasibility then implies $\mathcal{A}(X^{\prime})=\mathcal{A}(X)$ and consequently $\mathcal{A}(\Delta)=0$ must hold. The pinching inequality (Problem II.5.4) now implies

and $X$ is guaranteed to be the minimum of (9) if

is true for any feasible displacement $\Delta$. Therefore it suffices to show that (58) is guaranteed to hold under the assumptions of the proposition. In order to do so, we combine feasibility of $\Delta$ with Proposition 8 and Lemma 10 to obtain

which is just the optimality criterion (58). ∎