## Is it possible to sample uniformly on the surface of a high-dimensional polytope?

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?

Given a high-dimensional polytope like this:

$\| A \mathbf{x} \|_{\infty} = 1$

where $A$ is a given $m \times n$ matrix and $\mathbf{x}$ is a $n \times 1$ vector.

We want to sample a set of ${ s_1, s_2, \dots, s_n }$ that lie uniformly on the surface of this polytope.

I'm looking at some advanced Monte Carlo Methods, but it's not that easy.

To make the problem simpler, can we find some methods that can do infinite (non-uniform) sampling on the surface of the polytope?

-

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 this question or this paper by Diaconis, Lebeau, Michel (which came a couple of years later than the question). Sampling from the surface 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).

-
 Sorry for the ambiguity and thank you very much for the response. I have fixed my title. – Mark May 26 2012 at 15:23