← 研踪 PaperTrailarXiv:2608.15390 · v2
The Quick and the Dead: Estimating Sparse-Matrix Permanents with Adaptive Work Filtering
首次提交 2026-08-16 03:44
版本更新 2026-11-16 18:02
雷达观测 2026-11-17 17:11
摘要
Rasmussen's permanent estimator is a simple and unbiased estimator for the permanent of a binary matrix, but its practical performance can be limited by trajectories that terminate before completing a perfect matching. These failed trajectories, together with dispersion among the surviving weights, can substantially reduce the effective sample size. Although the literature leverages techniques such as doubly-stochastic matrix scaling to improve proposal balance and support filtering to remove structurally infeasible choices, using these at every step can substantially increase the trajectory cost. Furthermore, these techniques do not directly address the choice of the next vertex whose residual neighborhood is used for the proposal. This paper uses the classical minimum-degree ordering in sparse matrix algorithms to select the next vertex with total bucket-maintenance work per trajectory, where is the number of rows/columns in the matrix and is the number of nonzeros. The proposed estimator uses adaptive schedules to invoke the more expensive scaling and filtering operations only when needed. The experiments show favorable empirical accuracy under fixed time budgets on the tested matrices.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-16 18:02 · 最新观测版本
The Quick and the Dead: Estimating Sparse-Matrix Permanents with Adaptive Work Filtering
Rasmussen's permanent estimator is a simple and unbiased estimator for the permanent of a binary matrix, but its practical performance can be limited by trajectories that terminate before completing a perfect matching. These failed trajectories, together with dispersion among the surviving weights, can substantially reduce the effective sample size. Although the literature leverages techniques such as doubly-stochastic matrix scaling to improve proposal balance and support filtering to remove structurally infeasible choices, using these at every step can substantially increase the trajectory cost. Furthermore, these techniques do not directly address the choice of the next vertex whose residual neighborhood is used for the proposal. This paper uses the classical minimum-degree ordering in sparse matrix algorithms to select the next vertex with total bucket-maintenance work per trajectory, where is the number of rows/columns in the matrix and is the number of nonzeros. The proposed estimator uses adaptive schedules to invoke the more expensive scaling and filtering operations only when needed. The experiments show favorable empirical accuracy under fixed time budgets on the tested matrices.
查看此版本解读 →查看此版本原文 ↗