Markov chain Monte Carlo algorithms have long been observed to obtain near-optimal performance in various Bayesian inference settings. However, developing a supporting theory that makes these studies rigorous has proved challenging. In this paper, we study the classical spiked Wigner inference problem, where one aims to recover a planted Boolean spike from a noisy matrix measurement. We relate the recovery performance of Glauber dynamics on the annealed posterior to the performance of Approximate Message Passing (AMP), which is known to achieve Bayes-optimal performance. Our main results rely on the analysis of an auxiliary Markov chain called restricted Gaussian dynamics (RGD). Concretely, we establish the following results: 1. RGD can be reduced to an effective one-dimensional recursion which mirrors the evolution of the AMP iterates. 2. From a warm start, RGD rapidly converges to a fixed point in correlation space, which recovers Bayes-optimal performance when run on the posterior. 3. Conditioned on widely believed mixing results for the SK model, we recover the phase transition for non-trivial inference.

翻译：长期以来，马尔可夫链蒙特卡洛算法在各种贝叶斯推断场景中被观察到能达到接近最优的性能。然而，建立支撑这些研究的严谨理论一直颇具挑战。本文研究了经典的尖峰维格纳推断问题，其目标是从含噪矩阵测量中恢复一个植入的布尔尖峰信号。我们将退火后验分布上的Glauber动力学恢复性能与近似消息传递算法的性能联系起来，后者已知能达到贝叶斯最优性能。我们的主要结果依赖于对一个称为受限高斯动力学的辅助马尔可夫链的分析。具体而言，我们建立了以下结论：1. 受限高斯动力学可简化为一个有效的一维递归过程，该过程与近似消息传递迭代的演化过程相互对应；2. 从热启动状态出发，受限高斯动力学能在相关空间中快速收敛至不动点，当在后验分布上运行时该不动点可恢复贝叶斯最优性能；3. 基于学界广泛认可的SK模型混合性假设，我们恢复了非平凡推断的相变阈值。