5
$\begingroup$

I'm trying to sample uniformly on the intersections of faces of several simplicies, with all coordinates being non-negative. That is, given constraints $$A\vec{w}=\vec{b} \ \ and \ \ \vec{w} \geq \vec{0} \ \ and \ \ \sum w_i = 1,$$ I want to sample $\vec{w}$ uniformly. $A$'s dimension is about $100 \times 10000$. A concrete example will be: $$A = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix}, \ b=\begin{bmatrix} 1 \\ 0.7 \end{bmatrix}$$, sample $\vec{w}$ uniformly from $Aw=b$ subject to $\vec{w} \geq \vec{0}$ and $\sum w_i = 1$ (This makes the sampling space bounded). Below is a graphical representation of the problem -- to sample uniformly from the red intersection line.

a busy cat

I am well aware that rejection-sampling and MCMC sampling can theoretically solve this problem. However, I have already implemented both approaches in programming, and neither of these two methods performs well enough. This is because the dimension of my sampling space usually goes up to 10000, and rejection sampling simply throws away too many points and MCMC is taking forever to converge. Therefore, I'm desperate to try new methods. Many thanks in advance!! (please do not provide answers using rejection sampling; methods that already have open-source programming implementations are favored)

$\endgroup$
  • $\begingroup$ Use the algorithm I suggested in my answer to your other question. Don't use your own implementation, use the authors'. $\endgroup$ – Yuval Filmus Jun 30 '15 at 15:20
  • $\begingroup$ @YuvalFilmus Thanks! I will try the implementation in Matlab and tells you the performance later. $\endgroup$ – Miller Zhu Jul 1 '15 at 13:21
  • $\begingroup$ @D.W. 1. Yes you are right. I'm trying to sample from the intersection of faces of simplices. I will correct my problem. 2. I have not tried rejection sampling yet, but my intuition is that it will throw away too many points. Simply consider the 3D case, that one linear constraint is $x_1+x_2+x_3=1$ and another is $x_1=0.5$. The intersection is thus a line on the triangle. If I sample uniformly from the triangle first, then there will not be too many points that are exactly on the intersection (the line). This will be worse if you go up to higher dimensions, say like 10000. $\endgroup$ – Miller Zhu Jul 1 '15 at 13:24
  • 1
    $\begingroup$ @YuvalFilmus I've taken a look at the implementation you referred to. However, it is used for estimating the volume of a polytope and sampling within the polytope. However, my question is, how to sample on the intersection of the faces of the polytope. That is, how to solve $Ax=b$, but not $Ax \leq b$. Thanks! $\endgroup$ – Miller Zhu Jul 1 '15 at 14:13
  • 1
    $\begingroup$ @YuvalFilmus Thanks! I'm an R user and have never used Matlab before. So I'm confused about the commands: How do I specify the linear constraints $A$ and $b$ in makeBody, which only takes a shape and dim? For example, could you possibly tell me how to write a constraint for $A=[1 \ 1 \ 1]$ and $b=[1]$? Sorry about the trifles... $\endgroup$ – Miller Zhu Jul 1 '15 at 19:41