Permanents, alpha-permanents and Sinkhorn balancing

Published

June 28, 2014

Author(s)

F Sullivan, Isabel M. Beichl

Abstract

The method of Sinkhorn balancing that starts with a non-negative square matrix and iterates to produce a related doubly stochastic matrix has been used with some success to estimate the values of the permanent in some cases of physical interest, However it is often claimed that Sinkhorn balancing is slow to converge and hence not useful for efficient computation. In this paper we ex[plain how some simple low cost pre-processing allows one to guarantee that Singhorn balancing always converges linearly. We illustrate this approach by efficiently and accurately computing permanents and alpha-permanents of some previously studied matrices.

Citation

Computational Statistics

Volume

29

Issue

9

Pub Type

Journals

Download Paper

https://doi.org/10.1007/s00180-014-0506-1

Local Download

Keywords

permanent, alpha-permanent, Sinkhorn balancing, sequential importance sampling

Citation

Sullivan, F. and Beichl, I. (2014), Permanents, alpha-permanents and Sinkhorn balancing, Computational Statistics, [online], https://doi.org/10.1007/s00180-014-0506-1, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=913293 (Accessed April 23, 2024)