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.

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 Creators	ORCiD
Vatedka, Shashank	0000-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://raiithold.iith.ac.in/id/eprint/11255