Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $p_{1}, \ldots, p_{N}$ be a collection of points in $\mathbb{R}^{n}$. I would like to sample uniformly from the convex hull of these $N$ points in an `efficienct' way. In my setting, I have $n$ moderate (e.g. $n \approx 500$) but $N$ very large (e.g. $N \approx 2^{n^{2}}$).

I am aware that there is a great deal of work by Lovasz et. al. on using hit-and-run algorithms for doing this type of sampling. Unfortunately, to my knowledge that algorithm is impractical in my setting: when $N$ is very large compared to $n$, the cost of running the algorithm is dominated by the (large) cost of finding the boundaries of the convex body along a slice. In particular, this work suggests that around $n^{3}$ steps of a Markov chain are required to get a single good sample, but each step still seems to require at least $N$ operations.

I do have one advantage in this setting: I can sample a random element of $p_{1}, \ldots, p_{N}$ quite quickly (e.g. in time $O(\log(N))$. I thought that perhaps a "nonreversible" hit-and-run sampler might be possible, but so far don't have anything particularly general in that direction.

Thanks for any help!

EDIT: In response to Douglas Zare's comment below, I'll also add:

  1. It is certainly too much to ask for a sampling algorithm that is always' good in the above setting. I think I'll settle for a somewhat general algorithm that issometimes' good. As a baseline check on generality, it probably shouldn't fail miserably on e.g. the simplex. As a baseline check on goodness, I probably want something that is at least plausibly subexponential in $n$ and $\log(N)$.
  2. The examples that I care most about are moderately nice - e.g. there are $k$-transitive actions on the vertices for $k$ pretty big. So I feel at least moderately optimistic that algorithms that sometimes work given this data will probably work in my setting.
share|improve this question
1  
I think you need more assumptions to hope to be able to sample uniformly. You can define a distribution so that with probability about $1/2$ the convex hull is large, and with probability $1/2$ the convex hull is small, and you won't be able to rule out a large convex hull without checking almost all points. –  Douglas Zare Mar 24 at 6:23
    
Thank you! Some changes to the question above. –  qtrs Mar 24 at 11:51
    
Not nearly as fast as you ask for, but you can approximate the convex hull by the hull of a smaller, possibly random subset of the points. $e^{cn}$ should suffice for a good approximation. –  Omer Mar 25 at 16:29
    
Dear Omer, thanks for the comment. We tried doing a few things that seem to be in this spirit, like choosing $k > n$ points and sampling from the associated convex body. The result is biased, though in a way that is easier to understand than the nonreversible version: a point has density proportional to the number of size-$k$ convex bodies containing it. If the body has a lot of symmetry, maybe there is no bias. Otherwise, it wasn't obvious to me how to get around the bias. Is the claim that, for $k>e^{cn}$, most convex hulls of $k$-sets of extreme points cover most of the target? –  qtrs Mar 25 at 17:10
    
(Sorry for the rushed ending - ran out of characters.) In any case, it would be really exciting to me if something like that were often true. As mentioned by Douglas, it can't be true in general since adding $2^{n}$ points can completely change the full body, but maybe it is true for nice enough targets. –  qtrs Mar 25 at 17:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.