Sub-tree Based Upper and Lower Bounds on the Partition Function

A probabilistic inference problem is concerned with computing the partition function and the marginals of a global probability distribution. We investigate upper and lower bounds on the partition function of a given inference problem. Our bounds depend on the partition function of any sub-junction tree of a given junction graph representing the inference problem. In a theorem we compare such bounds using the entropies of the sub-junction trees. Finally we propose a greedy algorithm that computes low-complexity bounds on the partition function. Simulation results on two-dimensional grids are reported