  We propose an original particle-based implementation of the Loopy Belief
Propagation (LPB) algorithm for pairwise Markov Random Fields (MRF) on a
continuous state space. The algorithm constructs adaptively efficient proposal
distributions approximating the local beliefs at each note of the MRF. This is
achieved by considering proposal distributions in the exponential family whose
parameters are updated iterately in an Expectation Propagation (EP) framework.
The proposed particle scheme provides consistent estimation of the LBP
marginals as the number of particles increases. We demonstrate that it provides
more accurate results than the Particle Belief Propagation (PBP) algorithm of
Ihler and McAllester (2009) at a fraction of the computational cost and is
additionally more robust empirically. The computational complexity of our
algorithm at each iteration is quadratic in the number of particles. We also
propose an accelerated implementation with sub-quadratic computational
complexity which still provides consistent estimates of the loopy BP marginal
distributions and performs almost as well as the original procedure.
