Saving phase: Injectivity and stability for phase retrieval

Posted on by Dustin G. Mixon

In this entry, I offer a prize for a certain math problem, but before I discuss the prize, I want to provide some context.

Last time, I mentioned my talk at the FFT workshop on phaseless reconstruction.  One of the things I talked about was the fewest number of intensity measurements required for injectivity.  I recently wrote a paper with Afonso S. Bandeira, Jameson Cahill and Aaron A. Nelson (whose title is the same as this blog entry’s), and in this paper we discuss this problem quite a bit.  The paper also presents some interesting results regarding stable phase retrieval—for example, it introduces the strong complement property, which concerns the singular values of submatrices of the phase retrieval sensing matrix (analogous to the restricted isometry property of compressed sensing), and is equivalent in some sense to the stability of phase retrieval in the real case.  Rather than survey the various results of the paper, this blog entry will focus on the injectivity requirement.

Let N^*(M) denote the smallest number of injective intensity measurements in M-dimensional space.  By this I mean there exists M-dimensional vectors \{\varphi_n\}_{n=1}^{N^*(M)} for which \{|\langle x,\varphi_n\rangle|^2\}_{n=1}^{N^*(M)}=\{|\langle y,\varphi_n\rangle|^2\}_{n=1}^{N^*(M)} only if there exists a scalar c of modulus 1 such that x=cy, and there is no such ensemble of measurement vectors of size smaller than N^*(M).  In a paper by Balan, Casazza and Edidin, it is shown that N^*(M)=2M-1 when the vector space is \mathbb{R}^M.  This actually follows from a characterization of injectivity that they provide:

Theorem.  In the real case, the mapping x\mapsto\{|\langle x,\varphi_n\rangle|^2\}_{n=1}^{N} is injective if and only if for every S\subseteq\{1,\ldots,N\}, either \{\varphi_n\}_{n\in S} or \{\varphi_n\}_{n\in S^\mathrm{c}} spans \mathbb{R}^M.

For a proof, see this blog post.  The injectivity condition in this theorem has since been called the complement property, and from this, it is almost immediate that N^*(M)=2M-1:  Certainly, \{\varphi_n\}_{n=1}^{2M-1} satisfies the complement property if it’s full spark, and \{\varphi_n\}_{n=1}^{2M-2} can be partitioned into two sets of size M-1, neither of which spans.  Note that this characterization implies a sort of phase transition for injectivity:  If N<2M-1, then \{\varphi_n\}_{n=1}^N never lends injectivity, but if N\geq 2M-1, then \{\varphi_n\}_{n=1}^N almost always lends injectivity (by almost always, I mean that, for example, Gaussian random vectors lend injectivity with probability 1).  This is analogous to the linear algebraic notion of spanning:  If N<M, then \{\varphi_n\}_{n=1}^N does not span, and so x\mapsto\{\langle x,\varphi_n\rangle\}_{n=1}^N is not injective, but if N\geq M, then \{\varphi_n\}_{n=1}^N typically spans, thereby making x\mapsto\{\langle x,\varphi_n\rangle\}_{n=1}^N injective.

At the moment, the complex case lacks a simple injectivity characterization like the above theorem.  In our paper, we happen to characterize injectivity in this case, but I can’t figure out how to use the result to determine N^*(M):

Theorem.  In the complex case, the mapping x\mapsto\{|\langle x,\varphi_n\rangle|^2\}_{n=1}^{N} is injective if and only if for every nonzero vector u, \mathrm{span}_\mathbb{R}\{\varphi_n\varphi_n^*u\}_{n=1}^N=\mathrm{span}_\mathbb{R}\{iu\}^\perp.

Here, we use the real span to denote the set of linear combinations with real coefficients, and the orthogonal complement is taken in the real 2M-dimensional vector space \mathbb{C}^M.  The proof of this result is more technical than its real counterpart, but it definitely uses the same bag of tricks (consider the sum and difference of two vectors with the same intensity measurements, etc.).  While it is not clear how to apply this characterization to find N^*(M), we were able to use it to find other results.  For example, we showed that the complement property is actually necessary (but not sufficient) for injectivity in the complex case.

So we failed to find N^*(M) by an argument which is analogous to the real case.  At this point, let’s survey what is known about N^*(M).  In 1978, Vogt wrote a paper in which he credited the following conjecture to Ron Wright:

Wright’s Conjecture.  There exist three unitary matrices such that if \Phi=[U_1,U_2,U_3], then x\mapsto|\Phi^*x|^2 is injective.

Note that summing the entries of |U_i^*x|^2 gives \|x\|^2 for each i=1,2,3, and so we can afford to throw away any column from U_2 and any column from U_3.  In other words, Wright’s Conjecture implies N^*(M)\leq 3M-2.  The next stride happened 26 years later when Finkelstein proved that N^*(M)\geq3M-2.  Combined with Wright’s Conjecture, this led the community to believe that N^*(M)=3M-2, but to know this for sure, we needed better upper bounds.  In 2005, Weigert found that you can span the M^2-dimensional space of self-adjoint operators using M^2 rank-1 projections, which in turn implies that N^*(M)\leq M^2 (using the “standard” lifting argument, see this paper).  A year later, this upper bound was improved significantly by Balan, Casazza and Edidin using algebraic geometry: N^*(M)\leq 4M-2.  At this point, the gap was pretty small: N^*(M)\in[3M-2,4M-2], and we suspected from Wright’s Conjecture that the lower bound was the true value.  Everything changed in 2011, when Heinosaari, Mazzarella and Wolf leveraged embedding results from differential geometry to show that N^*(M)\geq4M-2\alpha(M-1)-3, where \alpha(M-1)\leq\log_2(M) is the number of 1‘s in the binary expansion of M-1.  This result disproved Wright’s Conjecture and narrowed the gap to an asymptotic expression: N^*(M)=(4+o(1))M.  Recently, Bodmann and Hammen posted a paper on the arXiv that describes a construction of 4M-4 injective intensity measurements, thereby decreasing the upper bound on N^*(M) by 2.  So now that we know N^*(M)\in[4M-2\alpha(M-1)-3,4M-4], what do we think the magic number is? 4M-4.

In our paper, we show that injectivity is equivalent to having no matrix of rank 1 or 2 be orthogonal to \{\varphi_n\varphi_n^*\}_{n=1}^N in the space of self-adjoint operators.  We also count the number of real degrees of freedom in the set S of matrices of rank 1 or 2: 4M-4.  Intuitively, the orthogonal complement of \{\varphi_n\varphi_n^*\}_{n=1}^N will tend to have dimension M^2-N, and so this ought to avoid S whenever (M^2-N)+(4M-4)\leq M^2, i.e, whenever N\geq 4M-4.  Moreover, if S is anything like a subspace (is it?), this should happen for almost all choices of \{\varphi_n\}_{n=1}^N whenever N\geq4M-4, similar to how almost all choices of \geq2M-1 real vectors lend injectivity.  This naturally leads to the following conjecture:

The 4M-4 Conjecture. Pick M\geq2. Then in the complex case, the following statements hold:

(a) If N<4M-4, then x\mapsto\{|\langle x,\varphi_n\rangle|^2\}_{n=1}^{N} is not injective.

(b) If N\geq4M-4, then x\mapsto\{|\langle x,\varphi_n\rangle|^2\}_{n=1}^{N} is injective for generic \{\varphi_n\}_{n=1}^N.

Note that this conjecture is a little bit stronger than just N^*(M)=4M-4, since (b) claims that generic vectors \{\varphi_n\}_{n=1}^N lend injectivity whenever N\geq4M-4 (as opposed to “mere” existence of an ensemble which lends injectivity).  For the sake of clarity, I want to elaborate on what I mean by “generic.”  Here, I mean that I can describe the set of \{\varphi_n\}_{n=1}^N for which x\mapsto\{|\langle x,\varphi_n\rangle|^2\}_{n=1}^{N} is not injective as a subset Z\subseteq\mathbb{R}^{2MN} (each coordinate of each \varphi_n contributing two real dimensions), and that Z is contained in the locus of zeros of some nontrivial polynomial of 2MN variables with real coefficients.  Using the power of algebraic geometry, this would in turn imply that the set of \{\varphi_n\}_{n=1}^N for which x\mapsto\{|\langle x,\varphi_n\rangle|^2\}_{n=1}^{N} is injective contains a nonempty Zariski-open set, which is necessarily dense with full measure.

Considering our dimension analysis of the set of matrices of rank \leq2, the 4M-4 Conjecture makes some intuitive sense.  In addition, we managed to prove that this conjecture holds in the special cases where M=2 and 3.  For the M=2 case, injectivity is equivalent to having \{\varphi_n\varphi_n^*\}_{n=1}^N span the space of self-adjoint operators, so the conjecture is not terribly surprising in this case.  For the M=3 case, we leveraged a test for injectivity that is suggested in the paper of Heinosaari, Mazzarella and Wolf.  (Actually, Jameson independently came up with the same test, and so in the original version of the paper, I called it “Cahill’s test,” but now that we’ve identified its true origin, we call it the HMW test after the originators.)  This test is pretty remarkable—given any ensemble of vectors in \mathbb{C}^3, you can quickly determine whether it lends injective intensity measurements.  I would love to find similar tests for higher dimensions, but I suspect any general test will be inefficient.  (In fact, that’s a great question: Is testing for injectivity NP-hard?)

At this point, I’m ready to reveal the prize I mentioned earlier:

I am offering a US$100 award for a proof of the 4M-4 Conjecture.  Additionally, I am offering a can of Coca-Cola for a disproof of the conjecture.

Yes, this pales in comparison to the wagers of Scott Aaronson, who inspired the following disclaimer:

This award has no time limit other than my death, and is entirely at my discretion (though if you want to convince me of your proof, a good approach would be to publish it in a peer-reviewed journal article).  I might, also at my discretion, decide to split the award among several people or groups, or give a smaller award for partial progress (half a Coke?).  I don’t promise to read every claimed proof that’s emailed to me. The prize amount will not be adjusted for inflation.

For the record, these prizes are not a reflection of my belief in whether the 4M-4 Conjecture is true—I definitely believe the conjecture.  Rather, the prizes are scaled according to how much I would value the requisite mathematics.  For example, I suspect that a proof of part (a) of the conjecture will constitute a substantial contribution to mathematics, especially compared to a sneaky counterexample (can you find 4M-5 vectors that lend injectivity?).  Granted, a sneaky construction would conceivably prompt a refinement to the conjecture, which I think is definitely worth a can of Coke.  Between the two parts of the conjecture, I think part (b) is the lower-hanging fruit:  It suffices to find a polynomial for which noninjective ensembles are zeros (such a polynomial is necessarily nontrivial since the Bodmann-Hammen construction forces the polynomial to be nonzero at some point).  On the other hand, proving part (a) will be an improvement to the leading lower bound, which is based on some serious work in K-theory.

Good luck!