Approximating the Permanent by Sampling from Adaptive Partitions

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

Computing the permanent of a matrix is a notoriously difficult (#P-complete) problem essential for tasks ranging from multi-target tracking to graph theory. While the determinant of a matrix is easy to compute, the permanent—which looks similar but lacks alternating signs—scales exponentially in complexity. This paper introduces ADAPART, an algorithm that adaptively partitions the state space to draw exact samples from the distribution defined by the permanent, achieving significant speedups and enabling high-performance target tracking.

The Challenge of the Permanent

Why do we care about the permanent? It counts perfect matchings in bipartite graphs and cycle covers in directed graphs. In real-world applications like multi-target tracking, it is the "secret sauce" that helps calculate the marginal probability that a specific measurement belongs to a specific target.

Existing solutions fall into three flawed camps:

  1. Exact Algorithms: These only work for tiny matrices (e.g., up to 40x40) due to exponential scaling.
  2. Theoretical Approximations (FPRAS): While guaranteed to work in polynomial time, they are so complex and slow ($O(n^7 \log^4 n)$) that they are practically useless in real-world scenarios.
  3. Variational Methods: These are very fast, but their bounds are often "exponentially loose," meaning the estimate could be off by a massive margin.

The authors aim to bridge this gap with a sampling-based approach that is both mathematically exact and practically fast.

Introducing ADAPART

The core of the paper is ADAPART (Adaptive Partitions). It builds on the concept of "rejection sampling with nesting bounds." If you have an upper bound on a complex distribution that "nests" (where the bound of the whole is greater than the sum of the bounds of its parts), you can use it to create a proposal distribution for exact sampling.

ADAPART introduces several key innovations:

  • Adaptive Partitioning: Previous methods used a fixed, rigid way to split the state space. ADAPART adaptively chooses how to split the matrix (which column to partition on) at each step to minimize "slack"—the gap between the bound and the truth.
  • Runtime Verification: Instead of relying on a bound that is proven to nest for all cases (which limits you to weaker bounds), ADAPART uses a tighter bound (the Soules bound) and simply checks if the nesting property holds at runtime. If it doesn't, it refines the partition until it does.
  • Greedy Optimization: At each step, the algorithm performs a local optimization to choose the partition yielding the tightest combined upper bound.

Datasets and Key Results

The authors evaluated ADAPART across random matrices (uniform and block-diagonal), real-world networks (cheminformatics, DNA electrophoresis, power networks), and synthetic multi-target tracking simulations.

Comparison of upper and lower bounds on the permanent for different matrix types.

The results demonstrate significant improvements over existing methods:

  • Speed: ADAPART is 12x to 32x faster than the previous state-of-the-art sampling baseline on real-world network matrices.
  • Tightness: The bounds produced by ADAPART are orders of magnitude tighter than variational methods (like Sinkhorn or Bethe). For example, on the bcspwr01 dataset, ADAPART's upper bound (log scale) was 20.1 compared to Sinkhorn's 40.3. By adaptively choosing partitions, ADAPART significantly reduces "slack," leading to fewer rejected samples.
  • Tracking Efficiency: In multi-target tracking simulations, the "optimal" proposal distribution is defined by the matrix permanent. Because ADAPART makes sampling from this distribution efficient, it allows trackers to find high-likelihood associations much faster. ADAPART achieved lower mean squared error and higher log-likelihood using 10x fewer samples than traditional sequential proposal distributions or Multiple Hypothesis Tracking (MHT).

Limitations and Future Directions

While the paper provides a polynomial runtime guarantee for dense matrices, performance on extremely sparse or specifically structured matrices may vary, although empirical results on block-diagonal matrices remain promising.

The efficiency of ADAPART is inherently tied to the quality of the underlying upper bound. The authors suggest that incorporating even tighter bounds (like the Bethe bound) into the ADAPART framework could yield further improvements, provided they can be computed efficiently. Finally, while focused on the permanent, the ADAPART framework is general. Future work could apply it to other #P-complete problems involving partition functions in graphical models.

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