  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\big(\frac{\log n}{\log\log n}\big)$ (with $n$ the problem dimension). To
address this inadequacy, this paper develops a non-asymptotic framework for
understanding AMP in spiked matrix estimation. Built upon 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 $\mathbb{Z}_2$ synchronization, we predict the behavior of
spectrally initialized AMP for up to $O\big(\frac{n}{\mathrm{poly}\log n}\big)$
iterations, showing that the algorithm succeeds without the need of a
subsequent refinement stage (as conjectured recently by
\citet{celentano2021local}); (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.
