most recent 30 from http://mathoverflow.net 2013-05-21T10:29:19Z http://mathoverflow.net/feeds/question/98027 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98027/is-it-possible-to-sample-uniformly-on-the-surface-of-a-high-dimensional-polytope Mark 2012-05-26T07:42:39Z 2012-05-29T01:58:43Z

<p>There are some pretty simple methods to do uniform sampling on the surface of high-dimensional spheres or cubes. Are there any methods that sample uniformly on the surface of a high-dimensional polytope?</p> <p>Given a high-dimensional polytope like this:</p> <p>$\| A \mathbf{x} \|_{\infty} = 1$</p> <p>where $A$ is a given $m \times n$ matrix and $\mathbf{x}$ is a $n \times 1$ vector.</p> <p>We want to sample a set of ${ s_1, s_2, \dots, s_n }$ that lie uniformly on the surface of this polytope.</p> <p>I'm looking at some advanced Monte Carlo Methods, but it's not that easy.</p> <p>To make the problem simpler, can we find some methods that can do infinite (non-uniform) sampling on the surface of the polytope?</p>

http://mathoverflow.net/questions/98027/is-it-possible-to-sample-uniformly-on-the-surface-of-a-high-dimensional-polytope/98044#98044 Igor Rivin 2012-05-26T14:56:00Z 2012-05-26T14:56:00Z

<p>Your question is ambiguous: from the title, it seems that you want to sample uniformly from the interior of the convex polytope. This is a heavily studied area, see for example <a href="http://mathoverflow.net/questions/9854/uniformly-sampling-from-convex-polytopes" rel="nofollow">this question</a> or <a href="http://www-stat.stanford.edu/~cgates/PERSI/papers/gibbsmetro_01Apr2011.pdf" rel="nofollow">this paper by Diaconis, Lebeau, Michel</a> (which came a couple of years later than the question). Sampling from the <em>surface</em> of a polytope has been studied much less, and I assume that it is even harder (the obvious way is to generate a list of faces, and apply the volume sampling algorithms to those; if your polytope is given as an intersection of of halfgpaces, this is roughly as hard, but if it is given as a convex hull, the number of faces could be exponential in the size of the input).</p>