Variational message passing without initialization using a free energy constraint

In iterative algorithms with graphical models, it is common to initialize messages. But this approach is not suitable in certain applications. In this paper, it is conjectured that if some messages are confined to a ball around their initialized values, then initialization can be avoided. Towards this goal, for networks specified with a bipartite graph, a variant of the sum-product algorithm is derived by adding an inequality constraint on the variable free energy in the underlying Bethe optimization problem. In the binary case, this leads to an upper bound that restricts the ℓ₁ norm of the extrinsic message (vector) to a ball around its (otherwise) initial value. Results are reported for binary LDPC decoders through simulations which confirm that initialization between decoding attempts can be eliminated and show that the algorithm tends to outperform the standard sum-product. A few more observations and comments on this approach, relation with other variational methods, and applications to analog processing and inference over distributed networks are outlined in the end.