跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 O(n+m)\mathcal{O}(n + m) total bucket-maintenance work per trajectory, where nn is the number of rows/columns in the matrix and mm 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.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 O(n+m)\mathcal{O}(n + m) total bucket-maintenance work per trajectory, where nn is the number of rows/columns in the matrix and mm 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.

查看此版本解读 →查看此版本原文 ↗