Approximate message passing from random initialization with applications to <i>Z</i><sub>2</sub> synchronization.
basic_science · Level V
Where this comes from
- Record sourced from PubMed, PMID 37490538.
- Also identified by DOI 10.1073/pnas.2302930120 and PMC identifier 10401009.
- No licence information is recorded for this record.
- Because redistribution is not established, this page shows the abstract only. Follow the links below for the full text.
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.