Since we posed the 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 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 conjecture in Dustin’s nice blog post about it so I’ll be brief. The problem concerns the optimal number of phaseless measurements needed to characterize (up to global phase) a complex vector . More precisely, determining the smallest integer for which there exists a set of vectors such that the map

is injective up to global phase (trivially, and , for a unit-modulus complex number , will be indistinguishable by these measurements). The conjecture is essentially saying, as the name suggests, that :

Conjecture 1 (The Conjecture)(a) If , then is not injective.

(b) If , then is injective for a generic set of vectors .

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 , we define the map where takes the value when it’s not well-defined. Theorem , in here, states that is injective if and only iff is injective in the following sense: If for every there exists and not both zero such that then there must exist and not both zero such that .

My suggestion is to tackle the conjecture through this equivalence by looking at the injectivity of . Why do I think the injectivity of should be easier to understand? Because, unlike Phase Retrieval, inverting 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 Conjecture:

Conjecture 2 ( Angle Conjecture)Let . For any there exists a full-rank diagonal matrix such that has two non-zero independent vectors in the nullspace both with the last coordinates in .

Theorem 3The Angle Conjecture implies part (a) of the Conjecture.

\proof{ Suppose the Conjecture is true. Then, given , let be the diagonal matrix and the two vectors in . Also, let and be the vectors corresponding to the first coordinates of, respectively, and . Similarly, let and be the real vectors corresponding to the last coordinates. It’s easy to see that and being non-zero and independent (together with the fact that is full-rank) implies that and are not a real multiple of each other. Yet, for every , and meaning that . This implies the non-injectivity of 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 real variables) but it’s unclear that such a transformation brings any useful insight.

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