Efficient Posterior Sampling for ℤ2 Synchronization
Abstract
Consider the ℤ2 synchronization problem Y = λ/√n θθ⊤ + Z, where θ is uniform on {−1,1}n and Z is an independent Gaussian Wigner matrix with off-diagonal variance one. We give a polynomial-time posterior sampling algorithm for every fixed λ>1, for which the conditional output law converges to the posterior in total variation, in expectation over the observation. The construction combines sequential TAP proposals with an independence Metropolis correction. The key is to control signed overlaps after logarithmic pinning and conditional TAP approximations along a random revealing path, which give an efficiently evaluable proposal with a polynomial density-ratio bound outside a set of vanishing posterior mass. To the best of our knowledge, this is the first polynomial-time posterior sampler for ℤ2 synchronization with a total-variation guarantee throughout the supercritical regime. For comparison, the diffusion-based sampler of \cite{montanari2023posterior} gives normalized Wasserstein guarantees at sufficiently large fixed signal-to-noise ratio.
Related
- Power-posterior implicit sampling for efficient Bayesian experimental design: Application to contaminant source identification in groundwater flow
- Synchronization in Probability of Reaction–Diffusion Neural Networks Under Stochastic Sampling Governed by Infinite Discrete Distributions
- Accelerating posterior sampling in Bayesian inverse problems with diffusion models: an online-offline perspective
- Learning to Replace MCMC in Split-Gibbs Diffusion Posterior Sampling via Deep Unfolding
- Flow Annealing Posterior Sampling for Function-Space Regression and Inverse Problems
BibTeX
@misc{li2026efficient,
title = {{Efficient Posterior Sampling for $\mathbb Z_2$ Synchronization}},
author = {Zhangsong Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08199},
eprint = {2610.08199},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08199},
}
RIS
TY - UNPB
TI - Efficient Posterior Sampling for ℤ_2 Synchronization
AU - Zhangsong Li
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08199
UR - https://arxiv.org/abs/2610.08199
AB - Consider the ℤ_2 synchronization problem Y = λ/√n θθ^⊤ + Z, where θ is uniform on {−1,1}^n and Z is an independent Gaussian Wigner matrix with off-diagonal variance one. We give a polynomial-time posterior sampling algorithm for every fixed λ>1, for which the conditional output law converges to the posterior in total variation, in expectation over the observation. The construction combines sequential TAP proposals with an independence Metropolis correction. The key is to control signed overlaps after logarithmic pinning and conditional TAP approximations along a random revealing path, which give an efficiently evaluable proposal with a polynomial density-ratio bound outside a set of vanishing posterior mass. To the best of our knowledge, this is the first polynomial-time posterior sampler for ℤ_2 synchronization with a total-variation guarantee throughout the supercritical regime. For comparison, the diffusion-based sampler of \cite{montanari2023posterior} gives normalized Wasserstein guarantees at sufficiently large fixed signal-to-noise ratio.
ER -