Post History
#3: Post edited
by
purplenanite
·
2024-09-28T19:05:12Z (3 months ago)
Included a second set of edits meant to demonstrate the dimensionality of the problem
How do I (efficiently) sample from the interior of a convex hull?
- How do I (efficiently) sample from the interior of a convex polytope?
I wish to sample a "typical" point in the interior of a convex hull.- The volume is defined by vectors $\vec{G}_k$ and values $v_k$
- such that $\forall k,(\vec{X} \cdot \vec{G}_k) > v_k$.
However, I also have an additional point $\vec{X}_j$ which is guaranteed to be on the edge of the convex hull normal to the vector $\vec{G}_j$ .- I currently have a few ideas:
- I could use the Metropolis-Hastings algorithm, which would start with $\vec{X}_j$ and perturb it with a normal distribution, accepting the new point if it stays in the interior of the convex shape, until it "looks right"? But I don't know how many samples I would need to process until that occurs, nor the hyperparameters to use?
I could also try perturbing $\vec{X}_j$ in the direction of $\vec{G}_j$, which would push the point away from the edge of the shape?
- I wish to sample a "typical" point in the interior of a convex polytope.
- The volume is defined by vectors $\vec{G}_k$ and values $v_k$
- such that $\forall k,(\vec{X} \cdot \vec{G}_k) > v_k$.
- However, I also have an additional point $\vec{X}_j$ which is guaranteed to be on the boundary of the convex polytope normal to the vector $\vec{G}_j$ .
- I currently have a few ideas:
- I could use the Metropolis-Hastings algorithm, which would start with $\vec{X}_j$ and perturb it with a normal distribution, accepting the new point if it stays in the interior of the convex shape, until it "looks right"? But I don't know how many samples I would need to process until that occurs, nor the hyperparameters to use?
- I could also try perturbing $\vec{X}_j$ in the direction of $\vec{G}_j$, which would push the point away from the boundary of the shape?
- (This is also in a very high dimensional space, of about 100,000 - but the exact number isn't too important)
#2: Post edited
by
purplenanite
·
2024-09-27T02:28:51Z (3 months ago)
specified interior of shape
How do I (efficiently) sample from a convex hull?
- How do I (efficiently) sample from the interior of a convex hull?
I wish to sample a "typical" point of a convex hull.- The volume is defined by vectors $\vec{G}_k$ and values $v_k$
- such that $\forall k,(\vec{X} \cdot \vec{G}_k) > v_k$.
- However, I also have an additional point $\vec{X}_j$ which is guaranteed to be on the edge of the convex hull normal to the vector $\vec{G}_j$ .
- I currently have a few ideas:
I could use the Metropolis-Hastings algorithm, which would start with $\vec{X}_j$ and perturb it with a normal distribution, accepting the new point if it stays inside the convex shape, until it "looks right"? But I don't know how many samples I would need to process until that occurs, nor the hyperparameters to use?- I could also try perturbing $\vec{X}_j$ in the direction of $\vec{G}_j$, which would push the point away from the edge of the shape?
- I wish to sample a "typical" point in the interior of a convex hull.
- The volume is defined by vectors $\vec{G}_k$ and values $v_k$
- such that $\forall k,(\vec{X} \cdot \vec{G}_k) > v_k$.
- However, I also have an additional point $\vec{X}_j$ which is guaranteed to be on the edge of the convex hull normal to the vector $\vec{G}_j$ .
- I currently have a few ideas:
- I could use the Metropolis-Hastings algorithm, which would start with $\vec{X}_j$ and perturb it with a normal distribution, accepting the new point if it stays in the interior of the convex shape, until it "looks right"? But I don't know how many samples I would need to process until that occurs, nor the hyperparameters to use?
- I could also try perturbing $\vec{X}_j$ in the direction of $\vec{G}_j$, which would push the point away from the edge of the shape?
#1: Initial revision
by
purplenanite
·
2024-09-26T18:07:46Z (3 months ago)
How do I (efficiently) sample from a convex hull?
I wish to sample a "typical" point of a convex hull.
The volume is defined by vectors $\vec{G}_k$ and values $v_k$
such that $\forall k,(\vec{X} \cdot \vec{G}_k) > v_k$.
However, I also have an additional point $\vec{X}_j$ which is guaranteed to be on the edge of the convex hull normal to the vector $\vec{G}_j$ .
I currently have a few ideas:
I could use the Metropolis-Hastings algorithm, which would start with $\vec{X}_j$ and perturb it with a normal distribution, accepting the new point if it stays inside the convex shape, until it "looks right"? But I don't know how many samples I would need to process until that occurs, nor the hyperparameters to use?
I could also try perturbing $\vec{X}_j$ in the direction of $\vec{G}_j$, which would push the point away from the edge of the shape?