Efficient Posterior Sampling for $\mathbb Z_2$ Synchronization
Consider the $\mathbb Z_2$ synchronization problem \[ \boldsymbol{Y} = \fracλ{\sqrt n} θθ^{\top} + \boldsymbol{Z}, \] where $θ$ is uniform on $\{-1,1\}^n$ and $\boldsymbol{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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.08199
curl -X POST /api/v1/records/arxiv/2610.08199/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.08199/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'