On signal reconstruction without phase

Posted on by Dustin G. Mixon

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:

On signal reconstruction without phase

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 \Phi=[\varphi_1\cdots\varphi_N], consider the corresponding “phaseless measurement” mapping \mathcal{A} defined by (\mathcal{A}(x))[n]:=|\langle x,\varphi_n\rangle|^2. Notice that \mathcal{A}(x)=\mathcal{A}(-x). 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 \mathcal{A}; \{\pm 1\} in the real case and the complex unit circle \mathbb{T} 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 M\times N matrix \Phi=[\varphi_1\cdots\varphi_N], and consider the mapping \mathcal{A}:\mathbb{R}^M/\{\pm 1\}\rightarrow\mathbb{R}_{\geq0}^N defined by (\mathcal{A}(x))[n]:=|\langle x,\varphi_n\rangle|^2. Then \mathcal{A} is injective if and only if for every subset S\subseteq\{1,\ldots,N\}, either \{\varphi_n\}_{n\in S} or \{\varphi_n\}_{n\in S^\mathrm{c}} spans.

Proof: (\Rightarrow) We seek the contrapositive: Suppose there exists an S such that neither \{\varphi_n\}_{n\in S} nor \{\varphi_n\}_{n\in S^\mathrm{c}} are spanning sets. Then there is a nonzero vector x which is orthogonal to \{\varphi_n\}_{n\in S}, and similarly a nonzero y orthogonal to \{\varphi_n\}_{n\in S^\mathrm{c}}. As such, \Phi^*x is supported on S^\mathrm{c} and \Phi^*y is supported on S. Since x and y are both nonzero, we have x+y\neq\pm(x-y), but since \Phi^*x and \Phi^*y have disjoint support, we know the coordinates of \Phi^*(x+y) and \Phi^*(x-y) are equal up to signs. Thus, \mathcal{A}(x+y)=\mathcal{A}(x-y) and so \mathcal{A} is not injective.

(\Leftarrow) Suppose \mathcal{A}(x)=\mathcal{A}(y), and define S:=\{n:\langle x,\varphi_n\rangle=-\langle y,\varphi_n\rangle\}. Then x+y is orthogonal to \{\varphi_n\}_{n\in S} and x-y is orthogonal to \{\varphi_n\}_{n\in S^\mathrm{c}}. Since either \{\varphi_n\}_{n\in S} or \{\varphi_n\}_{n\in S^\mathrm{c}} spans by assumption, we conclude that either x+y or x-y is zero accordingly. Thus, x=\pm y and so \mathcal{A} is injective.     \Box

From this result, we can glean a bit of information about injectivity in the real case. First, we note that injectivity requires N\geq 2M-1, since otherwise we can partition the \varphi_n‘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 M\times N matrix is a member of some undisclosed Zarski-open (dense and full-measure) subset of the Grassmannian \mathrm{Gr}(M,N).

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 M\times N matrix \Phi=[\varphi_1\cdots\varphi_N], and consider the mapping \mathcal{A}:\mathbb{C}^M/\mathbb{T}\rightarrow\mathbb{R}_{\geq0}^N defined by (\mathcal{A}(x))[n]:=|\langle x,\varphi_n\rangle|^2. Then \mathcal{A} is injective provided N\geq 4M-2.

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 4M-2 comes from. The authors conjecture that 4M-2 is the optimal bound in the complex case, just like 2M-1 was the optimal bound in the real case. Another paper showed that injectivity requires N\geq 3M-2, and this has led some to wonder whether 3M-2 is actually the optimal bound.

Incidentally, 4M-2 is not optimal in general because when M=2, we can get injectivity from N=4<6=4M-2 phaseless measurements. As an example, the following short, fat matrix lends injectivity:

\displaystyle{\Phi=\left[\begin{array}{llll}1\qquad&\sqrt{\frac{1}{3}}\qquad&\sqrt{\frac{1}{3}}\qquad&\sqrt{\frac{1}{3}}\qquad\\ 0&\sqrt{\frac{2}{3}}&\sqrt{\frac{2}{3}}e^{2\pi i/3}&\sqrt{\frac{2}{3}}e^{4\pi i/3}\end{array}\right]}.

Here, injectivity follows from the fact that \Phi 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 N\geq(4+o(1))M, thereby disproving the optimality of 3M-2. To do this, I appeal to Theorem 2 of yet another paper, which says that complex projective space \mathbb{C}\mathrm{P}_n does not embed into \mathbb{R}^{4n-2\alpha(n)}, where \alpha(n) is the number of 1‘s in the binary expansion of n. With this theorem in mind, suppose \mathcal{A}:\mathbb{C}^M/\mathbb{T}\rightarrow\mathbb{R}_{\geq0}^N were injective. Then \mathcal{B} defined by \mathcal{B}(x):=\mathcal{A}(x)/\|x\|^2 embeds \mathbb{C}\mathrm{P}_{M-1} into \mathbb{R}^N, implying that

\displaystyle{N>4(M-1)-2\alpha(M-1)\geq4M-C\log M}.

In fact, in the special case where M=2^k+1, we have \alpha(M-1)=1, and so an injective \mathcal{A} must have N\geq 4M-5. This shows that the bound in Theorem 2 above is at least nearly tight, but determining the optimal bound remains an open problem.