PolytopeWalk: Sparse MCMC Sampling over Polytopes
OPEN ACCESS
Loading...
Author / Producer
Date
2025-07-28
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Web of Science:
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
High dimensional sampling is an important computational tool in statistics, with applications in stochastic simulation, volume computation, and fast randomized algorithms. We present PolytopeWalk, a scalable library designed for sampling from a uniform distribution over polytopes, which are bounded geometric objects formed by linear inequalities. For sampling, we use Markov chain Monte Carlo (MCMC) methods, defined as a family of algorithms for generating approximate samples from a target probability distribution. Six state-of-the-art MCMC algorithms 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 𝒦2 = {𝑥 ∈ ℝ𝑑 | 𝐴𝑥 = 𝑏, 𝑥 ⪰𝑘 0}. This implementation maintains sparsity in 𝐴, ensuring scalability to higher dimensional settings in per-iteration cost. Finally, PolytopeWalk includes implementations of 2 preprocessing algorithms, facial reduction and initialization, thus providing an end-to-end solution.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
10 (111)
Pages / Article No.
7957
Publisher
Open Journals
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Computation (stat.CO); Machine Learning (cs.LG); Machine Learning (stat.ML); FOS: Computer and information sciences
Organisational unit
09819 - Chen, Yuansi / Chen, Yuansi
Notes
Funding
Related publications and datasets
Is new version of: 10.48550/arXiv.2412.06629