mlsanityData to 7 Oct 2026

Approximate message passing from random initialization with applications to mathbbZ2 synchronization

arXiv 2302.03682 ↗First posted 7 Feb 2023math.ST cs.IT eess.SPcited by 9

Not on the map. Why?

Abstract (arXiv)

This paper is concerned with the problem of reconstructing an unknown rank-one matrix with prior structural information from noisy observations. While computing the Bayes-optimal estimator seems intractable in general due to its nonconvex nature, Approximate Message Passing (AMP) emerges as an efficient first-order method to approximate the Bayes-optimal estimator. However, the theoretical underpinnings of AMP remain largely unavailable when it starts from random initialization, a scheme of critical practical utility. Focusing on a prototypical model called mathbbZ2 synchronization, we characterize the finite-sample dynamics of AMP from random initialization, uncovering its rapid global convergence. Our theory provides the first non-asymptotic characterization of AMP in this model without requiring either an informative initialization (e.g., spectral initialization) or sample splitting.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 29 of its 69 references that are in the map. First posted on arXiv 7 Feb 2023.

Builds on

29 of 69 references.

References · 29

  1. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  2. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  3. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 111
  4. 2018A modern maximum-likelihood theory for high-dimensional logistic regressioncited by 79
  5. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  6. 2015Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guaranteescited by 68
  7. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
  8. 2019Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimizationcited by 58
  9. 2021A unifying tutorial on Approximate Message Passingcited by 49
  10. 2016Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statisticscited by 45
  11. 2017Estimation of Low-Rank Matrices via Approximate Message Passingcited by 41
  12. 2020The Lasso with general Gaussian designs with applications to hypothesis testingcited by 40
17 more
  1. 2017Near-optimal bounds for phase synchronizationcited by 32
  2. 2020Approximate Message Passing algorithms for rotationally invariant matricescited by 31
  3. 2019Computational Hardness of Certifying Bounds on Constrained PCA Problemscited by 30
  4. 2021Inference for Heteroskedastic PCA with Missing Datacited by 21
  5. 2016Finite Sample Analysis of Approximate Message Passing Algorithmscited by 20
  6. 2016Message-passing algorithms for synchronization problems over compact groupscited by 18
  7. 2021Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initializationcited by 18
  8. 2022A Non-Asymptotic Framework for Approximate Message Passing in Spiked Modelscited by 18
  9. 2016The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differencescited by 15
  10. 2017The Likelihood Ratio Test in High-Dimensional Logistic Regression Is Asymptotically a Rescaled Chi-Squarecited by 15
  11. 2021Local convexity of the TAP free energy and AMP convergence for Z2-synchronizationcited by 15
  12. 2019Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passingcited by 14
  13. 2021PCA Initialization for Approximate Message Passing in Rotationally Invariant Modelscited by 14
  14. 2020Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noisecited by 9
  15. 2022Precise Asymptotics for Spectral Methods in Mixed Generalized Linear Modelscited by 7
  16. 2021SDP Achieves Exact Minimax Optimality in Phase Synchronizationcited by 3
  17. 2022Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Modelscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 4; 2025: 3; 2026: 1.

9 papers.

  1. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 17
  2. 2023Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCAcited by 7
  3. 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 6
  4. 2024Unifying AMP Algorithms for Rotationally-Invariant Modelscited by 3
  5. 2024Sharp Analysis of Power Iteration for Tensor PCAcited by 2
  6. 2025Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Couplingcited by 2
  7. 2024A Convergence Analysis of Approximate Message Passing with Non-Separable Functions and Applications to Multi-Class Classificationcited by 1
  8. 2025Learning with Restricted Boltzmann Machines: Asymptotics of AMP and GD in High Dimensionscited by 0
  9. 2026Easy, robust approximate message passing for planted spike modelscited by 0