Phase retrieval in high dimensions: Statistical and computational phase transitions

arXiv2006.05228MaRDI QIDQ6342452FDOQ6342452

Bruno Loureiro, Florent Krzakala, Antoine Maillard, Lenka Zdeborová

Publication date: 9 June 2020

Abstract: We consider the phase retrieval problem of reconstructing a $n$-dimensional real or complex signal $mathbf{X}^{star}$ from $m$ (possibly noisy) observations $Y_{m}u=|su{m}_{i=1}^{n}Ph{i}_{mui}{X}_i^{star}/sqrtn|$, for a large class of correlated real and complex random sensing matrices $mathbfPhi$, in a high-dimensional setting where $m,noinfty$ while $alpha=m/n=Theta(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 $mathbfPhi$. 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 $alpha=1$ (real case) and $alpha=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 $mathbfPhi$. Our work provides an extensive classification of the statistical and algorithmic thresholds in high-dimensional phase retrieval for a broad class of random matrices.

Has companion code repository: https://github.com/sphinxteam/PhaseRetrieval_demo

This page was built for publication: Phase retrieval in high dimensions: Statistical and computational phase transitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6342452)