patternMinor
Uniform sampling over non-standard simplex
Viewed 0 times
nonsamplingstandarduniformsimplexover
Problem
Uniform sampling over a $n$-dimensional standard simplex is described here: Uniform sampling from a simplex
I want to sample one point from a non-standard simplex with vertices at:
How to do that? It seems to be no longer a special case of the Dirichlet distribution.
Hit-and-run sampling would need a lot of cycle to diffuse throughout the simplex. When I only need one point, the other points are wasted.
Currently, $n \approx 15$
I want to sample one point from a non-standard simplex with vertices at:
- $s_{i}\vec{e_{i}}$, where $\vec{e_{i}}$ is the $i^{th}$ vector in the standard basis, and $s_{i} \ge 0$.
- the origin is : $\vec{0}$
How to do that? It seems to be no longer a special case of the Dirichlet distribution.
Hit-and-run sampling would need a lot of cycle to diffuse throughout the simplex. When I only need one point, the other points are wasted.
Currently, $n \approx 15$
Solution
According to Wikipedia the $n$-simplex is the set defined by:
$$S = \left \{ \mathbf{x} \in \mathbb{R}^n \; | \; \mathbf{x} = \sum_{i=0}^n \mathbf{u}_i\theta_i , \; \mathbf{u}_k \in \mathbb{R}^n , \;\; \theta_k > 0 \;\forall k, \;\;\sum_{i=0}^n \theta_i = 1\right \}$$
Note that the $\boldsymbol{\theta} = (\theta_0, \dots, \theta_n)^T$ is the standard $n$-simplex.
Hence in order to sample from $S$, compute a linear combination of the vertices $\mathbf{u}_k$ with the weights given by a sample of the standard simplex.
Which is the same as the following random process:
Consider the matrix of vertices $U = [\mathbf{u}_0 \; \dots \; \mathbf{u}_n]$, then a sample in $S$ is given by:
$$\boldsymbol{\theta} \sim \text{Standard-Simplex}$$
$$\mathbf{x} = U \boldsymbol{\theta}$$
Note that in your case the vertex $\mathbf{u}_k = s_k \mathbf{e}_k$.
$$S = \left \{ \mathbf{x} \in \mathbb{R}^n \; | \; \mathbf{x} = \sum_{i=0}^n \mathbf{u}_i\theta_i , \; \mathbf{u}_k \in \mathbb{R}^n , \;\; \theta_k > 0 \;\forall k, \;\;\sum_{i=0}^n \theta_i = 1\right \}$$
Note that the $\boldsymbol{\theta} = (\theta_0, \dots, \theta_n)^T$ is the standard $n$-simplex.
Hence in order to sample from $S$, compute a linear combination of the vertices $\mathbf{u}_k$ with the weights given by a sample of the standard simplex.
Which is the same as the following random process:
Consider the matrix of vertices $U = [\mathbf{u}_0 \; \dots \; \mathbf{u}_n]$, then a sample in $S$ is given by:
$$\boldsymbol{\theta} \sim \text{Standard-Simplex}$$
$$\mathbf{x} = U \boldsymbol{\theta}$$
Note that in your case the vertex $\mathbf{u}_k = s_k \mathbf{e}_k$.
Context
StackExchange Computer Science Q#99731, answer score: 2
Revisions (0)
No revisions yet.