Bruno Loureiro, Florent Krzakala, Lenka Zdeborová, Antoine Maillard
We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.
Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.
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 ΦµiX 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 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.
The same record, over MCP at https://syntology.ai/mcp:
get_harvested_code_for_paper("2006.05228")
get_code_for_paper("2006.05228")
have("2006.05228")
The run record, dated, one paper per request, free:
curl https://syntology.ai/api/ran/2006.05228.json
A badge for a README (the split and the date, never a ratio):
[](https://syntology.ai/paper/2006.05228)
Connect an agent — have() is free.