Phase retrieval in high dimensions: Statistical and computational phase transitions

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_{\mu }=|{\sum }_{i=1}^n{\Phi }_{\mu i}{X}_i^{\star }/\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 a 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.

arXiv comment12 pages (main text and references), 26 pages of supplementary material. v2 matches the final version accepted at NeurIPS 2021

References in corpus (8)

• Message Passing Algorithms for Compressed Sensing
• Statistical physics of inference: Thresholds and algorithms
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Large Deviations of Extreme Eigenvalues of Random Matrices
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval
• Exact asymptotics for phase retrieval and compressed sensing with random generative priors
• Spectral Method for Phase Retrieval: an Expectation Propagation Perspective

Cited by in corpus (4)

• Solving the fully-connected spherical $p$-spin model with the cavity method: equivalence with the replica results
• The replica-symmetric free energy for Ising spin glasses with orthogonally invariant couplings
• Macroscopic Analysis of Vector Approximate Message Passing in a Model Mismatch Setting
• Construction of optimal spectral methods in phase retrieval