Statistical inference with correlated disorder: the planted spin glass

Inference problems defined on random graphs can be studied by using statistical physics methods of disordered systems. In particular, these methods allows us to find the phase transitions characterizing the feasibility of said problems. A largely unexplored setting of Bayesian inference is that of structured signal, as most theoretical work studies models where the signal is made up of i.i.d. components. We study the planted spin glass model in the case of structured signal using the cavity method and compare the results with those obtained by performing inference via Belief Propagation on generated instances of the problem. We present the results in the form of a phase diagram, in which we can distinguish two phases: one in which inference is impossible and one where inference is easy.