论文标题
使用分段确定性马尔可夫进程对高维度中多层体积的有效计算
Efficient computation of the volume of a polytope in high-dimensions using Piecewise Deterministic Markov Processes
论文作者
论文摘要
在高维度上计算多层室的体积在计算上具有挑战性，但应用很广。计算此类体积的当前最新算法取决于使用例如使用例如使用的高斯分布的有效采样，例如汉密尔顿蒙特卡洛。我们提出了一种使用分段确定性马尔可夫流程的新采样策略。像哈密顿蒙特·卡洛（Hamiltonian Monte Carlo）一样，这种新方法涉及模拟非可逆过程的轨迹，并继承了类似的良好混合特性。但是，重要的是，由于其分段线性轨迹，可以更容易地模拟该过程 - 这会导致将计算成本降低到空间尺寸的因素。我们的实验表明，与使用汉密尔顿蒙特卡洛（Hamiltonian Monte Carlo）的现有方法相比，我们的方法在数值上是鲁棒的，并且比现有方法更快（或更好）。在单个核心处理器上，我们报告了几分钟的计算时间至尺寸500。
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.
