Markov Chains Approximate Message Passing
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915650627174400 |
|---|---|
| author | Rajaraman, Amit Wu, David X. |
| author_facet | Rajaraman, Amit Wu, David X. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_02384 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Markov Chains Approximate Message Passing Rajaraman, Amit Wu, David X. Data Structures and Algorithms Probability 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. |
| title | Markov Chains Approximate Message Passing |
| topic | Data Structures and Algorithms Probability |
| url | https://arxiv.org/abs/2512.02384 |