text: It has recently been observed that the permanent of a nonnegative square matrix, i.e., of a square matrix containing only nonnegative real entries, can very well be approximated by solving a certain Bethe free energy function minimization problem with the help of the sum-product algorithm. We call the resulting approximation of the permanent the Bethe permanent. In this paper, we give reasons why this approach to approximating the permanent works well. Namely, we show that the Bethe free energy function is convex and that the sum-product algorithm finds its minimum efficiently. We then discuss the fact that the permanent is lower bounded by the Bethe permanent, and we comment on potential upper bounds on the permanent based on the Bethe permanent. We also present a combinatorial characterization of the Bethe permanent in terms of permanents of so-called lifted versions of the matrix under consideration. Moreover, we comment on possibilities to modify the Bethe permanent so that it approximates the permanent even better, and we conclude the paper with some observations and conjectures about permanent-based pseudocodewords and permanent-based kernels.
  @cite_24: We construct a deterministic fully polynomial time approximationscheme (FPTAS) for computing the total number of matchings in abounded degree graph. Additionally, for an arbitrary graph, weconstruct a deterministic algorithm for computing approximately thenumber of matchings within running time exp(O(√n log2n)),where n is the number of vertices. Our approach is based on the correlation decay technique originating in statistical physics. Previously thisapproach was successfully used for approximately counting thenumber of independent sets and colorings in some classes of graphs [1, 24, 6].Thus we add another problem to the small, but growing, class of P-complete problems for whichthere is now a deterministic FPTAS.
  @cite_47: In this paper we rigorously prove the validity of the cavity method for the problem of counting the number of matchings in graphs with large girth. Cavity method is an important heuristic developed by statistical physicists that has lead to the development of faster distributed algorithms for problems in various combinatorial optimization problems. The validity of the approach has been supported mostly by numerical simulations. In this paper we prove the validity of cavity method for the problem of counting matchings using rigorous techniques. We hope that these rigorous approaches will finally help us establish the validity of the cavity method in general.
  @cite_30: Data association is the problem of determining the correspondence between targets and measurements. In this paper, we present a graphical model approach to data association and apply an approximate inference method, loopy belief propagation, to obtain the marginal association weights (e.g., for JPDA). In general, loopy belief propagation is not guaranteed to converge, and when convergence is obtained the result is not guaranteed to be the correct answer. We investigate the convergence properties of a loopy belief propagation algorithm for data association, proving that it converges, and demonstrating its practical efficiency. A greatly simplified implementation is provided, which exploits the structure in the factors to reduce the cost per iteration from O(m2n2) to O(mn) operations where n is the number of targets and m is the number of measurements. Combined with the previously published results on the accuracy of the approximation, the convergence results reveal loopy belief propagation as a highly attractive method for approximate calculation of joint association weights.
  @cite_89: We consider the problem of computing the permanent of a 0,1n by n matrix. For a class of matrices corresponding to constant degree expanders we construct a deterministic polynomial time approximation algorithm to within a multiplicative factor ([email protected])^n, for arbitrary @e>0. This is an improvement over the best known approximation factor e^n obtained in Linial, Samorodnitsky and Wigderson (2000) [9], though the latter result was established for arbitrary non-negative matrices. Our results use a recently developed deterministic approximation algorithm for counting partial matchings of a graph (Bayati, Gamarnik, Katz, Nair and Tet ali (2007) [2]) and Jerrum-Vazirani method (Jerrum and Vazirani (1996) [8]) of approximating permanent by near perfect matchings.
summary: Because computing the permanent is related to counting perfect matchings, the paper by Bayati and Nair @cite_47 on counting matchings in graphs with the help of the SPA is very relevant. Note that their setup is such that the perfect matching case can be seen as a limiting case (namely the zero-temperature limit) of the matching setup. However, for the perfect matching case (a case for which the authors of @cite_47 make no claims) the convergence proof of the SPA in @cite_47 is incomplete. Moreover, their matchings are weighted only inasmuch as the weight of a matching depends on the size of the matching. Consequently, because all perfect matchings have the same size, they all are assigned the same weight. (See also the related paper by Bayati, Gamarnik, Katz, Nair, and Tet ali @cite_24 , and an extension to counting perfect matchings in certain types of graph by Gamarnik and Katz @cite_89 .) For an SPA convergence analysis of a slightly generalized weighted matching setup, the interested reader is referred to a recent paper by Williams and Lau @cite_30 .