# Uniform sampling on a Riemannian manifold via tangent space and exponential map

Given a Riemannian manifold $$(\mathcal{M}, \{g_x\}_{x \in \mathcal{M}})$$ and a fixed point $$x \in \mathcal{M}$$, does the following procedure yield uniform samples from $$\{y \in \mathcal{M} : d_\mathcal{M}(x, y) \le 1 \}$$?

1. Sample uniformly from $$\{u \in \mathcal{T}_x \mathcal{M} : \lVert u \rVert_x \le 1\}$$ (say we know how to do that)
2. $$y = \exp_x(u)$$

It seems to me that by change of variables the density over $$y$$ will be constant only if the determinant of the Jacobian of $$\exp_x(\cdot)$$ is constant. But I'm not sure if this argument is correct mainly because I don't know if the pushforward measure of the metric-induced measure on the set from step 1 via the exponential map is the same as the volume form induced on $$\mathcal{M}$$ by $$g_x$$.

(I'm a novice in both Riemannian geometry and measure theory, so I'm sorry if this is trivially true or false, or it doesn't make sense.)

• As a trivial example, suppose $\mathcal{M}$ is a round 2-sphere of circumference $2$, and $x$ is the north pole. Then it seems to me that your point $y$ lands in the northern hemisphere with probability only $1/4$, whereas if it were uniform it should be $1/2$. Commented Sep 9, 2019 at 13:54

As Nate Eldredge pointed out in his comment, your two-step procedure will not in general simulate (a random element of $$\mathcal M$$ with) the uniform density $$f=1/|B_x|$$ on $$B_x:=\{y\in\mathcal M\colon d_{\mathcal M}(y,x)\le1\}$$, where $$|B_x|$$ is the volume of $$B_x$$. However, this "two-step" density, say $$h$$, can be used to simulate $$f$$, using the so-called rejection sampling method, as follows.

Suppose that $$c\in[1,\infty)$$ is such that $$f(y)\le c\,h(y)\tag{1}$$ for all $$y\in B_x$$. Let $$Y$$ be a random element of $$B_x$$ with density $$h$$, and let $$U$$ be a random variable uniformly distributed in the interval $$[0,1]$$ and independent of $$Y$$. Then the random pair $$(Y,Uc\,h(Y))$$ will be uniformly distributed on the subgraph $$\{(y,t)\colon y\in B_x,0\le t\le c\,h(y)\}$$ of the function $$c\,h$$ on $$B_x$$.

Now simulate a value $$y$$ of $$Y$$ using your two-step procedure, and then independently simulate a value $$u$$ of $$U$$.

Next, if $$u\,c\,h(y)>f(y)$$, discard the simulated value $$y$$ of $$Y$$ (as well as the simulated value $$u$$ of $$U$$). Otherwise, i.e. if $$u\,c\,h(y)\le f(y)$$, accept the simulated value $$y$$ of $$Y$$ as the simulated value $$x$$ of a random element $$X$$ of $$B_x$$. Then the random pair $$(X,Uc\,h(X))$$ will be uniformly distributed on the subgraph $$\{(y,t)\colon y\in B_x,0\le t\le f(y)\}$$ of the function $$f$$ on $$B_x$$ and hence $$X$$ with have the desired density $$f$$.

The expected "waste" fraction due to the rejection of some realizations of $$Y$$ will then be $$\int_{B_x}(h(y)-f(y)/c)\,dy=1-1/c$$. So, if $$h$$ is not far from $$f$$, then we can take the bounding factor $$c$$ in (1) to be somewhat close to $$1$$, and then the expected "waste" fraction $$1-1/c$$ will be somewhat close to $$0$$.

• Thanks for the answer, Iosif! But how can I use rejection sampling given that $h(\cdot)$ is an implicit density? I don't have an expression for it, right? Commented Sep 9, 2019 at 18:33
• @Călin : To use this method, you will indeed have to have an expression for $h$, which I think can be computed by standard means in each particular case. The main difficulty here is to invert the map $\exp_x$, and you seem to be assuming, in the description of the 2nd step of your procedure, that this map is accessible. Then the inversion can be done at least numerically, in principle to any precision, I think. I also think something like this is unavoidable in order to reach your goal. Commented Sep 9, 2019 at 19:04
• You're right. Thanks! Commented Sep 9, 2019 at 19:12