Efficient ℤ_2 synchronization on ℤ^d under symmetry-preserving side information
share
We consider ℤ_2-synchronization on the Euclidean lattice. Every vertex of ℤ^d is assigned an independent symmetric random sign θ_u, and for every edge (u,v) of the lattice, one observes the product θ_uθ_v flipped independently with probability p. The task is to reconstruct products θ_uθ_v for pairs of vertices u and v which are arbitrarily far apart. Abbé, Massoulié, Montanari, Sly and Srivastava (2018) showed that synchronization is possible if and only if p is below a critical threshold p̃_c(d), and efficiently so for p small enough. We augment this synchronization setting with a model of side information preserving the sign symmetry of θ, and propose an efficient algorithm which synchronizes a randomly chosen pair of far away vertices on average, up to a differently defined critical threshold p_c(d). We conjecture that p_c(d)=p̃_c(d) for all d ≥ 2. Our strategy is to renormalize the synchronization model in order to reduce the effective noise parameter, and then apply a variant of the multiscale algorithm of AMMSS. The success of the renormalization procedure is conditional on a plausible but unproved assumption about the regularity of the free energy of an Ising spin glass model on ℤ^d.
READ FULL TEXT