Estimating the Capacity of the 2-D Hard Square Constraint Using Generalized Belief Propagation

A binary m x n array is said to satisfy the two-dimensional (2-D) hard square constraint if no row or column of the array contains ones in consecutive positions. Let N(m,n) denote the number of such arrays. The capacity of the hard square constraint is the limit, as m, n go to infinity, of the quantity (1/mn)*(log N(m,n)). Determining this capacity exactly is a long-standing open problem; its numerical value is known up to ten decimal places. Recently, Sabato and Molkaraie demonstrated via simulations that the capacity of the hard square constraint can be approximated extremely well using the generalized belief propagation (GBP) algorithm. They did not, however, give an analytical explanation for their observations. In this talk, we outline an approach for analyzing GBP with a view to giving guarantees on the accuracy of the GBP estimate of the capacity of the hard square constraint. More generally, our approach provides a means of analyzing the performance of GBP in estimating the partition function of any binary pairwise model on 2-D grids. Our main result at this point is that the GBP estimate is always a lower bound on the true partition function of any such model on a 2-D grid of size 3xn, 4x4, or 5x5 (this is joint work with Eric Chan, Sidharth Jaggi and Pascal Vontobel at the Chinese University of Hong Kong).