Math @ Duke

Publications [#361598] of Holden Lee
Papers Published
 Ge, R; Lee, H; Lu, J; Risteski, A, Efficient sampling from the Bingham distribution
(September, 2020)
(last updated on 2022/05/22)
Abstract: We give a algorithm for exact sampling from the Bingham distribution
$p(x)\propto \exp(x^\top A x)$ on the sphere $\mathcal S^{d1}$ with expected
runtime of $\operatorname{poly}(d, \lambda_{\max}(A)\lambda_{\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 rank1 matrix inference problem in polynomial time.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

