Approximating the α-permanent

• 成果类型: Article
• 署名作者: Kou, S. C.; McCullagh, P.
• 署名单位: Harvard University; University of Chicago
• 刊物名称: BIOMETRIKA
• ISSN/ISSBN: 0006-3444
• DOI: 10.1093/biomet/asp036
• 发表日期: 2009
• 页码: 635644
• 关键词: algorithm

摘要

The standard matrix permanent is the solution to a number of combinatorial and graph-theoretic problems, and the alpha-weighted permanent is the density function for a class of Cox processes called boson processes. The exact computation of the ordinary permanent is known to be #P-complete, and the same appears to be the case for the alpha-permanent for most values of alpha. At present, the lack of a satisfactory algorithm for approximating the alpha-permanent is a formidable obstacle to the use of boson processes in applied work. This paper proposes an importance-sampling estimator using nonuniform random permutations generated in a cycle format. Empirical investigation reveals that the estimator works well for the sorts of matrices that arise in point-process applications, involving up to a few hundred points. We conclude with a numerical illustration of the Bayes estimate of the intensity function of a boson point process, which is a ratio of alpha-permanents.