5
$\begingroup$

My goal is to uniformly sample from a convex polytope. I know that for the simpler case, where I have to uniformly sample from a simplex, I can use Bayesian Bootstrap, discussed in these posts:

Uniform sampling from a simplex

Random vectors uniformely distributed into convex n-polytope

Therefore, I'm very interested in this approach. But I don't really know how to use Delaunay Triangulation here. What I have is a linear equation Ax = b and a non-negativity constraint that $x \geq \vec{0}$, and I want to sample x uniformly. Can someone tell me how to do the Delaunay Triangulation here? Thanks in advance!

$\endgroup$
2
  • 1
    $\begingroup$ Is your simplex closed? Do you know rejection sampling; why is it not applicable here? $\endgroup$
    – Raphael
    Jun 29, 2015 at 14:33
  • 2
    $\begingroup$ @Raphael Yes, the simplex is closed. I know rejection sampling, but it is very inefficient -- My sampling space has dimension 1000, so rejection sampling will filter out most of the points I sampled. $\endgroup$
    – Miller Zhu
    Jun 30, 2015 at 2:13

1 Answer 1

3
$\begingroup$

This is an active area of research. Fortunately, recently there has been a breakthrough due to Vempala and Cousins [1]. They provide a MATLAB implementation of their algorithm. If you're interested in the technical details, you can check out some slides from a recent workshop.

This algorithm only samples points approximately uniformly. Exact uniform sampling, or rather the related volume estimation problem, is known to be hard (under reasonable assumptions) in general. Your convex body isn't general, however – it's a polytope. Nevertheless, the answers to this question suggest that there is no better algorithm for this special case (they suggest employing general algorithms which are older than Cousins–Vempala).


  1. Bypassing KLS: Gaussian Cooling and an $O^*(n^3)$ Volume Algorithm by B. Cousins and S. Vempala (2014, preprint)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.