B0772
Title: A non-asymptotic framework for approximate message passing
Authors: Yuting Wei - University of Pennsylvania (United States) [presenting]
Abstract: Approximate message passing (AMP) emerges as an effective iterative paradigm for solving high-dimensional statistical problems. However, prior AMP theory --- which focused mostly on high-dimensional asymptotics --- fell short of predicting the AMP dynamics when the number of iterations surpasses $o(\log n/\log\log n)$ (with $n$ the problem dimension). To address this inadequacy, a non-asymptotic framework is developed for understanding AMP in spiked matrix estimation. Built upon a new decomposition of AMP updates and controllable residual terms, we lay out an analysis recipe to characterize the finite-sample behavior of AMP in the presence of an independent initialization, which is further generalized to allow for spectral initialization. As two concrete consequences of the proposed analysis recipe: (i) when solving $Z_2$ synchronization, we predict the behavior of spectrally initialized AMP for up to $O(n/\mathrm{poly}\log n)$ iterations, showing that the algorithm succeeds without the need of a subsequent refinement stage (as conjectured recently); (ii) we characterize the non-asymptotic behavior of AMP in sparse PCA (in the spiked Wigner model) for a broad range of signal-to-noise ratio.
