2022/05/30 by Kit Shing Ng, Pascal O. Vontobel, Ng, Kit Shing +1 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Information Theory (cs.IT) #Matrix Theory and Algorithms #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2205.15186
openalex publication_date 2022/05/30 · openalex created_date 2022/06/13 · openalex updated_date 2026/07/28
The permanent of a non-negative matrix appears naturally in many information processing scenarios. Because of the intractability of the permanent beyond small matrices, various approximation techniques have been developed in the past. In this paper, we study the Bethe approximation of the permanent and add to the body of literature showing that this approximation is very well behaved in many respects. Our main technical tool are topological double covers of the normal factor graph whose partition function equals the permanent of interest, along with a transformation of these double covers.