Permanents, \(\alpha \) -permanents and Sinkhorn balancing

详细信息    查看全文

• 作者：Francis Sullivan (1)
  Isabel Beichl (2)
  
• 关键词：Matrix scaling ; Doubly stochastic matrix ; Sequential importance sampling
• 刊名：Computational Statistics
• 出版年：2014
• 出版时间：December 2014
• 年：2014
• 卷：29
• 期：6
• 页码：1793-1798
• 全文大小：138 KB
• 参考文献：1. Ando T (1989) Majorization, doubly stocastic matrices and comparison of eigenvalues. Linear Algebra Appl 115:163鈥?48 CrossRef
  2. Beichl I, Sullivan F (1999) Approximating the permanent via importance sampling with application to the dimer covering problem. J Comput Phys 149:128鈥?47 CrossRef
  3. Ben-Dor A, Halevi S (1993) Zero-one permanent is #p-complete, a simpler proof. In: Proceedings of the 2nd Israel symposium on the theory and computing systems, pp 108鈥?17
  4. Knopp P, Sinkhorn R (1967) Concerning non-negative matrices and doubly stochastic matrices. Pac J Math 21:343鈥?48 CrossRef
  5. Kou S, McCullagh P (2009) Approximating the \(\alpha \) permanent. Biometrika 96:635鈥?44 CrossRef
  6. Liu JS (2001) Monte Carlo strategies in scientific computing. Springer, New York
  7. Sinkhorn R (1964) A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann Math Stat 35:876鈥?79 CrossRef
  8. Soules G (1991) The rate of convergence of sinkhorn balancing. Linear Algebra Appl 150:3鈥?0 CrossRef
  9. Tarjan R (1972) Depth-first search and linear graph algorithms. SIAM J Comput 1:146鈥?60 CrossRef
  10. Tassa T (2012) Finding all maximally-matchable edges in a bipartite graph. Theor Comput Sci 423:50鈥?8 CrossRef
  
• 作者单位：Francis Sullivan (1)
  Isabel Beichl (2)
  
  1. IDA/CCS, 17100 Science Drive, Bowie, MD聽, 20715, USA
  2. NIST, 100 Bureau Drive, Gaithersburg, MD聽, 20899, USA
  
• ISSN：1613-9658

文摘

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 explain how some simple, low cost pre-processing allows one to guarantee that Sinkhorn balancing always converges linearly. We illustrate this approach by efficiently and accurately computing permanents and \(\alpha \) -permanents of some previously studied matrices.