Title: On Convex Programming Relaxations for the Permanent,
Abstract: 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.