Region-based approximation to solve inference in loopy factor graphs : decoding LDPC codes by the Generalized Belief Propagation.

Summary In this thesis, we study the problem of Bayesian inference in factor graphs, in particular LDPC codes, which are almost solved by message-passing algorithms. In particular, we carry out an in-depth study of Belief Propagation (BP), whose suboptimality is raised in the case where the factor graph has loops. Starting from the equivalence between BP and the Bethe approximation in statistical physics which is generalized to the region-based approximation, we detail the Generalized Belief Propagation (GBP), a message-passing algorithm between clusters of the factor graph. We show through experiments that GBP outperforms BP in cases where clustering is performed according to the harmful topological structures that prevent BP from decoding well, namely trapping sets. Beyond the study of the performance in terms of error rate, we confront the two algorithms with respect to their dynamics in the face of non-trivial error events, in particular when they exhibit chaotic behavior. Through classical and original estimators, we show that the GBP algorithm can dominate the BP algorithm.