SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2006.05228 · NeurIPS · 2020

Phase retrieval in high dimensions: Statistical and computational phase transitions

Bruno Loureiro, Florent Krzakala, Lenka Zdeborová, Antoine Maillard

arXiv · PDF · Open in the Atlas

Code that ran

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.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

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.

For agents

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):

[![Syntology run record](https://syntology.ai/api/ran/2006.05228.svg)](https://syntology.ai/paper/2006.05228)

Connect an agent — have() is free.