 |
Center for Nonlinear Studies |
Abstract: BP algorithms are at the intersection between various fields such as statistical physics or information sciences. A typical issue is the relationship between the generally suboptimal BP solutions and the optimal solutions. The talk will address this question in the framework of sparse graph error-correcting codes such as Low-Density Parity-Check (LDPC) for which the optimal algorithm is the MAP algorithm which minimizes the probability of error. I will first revisit the material presented at LANL seminar (12/11/06). In the limit of large systems, BP and MAP decoding are characterized by a common object that is similar to the van der Waals equation of state. This object is derived from the BP algorithm (applied to the code or/and to its dual) and encodes the MAP performance via a Maxwell-type construction.The `Maxwell' decoder provides an operational interpretation for the erasure channel. Both the decoder and its analysis are the translation of the Maxwell construction from thermodynamics to probabilistic coding: this shows us how to predict the asymptotic MAP performance from the BP performance. I will then briefly show first steps on a way to derive BP-type algorithms from the MAP algorithm. With this aim I will discuss the application of Weitz's algorithm to the case of generalized binary random Markov fields such as LDPC graphs. Weitz's algorithm has been recently derived in theoretical computer science and gives the first polynomial approximation for counting independent sets up to the `tree threshold.' By constructing and pruning a specific tree, i.e., by adapting Weitz's derivation of the MAP algorithm, we derive iterative algorithms that interpolate continuously between MAP and BP for finite systems.