Phaseless reconstruction with polarization: The noiseless case

In the post before last, I reviewed a paper that showed that almost all ensembles of N\geq 4M-2 vectors in \mathbb{C}^M 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 x\in\mathbb{C}^M (up to a global phase factor) from measurements of the form \{|\langle x,\varphi_n\rangle|^2\}_{n=1}^N. Specifically, we wish to use the fewest measurements possible, namely N=\mathcal{O}(M).

Take a finite set V, and suppose we take phaseless measurements of x\in\mathbb{C}^M with a frame \Phi_V:=\{\varphi_i\}_{i\in V}\subseteq\mathbb{C}^M. Having |\langle x,\varphi_i\rangle| for every i\in V, 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 c_i=|\langle x,\varphi_i\rangle| to have positive phase. If \langle x,\varphi_j\rangle is also nonzero, then it has well-defined relative phase

\displaystyle{\omega_{ij}:=\big(\tfrac{\langle x,\varphi_i\rangle}{|\langle x,\varphi_i\rangle|}\big)^{-1}\tfrac{\langle x,\varphi_j\rangle}{|\langle x,\varphi_j\rangle|}},

which determines the frame coefficent by multiplication: c_j=\omega_{ij}|\langle x,\varphi_j\rangle|. Otherwise when \langle x,\varphi_j\rangle=0, we naturally take c_j=0, and for notational convenience, we arbitrarily take \omega_{ij}=1. From here, the original signal’s up-to-global-phase equivalence class [x]\in\mathbb{C}^M/\!\!\sim can be identified by applying the canonical dual frame \{\tilde{\varphi}_j\}_{j\in V}, namely the Moore-Penrose pseudoinverse, of \Phi_V:

\displaystyle{\sum_{j\in V}c_j\tilde{\varphi}_j=\sum_{j\in V}\omega_{ij}|\langle x,\varphi_j\rangle|\tilde{\varphi}_j=\big(\tfrac{\langle x,\varphi_i\rangle}{|\langle x,\varphi_i\rangle|}\big)^{-1}\sum_{j\in V}\langle x,\varphi_j\rangle\tilde{\varphi}_j=\big(\tfrac{\langle x,\varphi_i\rangle}{|\langle x,\varphi_i\rangle|}\big)^{-1}x\in[x]}.

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 \omega:=\mathrm{e}^{2\pi\mathrm{i}/3}. Then for any a,b\in\mathbb{C},

\displaystyle{\bar{a}b=\frac{1}{3}\sum_{k=0}^2\omega^k|a+\omega^{-k}b|^2}.

We can use this polarization identity to determine relative phase:

\displaystyle{\overline{\langle x,\varphi_i\rangle}\langle x,\varphi_j\rangle=\frac{1}{3}\sum_{k=0}^2\omega^{k}\big|\langle x,\varphi_i\rangle+\omega^{-k}\langle x,\varphi_j\rangle\big|^2=\frac{1}{3}\sum_{k=0}^2\omega^{k}\big|\langle x,\varphi_i+\omega^{k}\varphi_j\rangle\big|^2}.

Thus, if in addition to \Phi_V, we measure with \{\varphi_i+\omega^{k}\varphi_j\}_{k=0}^2, we can use the above trick to determine \overline{\langle x,\varphi_i\rangle}\langle x,\varphi_j\rangle and then normalize to get the relative phase \omega_{ij}, provided both \langle x,\varphi_i\rangle and \langle x,\varphi_j\rangle are nonzero. To summarize, if we measure with \Phi_V and \{\varphi_i+\omega^{k}\varphi_j\}_{k=0}^2 for every pair i,j\in V, then we can recover [x]. However, such a method uses |V|+3\binom{|V|}{2} measurements, and since \Phi_V is a frame, we necessarily have |V|\geq M and thus a total of \Omega(M^2) measurements.

In pursuit of \mathcal{O}(M) measurements, take some simple graph G=(V,E), arbitrarily assign a direction to each edge, and only take measurements with \Phi_V and \Phi_E:=\bigcup_{(i,j)\in E}\{\varphi_i+\omega^{k}\varphi_j\}_{k=0}^2. To recover [x], 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 x 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 G is a star, then x could be orthogonal to the vector corresponding to the internal vertex, whose removal would render the remaining graph edgeless. That said, we should select \Phi_V and G so as to minimize the impact of orthogonality with vertex vectors.

First, we can take \Phi_V to be full spark, that is, \Phi_V has the property that every subcollection of M frame elements spans.  Here, \Phi_V being full spark will be useful for two reasons. First, this implies that x is orthogonal to at most M-1 members of \Phi_V, thereby limiting the extent of x‘s damage to our graph. Additionally, \Phi_V being full spark frees us from requiring the graph to be connected after the removal of vertices; indeed, any remaining component of size M or more will correspond to a subframe of \Phi_V that necessarily has a dual frame to reconstruct with. It remains to find a graph of \mathcal{O}(M) vertices and edges that maintains a size-M component after the removal of any M-1 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 d-regular graph G of n vertices, consider its adjacency matrix A, and define the Laplacian to be L:=I-\frac{1}{d}A. We are particularly interested in the eigenvalues of the Laplacian: 0=\lambda_1\leq\cdots\leq\lambda_n. The second eigenvalue \lambda_2 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 G has expansion \lambda if \{\lambda_2,\ldots,\lambda_n\}\subseteq[1-\lambda,1+\lambda]; note that since 1-\lambda\leq\lambda_2, small expansion implies large spectral gap. Furthermore, a family of d-regular graphs \{G_i\}_{i=1}^\infty is a spectral expander family if there exists c<1 such that every G_i has expansion \lambda(G_i)\leq c. Since d 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 d-regular graph G of n vertices with spectral gap \lambda_2.  For all \varepsilon\leq\frac{\lambda_2}{6}, removing any \varepsilon dn edges from G results in a connected component of size \geq(1-\frac{2\varepsilon}{\lambda_2})n.

For our application, removing \varepsilon n vertices from a d-regular graph necessarily removes \leq\varepsilon dn edges, and so this lemma directly applies. More specifically, we want to guarantee that the removal of any M-1 vertices maintains a size-M component.  To do this, we will ensure both M-1\leq\varepsilon n and M-1<(1-\frac{2\varepsilon}{\lambda_2})n and invoke the above lemma.  Note that since n\geq M\geq2,

\displaystyle{\varepsilon\leq\frac{\lambda_2}{6}\leq\frac{\mathrm{Tr}[L]}{6(n-1)}=\frac{n}{6(n-1)}\leq\frac{1}{3}<\frac{2}{3}\leq 1-\frac{2\varepsilon}{\lambda_2}},

where the last inequality is a rearrangement of \varepsilon\leq\frac{\lambda_2}{6}. Thus, it suffices to have M\leq\varepsilon n+1.  Overall, we use the following criteria to pick our expander graph: Given the signal dimension M, use a d-regular graph G=(V,E) of n vertices with spectral gap \lambda_2 such that M\leq(\frac{\lambda_2}{6})n+1. Then by the previous discussion, the total number of measurements is N=|V|+3|E|=(\frac{3}{2}d+1)n.

Recall that we seek N=\mathcal{O}(M) measurements. To minimize the redundancy \frac{N}{M} for a fixed degree d, we would like a maximal spectral gap \lambda_2, and it suffices to seek minimal spectral expansion \lambda. Spectral graph families known as Ramanujan graphs are asymptotically optimal in this sense; taking \mathcal{G}_n^d to be the set of connected d-regular graphs with \geq n vertices, Alon and Boppana showed that for any fixed d,

\displaystyle{\lim_{n\rightarrow\infty}\inf_{G\in\mathcal{G}_n^d}\lambda(G)\geq\frac{2\sqrt{d-1}}{d}},

while Ramanujan graphs are defined to have spectral expansion \leq\frac{2\sqrt{d-1}}{d}. To date, Ramanujan graphs have only been constructed for certain values of d. One important construction was given by Lubotzky, Phillips and Sarnak, which produces a Ramanujan family whenever d-1\equiv 1\bmod4 is prime. Among these graphs, we get the smallest redundancy \frac{N}{M} when M=\lfloor(1-\frac{2\sqrt{d-1}}{d})\frac{n}{6}+1\rfloor and d=6:

\displaystyle{\frac{N}{M}\leq\frac{(\frac{3}{2}d+1)n}{(1-\frac{2\sqrt{d-1}}{d})\frac{n}{6}}=45\big(3+\sqrt{5}\big)\approx 235.62}.

Thus, in such cases, our techniques allow for phaseless reconstruction with only N\leq 236M measurements. However, the number of vertices in each Ramanujan graph from this construction is of the form q(q^2-1) or \frac{q(q^2-1)}{2}, where q\equiv1\bmod4 is prime, and so any bound on redundancy \frac{N}{M} using these graphs will only be valid for particular values of M.

In order to get N=\mathcal{O}(M) in general, we use the fact that random graphs are nearly Ramanujan with high probability. Without going into the details, this gives N\leq 240 M. 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.

Advertisements

4 thoughts on “Phaseless reconstruction with polarization: The noiseless case

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s