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

Computing the volume of a polytope in high dimensions iscomputationally challenging but has wide applications. Currentstate-of-the-art algorithms to compute such volumes rely on efficientsampling of a Gaussian distribution restricted to the polytope, usinge.g. Hamiltonian Monte Carlo. We present a new sampling strategy thatuses a Piecewise Deterministic Markov Process. Like Hamiltonian MonteCarlo, this new method involves simulating trajectories of anon-reversible process and inherits similar good mixingproperties. However, importantly, the process can be simulated moreeasily due to its piecewise linear trajectories — and this leads to areduction of the computational cost by a factor of the dimension ofthe space. Our experiments indicate that our method is numericallyrobust and is one order of magnitude faster (or better) than existingmethods using Hamiltonian Monte Carlo. On a single core processor, wereport computational time of a few minutes up to dimension 500.