论文标题
一个非反应框架，用于在峰值模型中传递的近似消息
A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models
论文作者
论文摘要
近似消息传递（AMP）是解决高维统计问题的有效迭代范式。然而，当迭代次数超过$ o \ big（\ frac {\ log n} {\ log log \ log \ log n} \ big）时，先前主要集中在高维渐近造的AMP理论（主要集中在高维渐近学上）都无法预测AMP动力学。为了解决这一不足，本文开发了一个非反应框架，用于理解峰值矩阵估计中的AMP。我们建立在AMP更新和可控剩余项的新分解的基础上，我们布置了一个分析配方，以表征在存在独立初始化的情况下AMP的有限样本行为，该过程被进一步概括以允许光谱初始化。作为提出的分析配方的两个具体后果：（i）求解$ \ mathbb {z} _2 $同步时，我们预测了频谱初始化AMP的行为，最多可$ o \ big（\ frac {n} {n} {\ mathrm {\ mathrm {poly} {poly} \ log n} \ big），而没有一个$ big）$ big）改进阶段（如\ citet {celentano2021local}最近猜想）; （ii）我们表征了稀疏PCA中AMP的非反应性行为（在尖刺的Wigner模型中），以广泛的信噪比。
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.
