Injectivity and Stability of Phase Retrieval (problems 19-21)

Throughout this post $\mathbb{K}$ will stand for either $\mathbb{R}$ or $\mathbb{C}$.

Given $A\in\mathbb{K}^{N\times M}$, the Phase Retrieval Problem aims to recover a vector $x\in\mathbb{K}^M$ from $|Ax|$, where $| \cdot |$ is the entrywise modulus. In other words, one has access to the modulus of $N$ linear measurements, and the goal is to recover $x\in\mathbb{K}^M$. Let $\mathbb{T}_{\mathbb{K}}$ denote the unit torus in $\mathbb{K}$ (corresponding to the unit circle in $\mathbb{C}$ or $\{\pm1\}$ in $\mathbb{R}$).

One can only hope to recover $x$ modulo $\mathbb{T}_{ \mathbb K }$ (meaning up to a global phase shift in $\mathbb{C}$ or a global sign flip in $\mathbb{R}$).

We say $A$ is injective for phase retrieval (for $\mathbb{K}$) if the map

\[\\ \mathcal{A}:x \bmod \mathbb{T}_\mathbb{K} \mapsto |Ax|, \\\]

is injective.

In 2013 a few collaborators and I (Bandeira et al., 2014) conjectured that $N\geq 4M-4$ linear measurements were necessary for injectivity over $\mathbb{C}$, and that generic $4M-4$ measurements were injective. While the second part of this conjecture was proven in (Conca et al., 2015), the first was shown to be false when Cynthia Vinzant found an injective set of $11$ linear measurements in $\mathbb{C}^4$ (Vinzant, 2015). In fact, a prize was awarded for this finding. Cynthia stated a refined version of the conjecture that still remains open (see here)

Conjecture 19 (Phase Retrieval injectivity at $4M-5$)

Let $N=4M-5$ and draw $A\in\mathbb{C}^{N\times M}$ at random (here the important thing is for $ \mathrm{im}(A) $ to be drawn uniformly from the Grassmannian of $ M $-dimensional subspaces of $ \mathbb{C}^{4M-5}$, it can e.g. be with iid gaussian entries). Let $p_M$ be the probability that the mapping $ x \bmod \mathbb{T} \mapsto |Ax|^2 $ is injective.
(a): $ p_M < 1 $ for all $ M $.
(b): $ \displaystyle\lim_{M \to \infty} p_M = 0 $.

Over $\mathbb{R}$ the question of injectivity is significantly easier and it is known that $N\geq 2M-1$ is necessary that that generic $2M-1$ measurements are injective. A crucial step in the proof of this statement is the fact that any partition of the rows of $A^{(2M-1)\times M}$ into two sets yields one set that spans $\mathbb{R}^M$. This is known as the complement property (see, e.g., (Bandeira et al., 2014)).

A natural question is whether such phaseless measurements allow for stable reconstruction of $x$. In this direction, Balan and Wang (Balan & Wang, 2013) showed that stability of the map $\mathcal{A}$ is related to the condition number of subsets of rows of $A$ that span $\mathbb{R}^M$.

Definition 1

Given $A\in\mathbb{R}^{N\times M}$ let $\omega(A)$ be defined as \begin{equation} \omega(A) = \min_{S\subseteq [N]:\, \mathrm{rank}(A_{S^c})<n} \sigma_M(A_S), \end{equation} where $A_S$ denotes the submatrix made of the rows indexed by $S$ and $\sigma_M$ is the $M$-th singular value (which is the smallest in non-degenerate situations).

The complement property says that $\mathcal{A}$ is injective if and only if $\omega(A)>0$. (Balan & Wang, 2013) shows that stability is tightly connected to the inverse of this quantity. They also make the following intriguing conjecture.

Conjecture 20 (Stability of Phase Retrieval at $2M-1$)

There exist universal constants $C>0$ and $0<\beta<1$ such that, for any $M>1$ and $A\in\mathbb{R}^{2M-1\times M}$ a matrix for which any subset of $M$ rows spans $\mathbb{R}^M$, \(\\ \omega(A) \leq C \max_{k\in[N]}\|A_k\|\beta^M, \\\) where $A_k$ is the $k$-th row of $A$.

This also motivates the following question (for which I do not know the state of the art, but a quick search did not reveal that the answer is already known).

Open Problem 21

What is the value of $\omega(A)$ for $A$ with iid standard gaussian entries? Does it satisfy the bound in the conjecture? If so, what is $\beta$?

Acknowledgments: I would like to thank Mitchell Taylor from bringing the Balan-Yang conjecture to my attention.

References

1. Bandeira, A. S., Cahil, J., Mixon, D. G., & Nelson, A. A. (2014). Saving phase: Injectivity and stability for phase retrieval. Applied and Computational Harmonic Analysis (ACHA), 37, 106–125.
2. Conca, A., Edidin, D., Hering, M., & Vinzant, C. (2015). An algebraic characterization of injectivity in phase retrieval. Applied and Computational Harmonic Analysis, 38(2), 346–356. https://doi.org/10.1016/j.acha.2014.06.005
3. Vinzant, C. (2015). A small frame and a certificate of its injectivity. 2015 International Conference on Sampling Theory and Applications (SampTA), 197–200. https://doi.org/10.1109/SAMPTA.2015.7148901
4. Balan, R., & Wang, Y. (2013). Invertibility and Robustness of Phaseless Reconstruction. ArXiv Preprint ArXiv:1308.4718. https://arxiv.org/abs/1308.4718