Phase retrieval in high dimensions: Statistical and computational phase transitions

We consider the phase retrieval problem of reconstructing a n -dimensional real or complex signal X ⋆ from m (possibly noisy) observations Y μ = | ∑ n i = 1 Φ μ i X ⋆ i / √ n | , for a large class of correlated real and complex random sensing matrices Φ , in a high-dimensional setting where m , n → ∞ 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 Φ . 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 statistical-to-algorithmic gap depending, again, on the spectral properties of Φ . Our work provides an extensive classification of the statistical and algorithmic thresholds in high-dimensional phase retrieval for a broad class of random matrices.