It was recently conjectured that the permanent of a @math -lifting @math of a matrix @math of degree @math is less than or equal to the @math th power of the permanent perm @math , i.e., perm @math and, consequently, that the degree- @math Bethe permanent @math of a matrix @math is less than or equal to the permanent perm @math of @math , i.e., perm @math . In this paper, we prove these related conjectures and show in addition a few properties of the permanent of block matrices that are lifts of a matrix. As a corollary, we obtain an alternative proof of the inequality perm @math on the Bethe permanent of the base matrix @math that uses only the combinatorial definition of the Bethe permanent.
The literature on permanents and on adjacent areas (of counting perfect matchings, counting 0-1 matrices with specified row and column sums, etc.) is vast. Apart from the previously mentioned papers, the most relevant papers to our work are the one by Chertkov & Yedidia @cite_12 that studies the so-called fractional free energy functionals and resulting lower and upper bounds on the permanent of a non-negative matrix, the papers @cite_7 (on counting perfect matchings in random graph covers), @cite_1 (on counting matchings in graphs with the help of the sum-product algorithm Computing the permanent is related to counting perfect matchings. ), and @cite_18 @cite_32 @cite_21 (on max-product min-sum algorithms based approaches to the maximum weight perfect matching problem). Relevant is also the line of work on approximating the permanent of a non-negative matrix using Markov-chain-Monte-Carlo-based methods @cite_6 , polynomial-time randomized approximation schemes @cite_0 , and Bethe-approximation based methods or sum-product-algorithm (SPA) based method @cite_18 @cite_22 . See @cite_27 for a more detailed account of these and other related papers.
@cite_18 @cite_22 @cite_7 @cite_21 @cite_1 @cite_32 @cite_6 @cite_0 @cite_27 @cite_12
1628027163 2167490374 1986705527 2044105411 2161611531 2761017552 1520400698
This work describes a method of approximating matrix per- manents efficiently using belief propagation. We formulate aprobability distribution whose partition function is exactly the permanent, then use Bethe free energy to approximate this partition function. After deriving some speedups to standard belief propagation, the resulting algorithm requires (n 2 ) time per iteration. Finally, we demonstrate the advantages of using this approximation. Let G be a fixed connected multigraph with no loops. A random n-lift of G is obtained by replacing each vertex of G by a set of n vertices (where these sets are pairwise disjoint) and replacing each edge by a randomly chosen perfect matching between the n-sets corresponding to the endpoints of the edge. Let XG be the number of perfect matchings in a random lift of G. We study the distribution of XG in the limit as n tends to infinity, using the small subgraph conditioning method. We present several results including an asymptotic formula for the expectation of XG when G is d-regular, d ≥ 3. The interaction of perfect matchings with short cycles in random lifts of regular multigraphs is also analysed. Partial calculations are performed for the second moment of XG, with full details given for two example multigraphs, including the complete graph K4. To assist in our calculations we provide a theorem for estimating a summation over multiple dimensions using Laplace's method. This result is phrased as a summation over lattice points, and may prove useful in future applications. 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. Let G=(U, V, E) be a bipartite graph with |U|=|V|=n. The factor size of G, f, is the maximum number of edge disjoint perfect matchings in G. We characterize the complexity of counting the number of perfect matchings in classes of graphs parameterized by factor size. We describe the simple algorithm, which is an approximation algorithm for the permanent that is a natural simplification of the algorithm suggested by Broder (1986) and analyzed by Jerrum and Sinclair (1988a, b). Compared to the algorithm by Jerrum and Sinclair (1988a, b), the simple algorithm achieves a polynomial speed up in the running time to compute the permanent. A combinatorial lemma is used to prove that the simple algorithm runs in time nO(n f). Thus: (1) for all constants α>0, the simple algorithm runs in polynomial time for graphs with factor size at least αn; (2) for some constant c, the simple algorithm is the fastest known approximation for graphs with factor size at least c log n. (Compare with the approximation algorithms described in Karmarkar (1988).) We prove the following complementary hardness results. For functions f such that 3⩽f(n)⩽n−3, the exact counting problem for f(n)-regular bipartite graphs is #P-complete. For and e>0, for any function f such that 3⩽f(n)⩽n1−e, approximate counting for f(n)-regular bipartite graphs is as hard as approximate counting for all bipartite graphs. An announcement of these results appears in Dagum (1988). We present a polynomial-time randomized algorithm for estimating the permanent of an arbitrary n × n matrix with nonnegative entries. This algorithm---technically a "fully-polynomial randomized approximation scheme"---computes an approximation that is, with high probability, within arbitrarily small specified relative error of the true value of the permanent. 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. We discuss schemes for exact and approximate computations of permanents, and compare them with each other. Specifically, we analyze and generalize the Belief Propagation (BP) approach to computing the permanent of a non-negative matrix. Known bounds and conjectures are verified in experiments, and some new theoretical relations, bounds and conjectures are proposed. We introduce a fractional free energy functional parameterized by a scalar parameter @math , where @math corresponds to the BP limit and @math corresponds to the exclusion principle Mean-Field (MF) limit, and show monotonicity and continuity of the functional with @math . We observe that the optimal value of @math , where the @math -parameterized functional is equal to the exact free energy (defined as the minus log of the permanent), lies in the @math range, with the low and high values from the range producing provable low and upper bounds for the permanent. Our experimental analysis suggests that the optimal @math varies for different ensembles considered but it always lies in the @math interval. Besides, for all ensembles considered the behavior of the optimal @math is highly distinctive, thus offering a lot of practical potential for estimating permanents of non-negative matrices via the fractional free energy functional approach.