Part of Advances in Neural Information Processing Systems 11 (NIPS 1998)
Yoshiyuki Kabashima, David Saad
We show the similarity between belief propagation and TAP, for decoding corrupted messages encoded by Sourlas's method. The latter is a special case of the Gallager error-correcting code, where the code word comprises products of J{ bits selected randomly from the original message. We examine the efficacy of solutions obtained by the two methods for various values of J{ and show that solutions for J{ 2': 3 may be sensitive to the choice of initial conditions in the case of unbiased patterns. Good approximations are obtained generally for J{ = 2 and for biased patterns in the case of J{ 2': 3, especially when Nishimori's temperature is being used.