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

Question

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?

Answer 1

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

Answer 2

The following references may be of interest:

• Shake-And-Bake Algorithms for Generating Uniform Points on the Boundary of Bounded Polyhedra - C. G. E. Boender, R. J. Caron, J. F. McDonald, A. H. G. Rinnooy Kan, H. E. Romeijn, R. L. Smith, J. Telgen and A. C. F. Vorst
• A general framework for approximate sampling with an application to generating points on the boundary of bounded convex regions - H. E. Romeijn
• Stochastic billiards for sampling from the boundary of a convex set - A. B. Dieker, Santosh Vempala

and the references provided therein.