Approximating the Permanent by Sampling from Adaptive Partitions

Jonathan Kuck, Tri Dao, Hamid Rezatofighi, Ashish Sabharwal, Stefano Ermon

Abstract

Computing the permanent of a non-negative matrix is a #P-complete problem with significant applications in target tracking and statistical thermodynamics. While theoretical approximation schemes exist, they are often computationally prohibitive. We introduce AdaPart, an efficient algorithm for drawing exact samples from the distribution defined by a matrix permanent. By utilizing adaptive partitioning and runtime verification of the "nesting" property, AdaPart achieves empirical speedups of up to 25x over previous sampling methods. Furthermore, in multi-target tracking applications, AdaPart enables high-accuracy performance with an order of magnitude fewer samples than traditional methods.

Introduction

The permanent of a square matrix $A$ is defined similarly to the determinant but lacks the alternating signs, a distinction that elevates its computational complexity from polynomial to #P-complete. In fields like multi-target tracking, the permanent represents the total probability of all possible measurement-to-target associations. Given the intractability of exact computation for large matrices, researchers typically rely on variational methods, which are fast but often loose, or sampling methods, which are exact but historically slow.

The AdaPart Algorithm

AdaPart (Adaptive Partitions) addresses the efficiency bottleneck of prior sampling techniques by moving away from rigid, pre-defined partitioning strategies.

Adaptive Partitioning

The algorithm treats the sampling process as a search over a tree of permutations. At each node, AdaPart evaluates multiple ways to partition the state space (e.g., splitting by different columns) and greedily selects the partition that minimizes the resulting upper bound. This local optimization significantly reduces the "slack" between the bound and the true value, leading to fewer rejected samples.

Runtime Verification of Nesting

A critical requirement for rejection sampling is the "nesting" property: the upper bound of a parent node must exceed the sum of its children's bounds. Previous methods were restricted to bounds where this property could be proven analytically for all possible matrices. AdaPart relaxes this constraint by using the tighter Soules bound and verifying the nesting property at runtime. If a partition fails to nest, the algorithm refines it further until the property holds, allowing for the use of much more accurate bounds.

Experimental Results

The authors evaluated AdaPart against synthetic matrices, real-world network data, and tracking simulations.

Efficiency and Speedup

AdaPart demonstrated significant performance gains over the state-of-the-art sampling baseline (Law, 2009). On real-world network matrices, speedups ranged from 12x to 25x, with the algorithm scaling efficiently as matrix dimensions increased.

Runtime comparison of AdaPart vs. Law (2009) on uniform and block diagonal matrices.

Bound Tightness

Compared to variational approximations like Sinkhorn or Bethe, AdaPart’s sampling-based approach provides substantially tighter bounds. As shown in the figure below, the Soules upper bound (used by AdaPart) remains orders of magnitude closer to the true permanent than competing variational upper bounds across various matrix structures, including uniform and block diagonal matrices.

Comparison of bound tightness (Bound/Permanent ratio) for various approximation methods across different matrix structures.

Multi-Target Tracking

In tracking simulations with 10 targets, the integration of AdaPart into a Rao-Blackwellized particle filter allowed for sampling from the optimal proposal distribution. This resulted in improved tracking accuracy (lower mean squared error and higher log-likelihood) while requiring only 10% of the samples used by standard filters like Multiple Hypothesis Tracking (MHT).

Conclusion

AdaPart represents a significant step forward in making the computation of the matrix permanent practical for real-world applications. By combining adaptive search with empirical verification of mathematical properties, it bridges the gap between the theoretical accuracy of sampling and the practical speed required for complex systems like multi-target tracking. Future work may involve sharpening the Soules bound further or extending the adaptive partitioning framework to other #P-complete problems involving partition function estimation.

Summary updated

Abstract

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 drawing exact samples from an unnormalized distribution. Using AdaPart, we show how to construct tight bounds on the permanent which hold with high probability, with guaranteed polynomial runtime for dense matrices. We find that AdaPart can provide empirical speedups exceeding 25x over prior sampling methods on matrices that are challenging for variational based approaches. Finally, in the context of multi-target tracking, exact sampling from the distribution defined by the matrix permanent allows us to use the optimal proposal distribution during particle filtering. Using AdaPart, we show that this leads to improved tracking performance using an order of magnitude fewer samples.
BibTeX
@inproceedings{kuck2019approximating,
  author = {Jonathan Kuck and Tri Dao and Hamid Rezatofighi and Ashish Sabharwal and Stefano Ermon},
  title = {{Approximating the Permanent by Sampling from Adaptive Partitions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=JQn23TR0fHM},
}
Figure