Double-Cover-Based Analysis of the Bethe Permanent of Block-Structured Positive Matrices
Provides theoretical understanding of the Bethe permanent approximation for block-structured matrices, which is of interest to researchers in matrix analysis and graphical models.
The paper studies the ratio of the permanent to the Bethe permanent for block-structured positive matrices, finding that the ratio is strongly concentrated around a value depending only on key parameters, and uses graph-cover-based approaches to explain and quantify this behavior.
We consider the permanent of a square matrix with non-negative entries. A tractable approximation is given by the so-called Bethe permanent that can be efficiently computed by running the sum-product algorithm on a suitable factor graph. While the ratio of the permanent of a matrix to its Bethe permanent is, in the worst case, upper and lower bounded by expressions that are exponentially far apart in the matrix size, in practice it is observed for many ensembles of matrices of interest that this ratio is strongly concentrated around some value that depends only on the matrix size. In this paper, for an ensemble of block-structured matrices where entries in a block take the same value, we numerically study the ratio of the permanent of a matrix to its Bethe permanent. It is observed that also for this ensemble the ratio is strongly concentrated around some value depending only on a few key parameters of the ensemble. We use graph-cover-based approaches to explain the reasons for this behavior and to quantify the observed value.