A different angle to the 4M-4 conjecture

Since we posed the {4M-4} conjecture (see here) almost a year ago, it has received some attention. In fact, a solution to part (b) of the conjecture appeared just a couple of weeks ago (see the paper here). Part (a), however, remains unsolved (despite the monetary motivation offered for its solution!). In this post I will describe an approach I think might have a chance at tackling part (a) of the {4M-4} conjecture. I was not able to make the approach work (otherwise this blog post would be quite different 🙂 ) but maybe someone else can. Before going into the approach a bit of context is in order.

You can read all about the {4M-4} conjecture in Dustin’s nice blog post about it so I’ll be brief. The problem concerns the optimal number {N^\ast(M)} of phaseless measurements needed to characterize (up to global phase) a complex vector {x\in\mathbb{C}^M}. More precisely, determining the smallest integer {N = N^*(M)} for which there exists a set of {N} vectors {\{\varphi_n\}_{n=1}^{N}} such that the map

\displaystyle x\in\mathbb{C}^{M} \rightarrow \{|\langle x,\varphi_n\rangle|^2\}_{n=1}^{N},

is injective up to global phase (trivially, {x} and {\omega x}, for a unit-modulus complex number {\omega}, will be indistinguishable by these measurements). The {4M-4} conjecture is essentially saying, as the name suggests, that {N^\ast(M) = 4M-4}:

Conjecture 1 (The {4M-4} Conjecture)(a) If {N< 4M-4}, then {x\in\mathbb{C}^{M} \rightarrow \{|\langle x,\varphi_n\rangle|^2\}_{n=1}^{N}} is not injective.

(b) If {N> 4M-4}, then {x\in\mathbb{C}^{M} \rightarrow \{|\langle x,\varphi_n\rangle|^2\}_{n=1}^{N}} is injective for a generic set of vectors {\{\varphi\}_{n=1}^{N}}.

As I said above, part (b) was solved here. We will be focusing on part (a).

The approach that I am about to describe is based on a, in my opinion, surprising relation between the injectivity of phaseless measurements and the injectivity of “scaleless” measurements described by Theorem 5 in this paper. Given a set of vectors {\{\varphi_n\}_{n=1}^{N}}, we define the map {\mathcal{B}:x\in\mathbb{C}^{M} \rightarrow \{\mathrm{arg}\left(\langle x,\varphi_n\rangle^2\right)\}_{n=1}^{N}} where {\mathrm{arg}} takes the value {0} when it’s not well-defined. Theorem {5}, in here, states that {\{|\langle x,\varphi_n\rangle|^2\}_{n=1}^{N}} is injective if and only iff {\mathcal{B}} is injective in the following sense: If for every {n=1,...,N} there exists {\alpha_n\in\mathbb{R}} and {\beta_n\in\mathbb{R}} not both zero such that {\alpha_n\langle x,\varphi_n\rangle^2 = \beta_n\langle x,\varphi_n\rangle^2} then there must exist {a\in\mathbb{R}} and {b\in\mathbb{R}} not both zero such that {ax = by}.

My suggestion is to tackle the {4M-4} conjecture through this equivalence by looking at the injectivity of {\mathcal{B}}. Why do I think the injectivity of {\mathcal{B}} should be easier to understand? Because, unlike Phase Retrieval, inverting {\mathcal{B}} is an easy problem, as easy as solving a linear system.

The main contribution of this blog post is the following Conjecture which implies part (a) of the {4M-4} Conjecture:

Conjecture 2 ({4M-4} Angle Conjecture) Let {N< 4M-4}. For any {\Phi = [\varphi_1,\dots,\varphi_N]^\ast\in\mathbb{C}^{N\times M}} there exists a full-rank diagonal matrix {D\in \mathbb{C}^{N\times N}} such that {[\Phi\ D]\in\mathbb{C}^{N\times (M+N)}} has two non-zero independent vectors in the nullspace both with the last {N} coordinates in {\mathbb{R}}.

Theorem 3 The {4M-4} Angle Conjecture implies part (a) of the {4M-4} Conjecture.

\proof{ Suppose the Conjecture is true. Then, given {\Phi\in\mathbb{C}^{N\times M}}, let {D} be the diagonal matrix and {z_1,z_2} the two vectors in {\mathcal{N}([\Phi\ D])}. Also, let {x} and {y} be the vectors corresponding to the first {M} coordinates of, respectively, {z_1} and {z_2}. Similarly, let {\beta} and {\alpha} be the real vectors corresponding to the last {N} coordinates. It’s easy to see that {z_1} and {z_2} being non-zero and independent (together with the fact that {D_i} is full-rank) implies that {x} and {y} are not a real multiple of each other. Yet, for every {n=1,\dots,N}, {\langle x,\varphi_n\rangle = -D_{nn}\beta_n} and {\langle y,\varphi_n\rangle = -D_{nn}\alpha_n} meaning that {\alpha_n\langle x,\varphi_n\rangle = \beta_n\langle y,\varphi_n\rangle}. This implies the non-injectivity of {\mathcal{B}} and concludes the proof.

QED

This problems seems to be related to the question of existence of vectors with real entries on the nullspace of a complex matrix. A question for the readers: have you seen a similar problem elsewhere?

This formulation can be easily transformed into a problem just concerning real linear algebra (by the natural “Realification” obtained by simply transforming each complex variable in {2} real variables) but it’s unclear that such a transformation brings any useful insight.

Advertisements

One thought on “A different angle to the 4M-4 conjecture

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