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.

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

Pingback: The 4M-4 conjecture is false! | Relax and Conquer

Relax and Conquer

A math research blog by Afonso S. Bandeira

A different angle to the 4M-4 conjecture

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

Leave a Reply Cancel reply

Share this:

Like this:

Related

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

Leave a Reply Cancel reply