Papers › Phase retrieval in high dimensions: Statistical and computational phase transitions
Phase retrieval in high dimensions: Statistical and computational phase transitions
Antoine Maillard, Bruno Loureiro, Florent Krzakala, Lenka Zdeborová
We consider the phase retrieval problem of reconstructing a n-dimensional real or complex signal 𝐗^⋆ from m (possibly noisy) observations Y_μ = | ∑ᵢ₌₁ⁿ Φ_(μi) X^⋆ᵢ/√(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 a 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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections