Modified Bethe Permanent of a Nonnegative Matrix

Vatedka, Shashank and Vontobel, Pascal (2020) Modified Bethe Permanent of a Nonnegative Matrix. In: 2020 International Conference on Signal Processing and Communications, SPCOM 2020, 19 July 2020through 24 July 2020, Bangalore.

[img] Text
Modified_Bethe_Permanent_of_a_Nonnegative_Matrix.pdf - Published Version
Available under License Creative Commons Attribution Non-commercial.

Download (463kB)

Abstract

Currently the best deterministic polynomial-time algorithm for approximating the permanent of a non-negative matrix is based on minimizing the Bethe free energy function of a certain normal factor graph (NFG). In order to improve the approximation guarantee, we propose a modified NFG with fewer cycles, but still manageable function-node complexity; we call the approximation obtained by minimizing the function of the modified normal factor graph the modified Bethe permanent. For nonnegative matrices of size 3× 3, we give a tight characterization of the modified Bethe permanent. For non-negative matrices of size n× n with n≥ 3, we present a partial characterization, along with promising numerical results. The analysis of the modified NFG is also interesting because of its tight connection to an NFG that is used for approximating a permanent-like quantity in quantum information processing. © 2020 IEEE.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Vatedka, Shashank0000-0003-2384-9392
Item Type: Conference or Workshop Item (Paper)
Additional Information: This work was done when the first author was a postdoc at the Dept. of Information Engineering, The Chinese University of Hong Kong, where he was supported in part by CUHK Direct Grants 4055039 and 4055077. The work described in this paper was partially supported by grants from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project Nos. CUHK 14209317 and CUHK 14207518).
Uncontrolled Keywords: Bethe free energy; Node complexity; Non-negative matrix; Normal factor graphs; Numerical results; Partial characterization; Polynomial-time algorithms; Quantum-information processing
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 15 Nov 2022 05:58
Last Modified: 15 Nov 2022 05:58
URI: http://raiith.iith.ac.in/id/eprint/11255
Publisher URL: http://doi.org/10.1109/SPCOM50965.2020.9179492
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 11255 Statistics for this ePrint Item