Timezone: »

 
Poster
Phase retrieval in high dimensions: Statistical and computational phase transitions
Antoine Maillard · Bruno Loureiro · Florent Krzakala · Lenka Zdeborová

Tue Dec 08 09:00 AM -- 11:00 AM (PST) @ Poster Session 1 #268
in Poster Session 2 »
We consider the phase retrieval problem of reconstructing a $n$-dimensional real or complex signal $\mathbf{X}^\star$ from $m$ (possibly noisy) observations $Y_\mu = | \sum_{i=1}^n \Phi_{\mu i} X^{\star}_i/\sqrt{n}|$, for a large class of correlated real and complex random sensing matrices $\mathbf{\Phi}$, in a high-dimensional setting where $m,n\to\infty$ 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 $\mathbf{\Phi}$. 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 statistical-to-algorithmic gap depending, again, on the spectral properties of $\mathbf{\Phi}$. Our work provides an extensive classification of the statistical and algorithmic thresholds in high-dimensional phase retrieval for a broad class of random matrices.

Author Information

Antoine Maillard (Ecole Normale Supérieure)
Bruno Loureiro (EPFL)
Florent Krzakala (ENS Paris, Sorbonnes Université & EPFL)
Lenka Zdeborová (EPFL)

More from the Same Authors