{'fraction_non_alphanumeric': 0.0421996765181591, 'fraction_numerical': 0.009998529627995884, 'mean_word_length': 4.313671875, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Convex Programming Relaxations for the Permanent

In recent years, several convex programming relaxations have been proposed to estimate the permanent of a non-negative matrix, notably in the works of Gurvits and Samorodnitsky. However, the origins of these relaxations and their relationships to each other have remained somewhat mysterious. We present a conceptual framework, implicit in the belief propagation literature, to systematically arrive at these convex programming relaxations for estimating the permanent -- as approximations to an exponential-sized max-entropy convex program for computing the permanent. Further, using standard convex programming techniques such as duality, we establish equivalence of these aforementioned relaxations to those based on capacity-like quantities studied by Gurvits and Anari et al.


Introduction
Let A ∈ R n×n be a square matrix with entries A i,j for 1 ≤ i, j ≤ n. The permanent of A is defined as: where S n is the set of all permutations over n symbols, i.e., the set of bijections σ : {1, 2, . . . , n} → {1, 2, . . . , n}. The matrix permanent makes its appearance in various branches of science and mathematics and algorithms to compute it are sought after, especially in theoretical computer science.
In a foundational result, Valiant [Val79] proved that it is unlikely that there is an efficient algorithm that computes the permanent of a matrix -even when the matrix is non-negative (the problem is #P−complete). Jerrum, Sinclair and Vigoda [JSV04], building upon a long line of work, showed that the Markov Chain Monte Carlo framework can be deployed to obtain a randomized algorithm to estimate the permanent of any non-negative matrix to within a factor of 1 + ε in time that is polynomial in the bit-lengths of A and 1/ε.
A different approach to estimate the value of the permanent of a non-negative matrix has been developed -notably in the works of Linial, Samorodnitsky and Wigderson [LSW98] and Gurvits and Samorodnitsky [GS02]. Roughly, the idea in these works is to reduce the computation of the permanent of a non-negative matrices to that of a n × n doubly stochastic matrix by computing a certain scaling. The latter work [GS02] reveals how the scalings can be viewed as solutions to certain convex programs -leading to convex programming relaxations for the permanent. The resolution of the van der Waerden conjecture by Egorychev [Ego81] and Falikman [Fal81] -that the permanent of a doubly stochastic matrix is lower bounded by e −n -resulted in a deterministic algorithm to estimate the permanent up to a multiplicative ratio of e n . Of note here is a relaxation introduced by Gurvits [Gur06], called the capacity of the associated polynomial p A (applies more generally), which allowed him to deploy the theory of hyperbolic or real-stable polynomials to derive the same result. These ideas were further developed in the works of [Gur11,GS14] where a curious convex program was presented and, it was shown using an inequality due to Schrijver [Sch98], that this program estimates the value of the permanent up to a 2 n factor.
The problem of computing the permanent has also attracted attention in statistical physics and, in particular, the belief propagation literature [WC10,Von13,CY13]. These algorithms are geared towards computing approximations to the Gibbs distribution associated to the matrix A. A bit more formally, if G = (V, W, E) is the bipartite graph where |V | = |W | = n and (i, j) ∈ E if A i,j > 0 and M is the set of perfect matchings in G, then the Gibbs distribution induced by A and supported on M is one where, for a matching M ∈ M, the probability of M , denoted by, p(M ), is The idea then is to maintain a proxy to p(M ), or a belief distribution b : M → R ≥0 and iteratively update it according to certain rules. It is not clear when and how quickly such algorithms converge although they seem to work well in practice and for locally tree-like graphs.
Are these three seemingly distinct approaches to compute the permanent, coming from different areas, connected?
The goal of this paper is to present some old and some new results in a unified manner which seem to suggest that there may be a close connection between the latter two approaches. The starting point to our work is the well-known fact that the following convex program has log Per(A) as its optimal value. (1) Each variable of this program corresponds to a perfect matching in G, and the goal is to find a probability distribution over perfect matchings in G that minimizes the Kullback-Leibler divergence from the Gibbs distribution. Thus, if one could compute the optimal value of this program then one could estimate the permanent exactly. However, the number of variables in this program can be exponentially large and it is not clear how to solve it. One can take the dual of this program, however, that leads (predictably) to the same problem; see [SV14] for more details. We show how we can bypass this barrier and construct approximate convex programs starting from this one by making assumptions on the distribution we are seeking. Key to these simplifications are some heuristics from belief propagation, which result in certain relations between these marginals that one (wishfully) expects the optimal distribution p to satisfy. Assuming these relationships, one can then write the above convex program entirely in terms of the first order marginals of the distribution b -dramatically reducing the number of variables. Of course, as a result of these simplifications, the convex programs obtained are approximations of the one above; see (3) and (6). However, as proved by Gurvits [Gur06] and Gurvits and Samorodnitsky [GS14], they give us some of the best deterministic algorithms to estimate the value of Per(A). We expect that our point of view will lead to new convex programming methods for other counting problems (such as those studied in [SV16]) by leveraging on heuristic reasonings from belief propagation.

Relaxations via Belief Propagation
Belief propagation algorithms attempt to find the Gibbs distribution p by maintaining belief distributions b supported over M. These relations are often arrived at by considering the case when G is a tree. In the following two subsections, we show that using two different relations, we end up with two different convex programs which, in turn, via standard techniques from convex programming allow us to recover the convex programs from [GS02, Gur09, Gur11, GS14, AMOV16]. Some of the results we present are implicit in the papers by [WC10,Von13,CY13,CS15]. Our contribution is to present the unified picture along with some new relations.
Let us now introduce some notation to explain the ideas formally. For a probability distribution b supported on M we denote by b i,j (1) the probability that the edge (i, j) is present in a random matching is a doubly stochastic matrix with support determined by A. We denote this set by Ω n (A) and the set of all doubly stochastic matrices by Ω n .

Gurvits' first relaxation for the permanent
The starting point here is the following observation that when G is a tree and b is any distribution over perfect matchings in G, then In other words, the probability of a perfect matching in G is completely determined by the marginal probabilities of the edges and is computed as if all the events (corresponding to picking a particular edge) were independent. The reason why this is trivially true in the case of a tree is because a tree has at most one perfect matching. Therefore, all the marginals are either zero or one, depending whether a given edge belongs to the unique perfect matching or not. The heuristic jump then occurs when one, wishfully thinking, hopes that these relations hold for all graphs -at least when b is the Gibbs distribution p. While incorrect, assuming that b satisfies (2), leads us to the convex program as an approximation to that in (1) in the following manner: The expression on the right hand side can be simplified further. Consider Thus the relaxation (1) reduces to the problem of maximizing the above expression over B ∈ Ω n (A), i.e., we arrive at the following convex program: 1 (3) Using Lagrangian duality, we can now derive the relaxation considered by Gurvits. For variables z 1 , . . . , z n consider the polynomial q A (z) One can show using standard techniques that the following is the dual of the above convex program.

Formally one can prove the following theorem (see Appendix A and [CS15]):
Theorem 2.1 For all non-negative n × n matrices A, R C (A) = exp(R E (A)).
Since the coefficient of Furthermore an important result of Gurvits [Gur06], which makes this convex program interesting, asserts that an upper bound holds: R C (A) ≤ e n · Per(A).
Note that even though we arrived at this convex program by making an incorrect assumption on the Gibbs distribution, the result is a relaxation which provably approximates the permanent up to a factor of e nthus yielding a deterministic algorithm to estimate the value of the permanent of A.
We conclude this section by showing how (3) can be reinterpreted in the language of polynomials, resulting in another relaxation for the permanent implicit in the work of [AMOV16] (see also [Gur09]). To explain their relaxation, consider any two positive matrices C and D such that their entry-wise product is equal to A, i.e., A i,j = C i,j · D i,j for all 1 ≤ i, j ≤ n. Define n 2 −variate polynomials p(x) = n i=1 n j=1 x i,j C i,j and q(y) = n j=1 n i=1 y i,j D i,j . Then the relaxation is as follows: 2 We observe that this relaxation is equivalent to (3).
Theorem 2.2 For all non-negative n × n matrices A, R P (A) = exp(R E (A)).
The proof can be easily deduced from the following observation.
Claim 2.3 Let r be the following polynomial over n 2 variables x i,j (for 1 ≤ i, j ≤ n) where M is any matrix with positive entries. Let B ∈ Ω n be any doubly stochastic matrix, then The proof of Claim 2.3 appears in Appendix B.
2 In the relaxation defining R P (A) one can equivalently optimize over a larger domain for B, namely B ∈ [0, 1] n×n .

Gurvits' second relaxation for the permanent
To derive the second relaxation, as before we start with a relation among a distribution b and its marginals which holds (again trivially) when G is a tree.
The reason this is true for trees is that for the unique perfect matching M of G for (i, j) ∈ M we have b i,j (1) = 1 and for (i, j) / ∈ M we have b i,j (0) = 1. As in the previous section, we make a jump and assume that this relation holds for any bipartite graph -at least for the case of the Gibbs distribution.
Let us simplify the convex program (1) using (5) as an assumption. We obtain that the objective of the convex program (1) can be written as The expression on the right hand side can be simplified as before to obtain Similarly, This allows us to rewrite the convex program (1) in the following form: It is worth noting that even though the program (1) is convex, it does not imply that the objective in (6) is convex. In fact it is convex only when restricted to the domain Ω n , which was observed by [Von13]. Even more remarkable is the fact that, despite us plugging in the relations between the marginals that are only guaranteed to hold when G is a tree, it was proved that the approximation guarantee is even better as for the first relaxation. Here proving that this convex program has any relation to the permanent requires some work and, indeed, Gurvits, using an inequality due to Schrijver [Sch98], proved that Notice here that the estimate obtained from the convex program provides a lower bound to the permanent unlike Gurvits' first relaxation. Subsequently, Gurvits and Samorodnitsky [GS14] proved that this quantity in fact provides a sharp estimate for the permanent: Finally, we show how another polynomial-based relaxation for the permanent that is implicit in [AMOV16] is equivalent to (6). Let, as before, C and D be two positive matrices such that their entry-wise product is equal to A, i.e., A i,j = C i,j · D i,j for all 1 ≤ i, j ≤ n. Define polynomials p(x) = n i=1 n j=1 x i,j C i,j and q(y) = n j=1 n i=1 y i,j D i,j . Consider the following As in the case of the first relaxation, we have the following theorem.   Note importantly that the objective of (8) is concave in B. We now derive the dual of the above program. Introduce Lagrangian multipliers α, β ∈ R n for the row and column stochasticity constraints. We arrive at the Lagrangian The next step is to compute g(α, β) = sup B≥0 L(B, α, β).
To this end let us compute the derivative of L with respect to B i,j .
By plugging in these values to the Lagrangian, we obtain Since the Slater's condition is satisfied for (8), strong duality holds and we can deduce that Finally, we can eliminate one set of variables due to a simple form of the dual objective g(α, β). Indeed, let us rewrite g(α, β) as We derive analytically a formula for h(β) = min α∈R n g(α, β). Note that the problem of minimizing over α is separable and hence we just need to solve a sequence of optimization problems of the form min αi∈R e −1−αi n j=1 A i,j e −βj + α i .
By a simple calculation, the optimal value of the above is log  Finally we obtain R E (A) = min α,β∈R n g(α, β) = min β∈R n h(β) = log R C (A).

B Proof of Claim 2.3
Proof: For any x ∈ R n×n >0 and any positive doubly stochastic matrix B we have To deduce equality it remains to observe that the applied Jensen's inequality is tight whenever x i,j Mi,j Bi,j = const. which can be easily achieved by plugging in an appropriate value of x.