# How to sample points in hyperbolic space?

Hyperbolic space in the Poincaré upper half space model looks like ordinary $$\Bbb R^n$$ but with the notion of angle and distance distorted in a relatively simple way. In Euclidean space I can sample a random point uniformly in a ball in several ways, e.g. by generating $$n$$ independent Gaussian samples to obtain a direction, and separately sample a radial coordinate $$r$$ by uniformly sampling $$s$$ from $$\left[0, \frac1{n+1}R^{n+1}\right]$$, where $$R$$ is the radius, and setting $$r = \left((n+1)s\right)^{\frac1{n+1}}$$. In the hyperbolic upper half plane a sphere happens to still be a sphere, only its centre will not be the centre in the Euclidean metric, so we could do the same.

If we want to sample according to a non-uniform distribution, but still in an isotropic way, e.g. a Gaussian distribution, this doesn't seem so easy. In Euclidean space we could just generate a Gaussian sample for each coordinate (this only works for the Gaussian distribution), or equivalently generate a multidimensional Gaussian sample. Is there a direct way to convert this sample to a sample in hyperbolic space?

An alternative approach could be to first generate a direction uniformly distributed direction (e.g. from $$n$$ Gaussian samples) then a Gaussian sample for the radial component, and finally generate the image under the exponential map in the specified direction for the specified length. A variation would be to just take the Euclidean Gaussian sample and map it under the exponential map.

My questions:

• what would be a good and efficient way to obtain a Gaussian sample with given mean and standard deviation in hyperbolic space?
• do the ways I describe above provide the desired sampling?
• did anyone work out the formula's already?
• how does this generalize to other metrics and other probability distributions?

EDIT

I just realized that even in the case of uniform sampling these questions remain; even though a sphere is a sphere, a uniform distribution would not be described by a constant function on a ball.

• @yes thanks for your comment. On every topological space you have the Borel sigma algebra, generated by the topology. A Riemannian metric gives you a notion of a volume. If the total volume is finite, this can be normalized to give a probability distribution, or more generally it gives you in a direct way uniform probability distributions on measurable sets of finite volume. Since you have a geometrical structure, including the notion of geodesics and arc lengths, you could also define Gaussian distributions by a probability density that decays by distance in the same way as in euclidean space – doetoe May 20 '15 at 6:27
• @yes It may be easier to sample around the centre of the ball in the ball model and then transport it through an isometry, at least Euclidean and hyperbolic rotations around the centre coincide. If this is indeed the most efficient, the question would reduce to how to sampling around the centre in the disk model according to the normal distribution for the hyperbolic metric. – doetoe May 20 '15 at 7:45
• You should be able to adapt Mark Girolami's Riemannian manifold MCMC to generate samples here. But it may be overkill. You do MCMC, but you generate proposals by shooting geodesics out from the current point. – Nick Alger Mar 7 at 19:52
• @NickAlger that sounds interesting, do you have a link? – doetoe Mar 7 at 20:05
• Here's his main paper about it. They transform the problem of sampling a nonuniform distribution on flat space into a problem of sampling a uniform distribution on a manifold, whereas you start with a uniform distribution on the manifold. rss.onlinelibrary.wiley.com/doi/full/10.1111/… – Nick Alger Mar 7 at 20:12

I'm in the middle of doing this for myself. I think the most appropriate analogue to the Gaussian would be the heat kernel in hyperbolic space. Fortunately, this has been figured out before: https://www.math.uni-bielefeld.de/~grigor/nog.pdf (also available in a Bulletin of the London Mathematical Society).

If you use the standard decay ($$e^{-dist^2/constant}$$), I expect that the total mass will be larger than 1, due to an exponential increase in volume with radius for hyperbolic space.

To sample uniformly on a given ball (or other compact set), one could do rejection sampling with the volume form: $$\left(\frac{2}{1-||x||^2} \right)^n \, dx_1 \, \ldots \, dx_n$$

Here's a uniform sample for the ball of radius 3 centered at the origin:

If desired, I'd be glad to say more. I just thought I'd put this up, since there was clearly some interest in this, at least in the past.

• Thank! I didn't have time yet to study the liked article, but it looks interesting and relevant – doetoe Mar 7 at 20:01
• The relevant equations are (1.6) and (1.7), for odd and even dimensions, respectively. The standard Euclidean Gaussian is the result of diffusing a delta distribution at the mean for time $\sigma / 2$. These distributions are the result of doing the same in hyperbolic space. The heat equation governs this evolution and preserves mass. This also answers your question of how to generalize this to other Riemannian manifolds. Finding an explicit formula in these other instances is probably not likely, unfortunately. – xue2sheng1 Mar 7 at 21:32

The constant pi is only a constant in Euclidean space. The value of pi is different in other geometries. The parameter pi changes the probability mass under the Gaussian. The parameter pi is used to normalize the probabilities. I'm just starting to study this.

I concluded some time ago that the space changes from hyperbolic to Euclidean to spherical as the number of sigmas go up. I was happy to run across a discussion of circles in each space and pi as a function of Lp spaces via the parameter p.

Accept-Reject (AR) sampling is probably the way to go here. AR sampling works in $$n$$ dimensional spaces just like it does in 1 dimensional space (e.g. sampling from a Gaussian via a Laplace/Double exponential) you define an envelope function and then sample uniformly under the envelope. Here the envelope function would need to be a function covering the Poincare space. The closer the envelope is to the actual space the more efficient the sampling process. A key point here though is that in order to sample from the Poincare disk space you need to actually define a probability measure over the space. It isn't clear to me what a Gaussian measure on the Poincare disk means.