论文标题
宾厄姆分销的有效抽样
Efficient sampling from the Bingham distribution
论文作者
论文摘要
我们给出了从Bingham分布$ p（x）\ propto \ exp（x^\ top a x）$的精确采样的算法，$ \ mathcal s^{d-1} $，预期的运行时间为$ \ operatateOrnAme {poly}（poly}（poly）{poly}（d，λ_=，λ_ {\ max} $）$} $}。该算法基于排斥采样，其中建议分布是PDF的多项式近似，并且可以通过明确评估在球体上多项式的积分来取样。假设多项式的逆函数的精确计算，我们的算法给出了精确的样品。这与马尔可夫链蒙特卡洛算法相反，蒙特卡洛算法尚不在此问题上快速混合，并且只提供了近似样品。 作为直接应用，我们将其用于从多项式时间中等级-1矩阵推断问题的后验分布进行样本。
We give a algorithm for exact sampling from the Bingham distribution $p(x)\propto \exp(x^\top A x)$ on the sphere $\mathcal S^{d-1}$ with expected runtime of $\operatorname{poly}(d, λ_{\max}(A)-λ_{\min}(A))$. The algorithm is based on rejection sampling, where the proposal distribution is a polynomial approximation of the pdf, and can be sampled from by explicitly evaluating integrals of polynomials over the sphere. Our algorithm gives exact samples, assuming exact computation of an inverse function of a polynomial. This is in contrast with Markov Chain Monte Carlo algorithms, which are not known to enjoy rapid mixing on this problem, and only give approximate samples. As a direct application, we use this to sample from the posterior distribution of a rank-1 matrix inference problem in polynomial time.
