Approximate Message Passing with Random Initialization for Phase Retrieval

• URL: http://arxiv.org/abs/2608.01654v1
• Date: Mon, 03 Aug 2026 03:44:13 GMT
• Title: Approximate Message Passing with Random Initialization for Phase Retrieval
• Abstract summary: We prove a Gaussian decomposition of the AMP trajectory and control its error over the horizons required for recovery.<n>The majority of our analysis applies more generally to generalized AMP for single-index models.
• Score: 7.7572821781975
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze approximate message passing (AMP) with an independent Gaussian initialization for noiseless phase retrieval in the proportional asymptotic regime. A random initialization has overlap of order $d^{-1/2}$ with the signal, and AMP requires a growing number of iterations to attain non-vanishing overlap. Thus, its precise behavior cannot be characterized by classical fixed-time state evolution. We prove a Gaussian decomposition of the AMP trajectory and control its error over the horizons required for recovery. The resulting analysis shows that random initialization attains the weak-recovery threshold $δ_{\rm weak}=1/2$. For $δ\in(δ_{\rm weak},δ_{\rm str})$, where $δ_{\rm str}\approx1.13$, the signal strength follows state evolution and approaches its stable finite fixed point uniformly for \(n^{1/3}/\operatorname{polylog}(n)\) iterations. For $δ>δ_{\rm str}$, AMP reaches any prescribed fixed recovery accuracy within $O_{δ,\varepsilon}(\log n)$ iterations. The majority of our analysis applies more generally to generalized AMP for single-index models.

Related papers

• On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensing [18.637825309463125]
  Binary Iterative Hard Thresholding (BIHT) is a simple, yet effective, greedy method for recovering a sparse vector from one-bit sign measurements.<n>A convergence analysis of this algorithm was left open in the introductory work of [Jac+11] and has remained unresolved for over a decade.<n>This paper resolves that gap and characterizes when per-iteration normalization is algorithmically necessary.
  arXiv  Detail & Related papers  (2026-07-17T00:44:33Z)
• How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysis [53.063298916923976]
  We study the feedback in a Gaussian single-index model with $r*(x) = *(langle *, xrangle)$ and $x sim N(0, I_d)$.<n>We analyze a two-stage neural reward model that first learns the hidden direction $*$ from reward-weighted samples and then fits the readout layer by weighted ridge regression.
  arXiv  Detail & Related papers  (2026-05-23T22:00:38Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Sparse Max-Affine Regression [8.338559499737135]
  This paper presents Sparse Gradient as a solution for variable selection in convex piecewise linear regression.<n>A non-asymptotic local convergence analysis is provided for Sp-GD under sub-Gaussian noise.<n>A new transformation named Real Maslov Dequantization (RMD) is proposed to transform sparse generalizeds into sparse max-affine models.
  arXiv  Detail & Related papers  (2024-11-04T16:19:09Z)
• On Leaky-Integrate-and Fire as Spike-Train-Quantization Operator on Dirac-Superimposed Continuous-Time Signals [0.5439020425819]
  Leaky-integrate-and-fire (LIF) is studied as a non-linear operator that maps an integrable signal $f$ to a sequence $eta_f$ of discrete events, the spikes. We prove the quantization formula $|eta_f - f|_A, alpha$ with leaky parameter $alpha$ under the general condition of local integrability.
  arXiv  Detail & Related papers  (2024-02-10T17:07:19Z)
• Approximate message passing from random initialization with applications to $\mathbb{Z}_{2}$ synchronization [25.511475484340156]
  This paper is concerned with the problem of reconstructing an unknown rank-one matrix with prior structural information from observations. We provide the first non-asymotic characterization of Approximate Message Passing (AMP) in this model.
  arXiv  Detail & Related papers  (2023-02-07T18:58:08Z)
• A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models [24.786030482013437]
  Approximate message passing (AMP) emerges as an effective iterative paradigm for solving high-dimensional statistical problems. Prior AMP theory fell short of predicting the AMP dynamics when the number of iterations surpasses $obig(fraclog nloglog nbig)$. This paper develops a non-asymptotic framework for understanding AMP in spiked matrix estimation.
  arXiv  Detail & Related papers  (2022-08-05T17:59:06Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
  We show that the rate estimate $widetildemathcalO(depsilon-1)$ improves the previously known rates in both of these metrics. In particular, for convex and firstorder smooth potentials, we show that LMC algorithm achieves the rate estimate $widetildemathcalO(depsilon-1)$ which improves the previously known rates in both of these metrics.
  arXiv  Detail & Related papers  (2020-07-22T18:18:28Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.