Timeline for Sampling from a Convex Body with Many Extremal Points
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 25, 2014 at 17:10 | comment | added | qtrs | (Sorry for the rushed ending - ran out of characters.) In any case, it would be really exciting to me if something like that were often true. As mentioned by Douglas, it can't be true in general since adding $2^{n}$ points can completely change the full body, but maybe it is true for nice enough targets. | |
| Mar 25, 2014 at 17:10 | comment | added | qtrs | Dear Omer, thanks for the comment. We tried doing a few things that seem to be in this spirit, like choosing $k > n$ points and sampling from the associated convex body. The result is biased, though in a way that is easier to understand than the nonreversible version: a point has density proportional to the number of size-$k$ convex bodies containing it. If the body has a lot of symmetry, maybe there is no bias. Otherwise, it wasn't obvious to me how to get around the bias. Is the claim that, for $k>e^{cn}$, most convex hulls of $k$-sets of extreme points cover most of the target? | |
| Mar 25, 2014 at 16:29 | comment | added | Omer | Not nearly as fast as you ask for, but you can approximate the convex hull by the hull of a smaller, possibly random subset of the points. $e^{cn}$ should suffice for a good approximation. | |
| Mar 24, 2014 at 11:51 | history | edited | qtrs | CC BY-SA 3.0 |
added 734 characters in body
|
| Mar 24, 2014 at 6:23 | comment | added | Douglas Zare | I think you need more assumptions to hope to be able to sample uniformly. You can define a distribution so that with probability about $1/2$ the convex hull is large, and with probability $1/2$ the convex hull is small, and you won't be able to rule out a large convex hull without checking almost all points. | |
| Mar 24, 2014 at 5:51 | review | First posts | |||
| Mar 24, 2014 at 6:16 | |||||
| Mar 24, 2014 at 5:34 | history | asked | qtrs | CC BY-SA 3.0 |