Abstract

We consider the phase retrieval problem of reconstructing a n-dimensional real or complex signal X* from m (possibly noisy) observations Y= |F X|, for a large class of correlated real and complex random sensing matrices F, in a high-dimensional setting where m,n are large while α=m/n=Θ(1). First, we derive sharp asymptotic 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 F. 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 F. Our work provides an extensive classification of the statistical and algorithmic thresholds in high-dimensional phase retrieval for a broad class of random matrices. Finally, we will discuss the design of optimal spectral methods in phase retrieval, a powerful tool which can be used as initialization for a subsequent algorithm, at a low computational cost. This talk will be based on the papers: https://arxiv.org/abs/2006.05228, https://arxiv.org/abs/2012.04524.

Attachment

Video Recording