The Condition Number in Phase Retrieval from Intensity Measurements

Abstract

This paper investigates the stability of phase retrieval by analyzing the condition number of the nonlinear map ${\Psi }_{\mathbf{A}}(\mathbf{x})=(|⟨{\mathbf{a}}_j,\mathbf{x}⟩{|}^2{)}_{1\le j\le m}$, where ${\mathbf{a}}_j\in {\mathbb{H}}^n$ are known sensing vectors with $\mathbb{H}\in \{\mathbb{R},\mathbb{C}\}$. For each $p\ge 1$, we define the condition number ${\beta }_{{\Psi }_{\mathbf{A}}}^{{\ell }_p}$ as the ratio of optimal upper and lower Lipschitz constants of ${\Psi }_{\mathbf{A}}$ measured in the ${\ell }_p$ norm, with respect to the metric ${\mathrm{dist}}_{\mathbb{H}}\left(\mathbf{x},\mathbf{y}\right)=\Vert \mathbf{x}{\mathbf{x}}^{\ast }-\mathbf{y}{\mathbf{y}}^{\ast }{\Vert }_{\ast }$. We establish universal lower bounds on ${\beta }_{{\Psi }_{\mathbf{A}}}^{{\ell }_p}$ for any sensing matrix $\mathbf{A}\in {\mathbb{H}}^{m\times d}$, proving that ${\beta }_{{\Psi }_{\mathbf{A}}}^{{\ell }_1}\ge \pi /2$ and ${\beta }_{{\Psi }_{\mathbf{A}}}^{{\ell }_2}\ge \sqrt{3}$ in the real case $(\mathbb{H}=\mathbb{R})$, and ${\beta }_{{\Psi }_{\mathbf{A}}}^{{\ell }_p}\ge 2$ for $p=1,2$ in the complex case $(\mathbb{H}=\mathbb{C})$. These bounds are shown to be asymptotically tight: both a deterministic harmonic frame ${\mathbf{E}}_m\in {\mathbb{R}}^{m\times 2}$ and Gaussian random matrices $\mathbf{A}\in {\mathbb{H}}^{m\times d}$ asymptotically attain them. Notably, the harmonic frame ${\mathbf{E}}_m\in {\mathbb{R}}^{m\times 2}$ achieves the optimal lower bound $\sqrt{3}$ for all $m\ge 3$ when $p=2$, thus serving as an optimal sensing matrix within $\mathbf{A}\in {\mathbb{R}}^{m\times 2}$. Our results provide the first explicit uniform lower bounds on ${\beta }_{{\Psi }_{\mathbf{A}}}^{{\ell }_p}$ and offer insights into the fundamental stability limits of phase retrieval.