MATLAB: “Very” high dimensional convex hulls

Question

I am trying to generate points that are uniformly distributed over a convex hull in a high dimensional space.

What I have as input is a set of N points in D dimensions. I want to sample uniformly over the convex hull of this set points. The best solution that I have found so far is by using Matt Jacobson's "vert2lcon" (file 30892 on the FEX) to convert from vertex representation to a linear constrain representation (i.e. inequalities defining the facets of the hull), and then to use Tim Benham's "cprand" (file 34208 on the FEX) to sample uniformly over the hull.

This works great for a few dimensions, however, the hull's that I am interested in are very high dimensional, somewhere between 30-60 dimensions usually. When I try to use vert2lcon on all D~30 dimensions MATLAB crashes. The reason is that vert2lcon constructs the convex hull of my points by calling "convhulln", which in turn calls "Qhull", and the crash report says that the error is happening during the mex function for "Qhull". My guess is that it can't handle that many dimensions.

Any suggestions?

I have thought of trying to take a subset of the dimensions at a time, but I'm not sure that that would work (thought about the example of a sphere, if you take the one dimensional orthogonal projections, and compute their convex hulls you get three lines parallel to the coordinate axes, the 3D convex hull of these convex hulls is going to be an octahedron so it definitely doesn't reproduce the sphere).

Answer 1

One idea is to generate samples uniformly over a hypercube and throw out the ones that are outside of the convex hull without actually computing the hull itself. But, since I don't know which points are on the hull apriori without constructing it I'm not sure how to do this either.

You could do that by solving the QP (e.g., using lsqlin)

 min d(w) = norm(V.'*w-y).^2
s.t. sum(w)=1
     w>=0

where y is the point you want to test for inclusion in the convex hull. If the optimal d(w) is zero, then y is in the hull

You haven't mentioned how big N is so I can't know in advance how practical this would be for you.