A Complexity Bound for the Kent-Ganeiber-Mardia Sampler for the Bingham Distribution

Abstract

The Bingham distribution is a family of antipodally symmetric distributions on the unit sphere, characterised by an exponential-of-quadratic change of measure with respect to the uniform distribution. Kent, Ganeiber and Mardia proposed a rejection sampler for generating samples from Bingham distributions using proposals from an angular central Gaussian (ACG) distribution. Their empirical results suggest that the least efficient regime is the high-concentration limit, where the acceptance probability is of order $d^{-1/2}$ in dimension $d$, implying a polynomial complexity guarantee. In this note, we verify this dimension-dependent prediction, establishing the uniform guarantee $\inf \{{\alpha }_D:D=D^{\top }\in {\mathbb{R}}^{d\times d}\}\ge c_{\star }/\sqrt{d}$, where $c_{\star }=0.759\dots$. A one-dimensional high-concentration limit demonstrates that the $d^{-1/2}$ rate is unimprovable and that even the constant $c_{\star }$ cannot be improved beyond $0.857\dots$. The proof relies on a novel interpretation of the acceptance probability and a comparison principle for weighted sums of chi-squared random variables, which may be of independent interest.

8 pages, no figures