Poster
Approximating the Permanent by Sampling from Adaptive Partitions
Jonathan Kuck · Tri Dao · Hamid Rezatofighi · Ashish Sabharwal · Stefano Ermon

Wed Dec 11th 10:45 AM -- 12:45 PM @ East Exhibition Hall B + C #177

Computing the permanent of a non-negative matrix is a core problem with practical applications ranging from target tracking to statistical thermodynamics. However, this problem is also #P-complete, which leaves little hope for finding an exact solution that can be computed efficiently. While the problem admits a fully polynomial randomized approximation scheme, this method has seen little use because it is both inefficient in practice and difficult to implement. We present ADAPART, a simple and efficient method for exact sampling of permutations, each associated with a weight as determined by a matrix. ADAPART uses an adaptive, iterative partitioning strategy over permutations to convert any upper bounding method for the permanent into one that satisfies a desirable `nesting' property over the partition used. These samples are then used to construct tight bounds on the permanent which hold with a high probability. Empirically, ADAPART provides significant speedups (sometimes exceeding 50x) over prior work. We also empirically observe polynomial scaling in some cases. In the context of multi-target tracking, ADAPART allows us to use the optimal proposal distribution during particle filtering, leading to orders of magnitude fewer samples and improved tracking performance.

Author Information

Jonathan Kuck (Stanford)
Tri Dao (Stanford University)
Hamid Rezatofighi (Stanford University // University of Adelaide)
Ashish Sabharwal (Allen Institute for AI)
Stefano Ermon (Stanford)

More from the Same Authors