|
Abstract:
|
Approximate message passing (AMP) serves as an effective and computationally efficient paradigm for solving high-dimensional statistical problems with structures, such as low-rank matrix estimation and sparse regression. However, prior theory mainly focused on its infinite sample limit for a fixed number of iterations, which falls short in predicting the AMP dynamics when the number of iterations surpasses $o(\log n/\log\log n)$. Based on a new decomposition of the AMP updates, we develop characterizations of the AMP trajectory up to a polynomial number of iterations, which is stronger than results obtained by standard state evolution analyses of AMP. As concrete consequences, our results reveal that: (i) AMP manages to solve the Z2 synchronization problem without the need for a further local refinement stage, as conjectured in earlier work; (ii) AMP is provably effective to recovery sparse spikes in matrix estimation for a broad range of signal strength.
|
