2023/02/07 by Gen Li, Wei Fan, Li, Gen +3 · 3 citations
Computer Science · Engineering · #Blind Source Separation Techniques #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Signal Processing (eess.SP) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2302.03682
openalex publication_date 2023/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ℤ2 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.