Phase retrieval in high dimensions: Statistical and computational phase transitions
This work provides a foundational classification of statistical and algorithmic thresholds in high-dimensional phase retrieval, which is crucial for signal processing and imaging applications.
The paper tackles the phase retrieval problem of reconstructing a high-dimensional signal from noisy magnitude observations using random sensing matrices, deriving sharp asymptotics for the lowest possible estimation error and revealing phase transitions for weak- and full-recovery thresholds, with perfect recovery occurring at α=1 for real and α=2 for complex cases. It also analyzes the performance of the approximate message-passing algorithm, establishing a statistical-to-algorithmic gap dependent on the spectral properties of the matrices.
We consider the phase retrieval problem of reconstructing a $n$-dimensional real or complex signal $\mathbf{X}^{\star}$ from $m$ (possibly noisy) observations $Y_μ= | \sum_{i=1}^n Φ_{μi} X^{\star}_i/\sqrt{n}|$, for a large class of correlated real and complex random sensing matrices $\mathbfΦ$, in a high-dimensional setting where $m,n\to\infty$ while $α= m/n=Θ(1)$. First, we derive sharp asymptotics for the lowest possible estimation error achievable statistically and we unveil the existence of sharp phase transitions for the weak- and full-recovery thresholds as a function of the singular values of the matrix $\mathbfΦ$. This is achieved by providing a rigorous proof of a result first obtained by the replica method from statistical mechanics. In particular, the information-theoretic transition to perfect recovery for full-rank matrices appears at $α=1$ (real case) and $α=2$ (complex case). Secondly, we analyze the performance of the best-known polynomial time algorithm for this problem -- approximate message-passing -- establishing the existence of a statistical-to-algorithmic gap depending, again, on the spectral properties of $\mathbfΦ$. Our work provides an extensive classification of the statistical and algorithmic thresholds in high-dimensional phase retrieval for a broad class of random matrices.