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.

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

Pingback: Quantum mechanics and phase retrieval « Short, Fat Matrices
Pingback: ESI 2012: Phase Retrieval « Short, Fat Matrices
Pingback: Phase retrieval with polarization « Short, Fat Matrices
Pingback: Phase retrieval from power spectra of masked signals | Short, Fat Matrices

	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…

Share this:

Like this:

Related

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

Leave a Reply Cancel reply