In the post before last, I reviewed a paper that showed that almost all ensembles of vectors in produce injective phaseless measurements. In the present post, I’ll describe a phaseless reconstruction technique about which I’m currently writing a paper with Boris Alexeev, Afonso Bandeira and Matt Fickus. Here, I’ll specifically address the noiseless case; we’ve modified the procedure to be provably stable (this is the main subject of our paper), but the major ideas are easier to understand in the noiseless case. Perhaps I’ll discuss the modifications we make in a future post.
Recall: We seek to reconstruct a signal (up to a global phase factor) from measurements of the form . Specifically, we wish to use the fewest measurements possible, namely .
Take a finite set , and suppose we take phaseless measurements of with a frame . Having for every , we claim it suffices to determine the relative phase between all pairs of frame coefficients. Indeed, if we had this information, we could arbitrarily assign some nonzero frame coefficient to have positive phase. If is also nonzero, then it has well-defined relative phase
which determines the frame coefficent by multiplication: . Otherwise when , we naturally take , and for notational convenience, we arbitrarily take . From here, the original signal’s up-to-global-phase equivalence class can be identified by applying the canonical dual frame , namely the Moore-Penrose pseudoinverse, of :
Now that we understand that relative phase between frame coefficients is useful, how do we extract this information? We’ll use a special version of the polarization identity:
Lemma 1. Take . Then for any ,
We can use this polarization identity to determine relative phase:
Thus, if in addition to , we measure with , we can use the above trick to determine and then normalize to get the relative phase , provided both and are nonzero. To summarize, if we measure with and for every pair , then we can recover . However, such a method uses measurements, and since is a frame, we necessarily have and thus a total of measurements.
In pursuit of measurements, take some simple graph , arbitrarily assign a direction to each edge, and only take measurements with and . To recover , we again arbitrarily assign some nonzero vertex measurement to have positive phase, and then we propagate relative phase information along the edges by multiplication to determine the phase of the other vertex measurements relative to the original vertex measurement. However, if is orthogonal to a given vertex vector, then that measurement is zero, and so relative phase information cannot propagate through the corresponding vertex; indeed, such orthogonality has the effect of removing the vertex from the graph, and for some graphs, this will prevent recovery. For example, if is a star, then could be orthogonal to the vector corresponding to the internal vertex, whose removal would render the remaining graph edgeless. That said, we should select and so as to minimize the impact of orthogonality with vertex vectors.
First, we can take to be full spark, that is, has the property that every subcollection of frame elements spans. Here, being full spark will be useful for two reasons. First, this implies that is orthogonal to at most members of , thereby limiting the extent of ‘s damage to our graph. Additionally, being full spark frees us from requiring the graph to be connected after the removal of vertices; indeed, any remaining component of size or more will correspond to a subframe of that necessarily has a dual frame to reconstruct with. It remains to find a graph of vertices and edges that maintains a size- component after the removal of any vertices.
To this end, we consider a well-studied family of sparse graphs known as expander graphs. We choose these graphs for their notably strong connectivity properties. There is a combinatorial definition of expander graphs, but we will focus on the spectral definition. Given a -regular graph of vertices, consider its adjacency matrix , and define the Laplacian to be . We are particularly interested in the eigenvalues of the Laplacian: . The second eigenvalue of the Laplacian is called the spectral gap of the graph, and as we shall see, this value is particularly useful in evaluating the graph’s connectivity. We say has expansion if ; note that since , small expansion implies large spectral gap. Furthermore, a family of -regular graphs is a spectral expander family if there exists such that every has expansion . Since is constant over an expander family, we see that expanders with many vertices are particularly sparse. There are many results which describe the connectivity of expanders, but the following is particularly relevant to our application:
Lemma 2. Consider a -regular graph of vertices with spectral gap . For all , removing any edges from results in a connected component of size .
For our application, removing vertices from a -regular graph necessarily removes edges, and so this lemma directly applies. More specifically, we want to guarantee that the removal of any vertices maintains a size- component. To do this, we will ensure both and and invoke the above lemma. Note that since ,
where the last inequality is a rearrangement of . Thus, it suffices to have . Overall, we use the following criteria to pick our expander graph: Given the signal dimension , use a -regular graph of vertices with spectral gap such that . Then by the previous discussion, the total number of measurements is .
Recall that we seek measurements. To minimize the redundancy for a fixed degree , we would like a maximal spectral gap , and it suffices to seek minimal spectral expansion . Spectral graph families known as Ramanujan graphs are asymptotically optimal in this sense; taking to be the set of connected -regular graphs with vertices, Alon and Boppana showed that for any fixed ,
while Ramanujan graphs are defined to have spectral expansion . To date, Ramanujan graphs have only been constructed for certain values of . One important construction was given by Lubotzky, Phillips and Sarnak, which produces a Ramanujan family whenever is prime. Among these graphs, we get the smallest redundancy when and :
Thus, in such cases, our techniques allow for phaseless reconstruction with only measurements. However, the number of vertices in each Ramanujan graph from this construction is of the form or , where is prime, and so any bound on redundancy using these graphs will only be valid for particular values of .
In order to get in general, we use the fact that random graphs are nearly Ramanujan with high probability. Without going into the details, this gives . While the desired expansion properties of a random graph are only present with high probability, estimating the spectral gap is inexpensive, and so it is computationally feasible to verify whether a randomly drawn graph is good enough.