# Efficient computation of the volume of a polytope in high-dimensions using Piecewise Deterministic Markov Processes

arXiv: https://arxiv.org/abs/2202.09129 · HTML: https://mlsanity.com/paper/2202.09129/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 42 references that are in the map.
- First posted on arXiv 18 Feb 2022.

## Builds on (most cited first, 9 of 9)

- [On the marginal likelihood and cross-validation](https://mlsanity.com/paper/1905.08737/) (2019)
- [Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation](https://mlsanity.com/paper/1710.06261/) (2017)
- [The Bouncy Particle Sampler: A Non-Reversible Rejection-Free Markov Chain Monte Carlo Method](https://mlsanity.com/paper/1510.02451/) (2015)
- [Piecewise Deterministic Markov Processes for Continuous-Time Monte Carlo](https://mlsanity.com/paper/1611.07873/) (2016)
- [Volesti: Volume Approximation and Sampling for Convex Polytopes in R](https://mlsanity.com/paper/2007.01578/) (2020)
- [Gaussian Cooling and O*(n^3) Algorithms for Volume and Gaussian Volume](https://mlsanity.com/paper/1409.6011/) (2014)
- [Piecewise Deterministic Markov Processes for Scalable Monte Carlo on Restricted Domains](https://mlsanity.com/paper/1701.04244/) (2017)
- [Practical volume computation of structured convex bodies, and an application to modeling portfolio dependencies and financial crises](https://mlsanity.com/paper/1803.05861/) (2018)
- [Geometric algorithms for sampling the flux space of metabolic networks](https://mlsanity.com/paper/2012.05503/) (2020)

## Built on by (most cited first, 3 of 3)

- [Provable Preimage Under-Approximation for Neural Networks (Full Version)](https://mlsanity.com/paper/2305.03686/) (2023)
- [PREMAP: A Unifying PREiMage APproximation Framework for Neural Networks](https://mlsanity.com/paper/2408.09262/) (2024)
- [Resonances in reflective Hamiltonian Monte Carlo](https://mlsanity.com/paper/2504.12374/) (2025)

## Abstract (arXiv)

Computing the volume of a polytope in high dimensions is computationally challenging but has wide applications. Current state-of-the-art algorithms to compute such volumes rely on efficient sampling of a Gaussian distribution restricted to the polytope, using e.g. Hamiltonian Monte Carlo. We present a new sampling strategy that uses a Piecewise Deterministic Markov Process. Like Hamiltonian Monte Carlo, this new method involves simulating trajectories of a non-reversible process and inherits similar good mixing properties. However, importantly, the process can be simulated more easily due to its piecewise linear trajectories - and this leads to a reduction of the computational cost by a factor of the dimension of the space. Our experiments indicate that our method is numerically robust and is one order of magnitude faster (or better) than existing methods using Hamiltonian Monte Carlo. On a single core processor, we report computational time of a few minutes up to dimension 500.