Proc Natl Acad Sci U S A. 2023 Aug;120(31):e2302930120. doi: 10.1073/pnas.2302930120. Epub 2023 Jul 25.
ABSTRACT
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 is intractable in general due to the requirement of computing high-dimensional integrations/summations, 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 [Formula: see text] synchronization, we characterize the finite-sample dynamics of AMP from random initialization, uncovering its rapid global convergence. Our theory-which is nonasymptotic in nature-in this model unveils the non-necessity of a careful initialization for the success of AMP.
PMID:37490538 | DOI:10.1073/pnas.2302930120
