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.
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.
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