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:
- 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)$. - 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.
