Belief propagation <i>vs.</i> TAP for decoding corrupted messages

Abstract

PACS. 89.70+c { Information science. PACS. 89.90+n { Other areas of general interest to physicists. PACS. 02.50−r { Probability theory, stochastic processes, and statistics. Abstract. { We employ two dierent methods, based on belief propagation and TAP, for decoding corrupted messages encoded by employing Sourlas’s method, where the code word comprises products of K bits selected randomly from the original message. We show that the equations obtained by the two approaches are similar and provide the same solution as the one obtained by the replica approach in some cases (K = 2). However, we also show that for K 3 and unbiased messages the iterative solution is sensitive to the initial conditions and is likely to provide erroneous solutions; and that it is generally benecial to use Nishimori’s temperature, especially in the case of biased messages. Belief networks [1], also termed Bayesian networks, and influence diagrams are diagram-matic representations of joint probability distributions over a set of variables. The set of variables is usually represented by the vertices of a graph, while arcs between vertices rep-resent probabilistic dependences between variables. Belief propagation provides a convenient