On entropy decomposition and new bounds on the partition function

Recent work has related the belief propagation algorithm for probabilistic inference problem to some approximations to the free energy function in statistical physics. In this paper we investigate some properties of one such approximation, called the Bethe-Kikuchi approximation. We also derive low-complexity upper and lower bounds on the partition function, i.e. the global normalization constant, for a given inference problem