高效采样高维多面体，支持稀疏结构，提升大规模计算效率
PolytopeWalk: Sparse MCMC Sampling over Polytopes
- 基于稀疏约束的MCMC方法，保持矩阵稀疏性以支持高维采样
- 在Netlib数据集和结构化多面体上实现更高采样效率与更低每步开销
- 适用于系统生物学、贝叶斯不确定性量化等需要均匀采样的领域
高维采样是统计学及其他计算学科的重要工具，应用涵盖贝叶斯不确定性量化、系统生物学中的代谢建模以及体积计算。我们提出PolytopeWalk，一个可扩展的Python库，用于在多面体上进行均匀采样。该库提供端到端解决方案，包括面约简预处理与初始化方法。实现了六种前沿的多面体MCMC算法，如Dikin、Vaidya和John Walk。此外，我们引入这些算法的新稀疏约束形式，可在形如K_2 = {x ∈ R^d | Ax = b, x ⪰_k 0}的稀疏多面体上高效采样。该实现保持矩阵A的稀疏性，确保在高维设置（d > 10^5）下的可扩展性。我们在Netlib数据集和结构化多面体上验证了采样效率提升与每步成本降低。PolytopeWalk开源地址：github.com/ethz-randomwalk/polytopewalk，文档见polytopewalk.readthedocs.io。
原文摘要 · Abstract (English)
High dimensional sampling is an important computational tool in statistics and other computational disciplines, with applications ranging from Bayesian statistical uncertainty quantification, metabolic modeling in systems biology to volume computation. We present $\textsf{PolytopeWalk}$, a new scalable Python library designed for uniform sampling over polytopes. The library provides an end-to-end solution, which includes preprocessing algorithms such as facial reduction and initialization methods. Six state-of-the-art MCMC algorithms on polytopes are implemented, including the Dikin, Vaidya, and John Walk. Additionally, we introduce novel sparse constrained formulations of these algorithms, enabling efficient sampling from sparse polytopes of the form $K_2 = \{x \in \mathbb{R}^d \ | \ Ax = b, x \succeq_k 0\}$. This implementation maintains sparsity in $A$, ensuring scalability to high dimensional settings $(d > 10^5)$. We demonstrate the improved sampling efficiency and per-iteration cost on both Netlib datasets and structured polytopes. $\textsf{PolytopeWalk}$ is available at github.com/ethz-randomwalk/polytopewalk with documentation at polytopewalk.readthedocs.io .
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。