Frame theory is chiefly concerned with measuring a signal by taking inner products with an ensemble of vectors, called a frame. From these inner products, various features of the signal can be analyzed, and the signal can be reconstructed. In some applications, only the magnitudes of the inner products are available. The following paper gives the fundamental limits of signal reconstruction from such “phaseless” measurements:
Radu Balan, Pete Casazza, Dan Edidin
Phaseless measurements have received considerable attention recently. Notably, Candes, Strohmer and Voroninski reported a stable and efficient reconstruction algorithm from measurements with a random ensemble of vectors; I might discuss their contribution in a later post. As for the Balan-Casazza-Edidin paper, the main point is to describe the frames for which the phaseless measurement process is injective, thereby making reconstruction possible.
The concept of injectivity in this problem requires a little care. Given a short, fat matrix , consider the corresponding “phaseless measurement” mapping defined by . Notice that . Indeed, global phase is lost in the phaseless measurement process, and so we identify signals which are equal up to a global phase factor. This is done by modding out global phase from the domain of ; in the real case and the complex unit circle in the complex case. It’s in this sense that we seek injectivity in our phaseless measurement process.
The paper uses algebraic geometry to prove the bulk of its results. Among these are two main results: one which characterizes injectivity in the real case, and one which gives a strong sufficient condition for injectivity in the complex case. The first of these results is given below, along with a simplified, non-algebro-geometric proof:
Theorem 1 (Balan, Casazza, Edidin). Take a real matrix , and consider the mapping defined by . Then is injective if and only if for every subset , either or spans.
Proof: () We seek the contrapositive: Suppose there exists an such that neither nor are spanning sets. Then there is a nonzero vector which is orthogonal to , and similarly a nonzero orthogonal to . As such, is supported on and is supported on . Since and are both nonzero, we have , but since and have disjoint support, we know the coordinates of and are equal up to signs. Thus, and so is not injective.
() Suppose , and define . Then is orthogonal to and is orthogonal to . Since either or spans by assumption, we conclude that either or is zero accordingly. Thus, and so is injective.
From this result, we can glean a bit of information about injectivity in the real case. First, we note that injectivity requires , since otherwise we can partition the ‘s into two (nearly) equal subcollections, neither of which spans. Also, we note that full spark frames necessarily satisfy the above condition, and Gassian-random frames are full spark with probability one. Thus, it is very easy to (randomly) construct frames for which the phaseless measurement process is injective in the real case. But the paper actually says something stronger than the with-probability-one statement: It shows that generic real short, fat matrices lend injectivity. Here, a generic real matrix is a member of some undisclosed Zarski-open (dense and full-measure) subset of the Grassmannian .
For the complex case, the paper falls short of providing a characterization like Theorem 1. Instead, it gives the following result:
Theorem 2 (Balan, Casazza, Edidin). Take a generic complex matrix , and consider the mapping defined by . Then is injective provided .
Considering the use of “generic,” the proof of this result is inherently algebro-geometric, but the crux of the argument is a matter of counting variables and constraints; at least, this is where the comes from. The authors conjecture that is the optimal bound in the complex case, just like was the optimal bound in the real case. Another paper showed that injectivity requires , and this has led some to wonder whether is actually the optimal bound.
Incidentally, is not optimal in general because when , we can get injectivity from phaseless measurements. As an example, the following short, fat matrix lends injectivity:
Here, injectivity follows from the fact that is a projective 2-design (by Theorem 5 of this paper), and in fact, Theorem 3.4 of this paper gives a painless reconstruction formula for any such projective 2-design.
I’ll conclude by demonstrating the necessity of , thereby disproving the optimality of . To do this, I appeal to Theorem 2 of yet another paper, which says that complex projective space does not embed into , where is the number of ‘s in the binary expansion of . With this theorem in mind, suppose were injective. Then defined by embeds into , implying that
In fact, in the special case where , we have , and so an injective must have . This shows that the bound in Theorem 2 above is at least nearly tight, but determining the optimal bound remains an open problem.