|
| Publications [#361589] of Jianfeng Lu
Papers Published
- Ge, R; Lee, H; Lu, J; Risteski, A, Efficient sampling from the Bingham distribution,
Algorithmic Learning Theory. PMLR, 2021
(September, 2020)
(last updated on 2026/01/15)
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^{d-1}$ 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 rank-1 matrix inference problem in polynomial time.
|
