4

Suppose I have the following scenario:

enter image description here

And I am aware of an algorithm to draw uniformly from (in this case) the 2-sphere. Does this same algorithm readily extend to the situation where I randomly take a "cut/slice" (shown in red above) and what points uniformly over this circle?

Further, suppose now that I have a uniform random sampling algorithm over an arbitrary Riemannian manifold. Would the same principles necessarily apply?

Aksakal
  • 61,310
tisPrimeTime
  • 525
  • 4
  • 15
  • What principles are you referring to?? Indeed, this specific example involves one Riemannian manifold (the 2-sphere), but the disk itself is not. (It's a manifold-with-boundary and the two of them are embedded in a larger space.) – whuber Jun 10 '23 at 17:39
  • Oh ok let me clarify. Evidently the sphere is a Riemannian manifold so I am wondering if whatever is answered here can naturally extend to any Riemannian manifold. Where my question is as above. Stated again briefly here, "If I have the above 2-sphere, that has a method to uniformly sample over its surface (of which there are many). Can that method be easily extended to uniformly sample (or obtain uniform samples) over any given slice/disk taken from this 2-sphere". I hope that provides a little more clarification? – tisPrimeTime Jun 10 '23 at 17:44
  • There seems to be a contradiction here. The slice will be a circle, but you refer to it as a disk; and if the slice is a disk, then do you mean the 3-ball instead of the 2-sphere? – whuber Jun 10 '23 at 17:46
  • Yes you are correct, I misspoke. In my head I meant the 2-sphere, and the "circle". This is what I had in mind. But will the implications necessarily be different when considering 3-ball --> disk? As far as I envision the question is about uniform sampling over some $D$ dimensional Riemannian structure, and its implications for a $D-1$ dimensional structure (as it lies on the same geometry). – tisPrimeTime Jun 10 '23 at 18:04
  • It sounds like you might be asking how to obtain the conditional distribution on the submanifold. See https://stats.stackexchange.com/a/584907/919 for some explanation and warnings. The basic idea is to sample within a sufficiently small tubular neighborhood of the submanifold. This is found by moving a sufficiently small distance $\epsilon$ along all geodesics emanating from the submanifold in directions within its normal bundle. Any sample point falling within the tube is assigned to the origin of the (unique) such geodesic passing through it. – whuber Jun 10 '23 at 18:36
  • 1
    The sphere, btw, is special: it's easy to define a transformation from it to any circle that preserves uniformity of distribution (just make the common axis of the sphere and circle the origin of latitude, longitude coordinates: the map identifies the circle with the meridians). But such a transformation won't exist for an arbitrary manifold. – whuber Jun 10 '23 at 19:40
  • OK I see. If I may give a little more details, I am in particualr working with Stiefel manifolds of which the sphere is simplest representation of a "1-D" Stiefel manifold so I provided it for intuition sake. I guess implicitly asking that: "If there is a Haar measure defined specifically for $S^2$ (or $St(m,n)$), then I take a slice of that Riemannian structure (i.e. a submanifold), can one assume that the same Haar measure can be used by the submanifold for the purpose of uniform random sampling? --- I am not sure how far this deviates from my original question but that's what I had mind – tisPrimeTime Jun 11 '23 at 05:43
  • Because these manifolds aren't naturally groups (except in edge cases), by "Haar measure" I suppose you mean the uniform measure invariant under the group action. If the group acts transitively on your submanifold then you have a good analog of the sphere-circle example. Otherwise, the tubular neighborhood construction still applies. – whuber Jun 11 '23 at 15:33
  • Sorry could you clarify this part: "Because these manifolds aren't naturally groups (except in edge cases)" for some reason it doesn't quite click with me .... And you are completely correct wrt my intent of use of the "Haar measure" here. – tisPrimeTime Jun 12 '23 at 12:02
  • Haar measure, by definition, is a measure on a (topological) group. It doesn't apply to general manifolds. – whuber Jun 12 '23 at 14:00

3 Answers3

3

Let's restate the originally intended problem: we have a uniform sample of D-1 sphere. How to convert this into uniform sampling of D-2 sphere? For instance, if we have a sample on a surface of a sphere, how to convert it to a uniform sample on a circle?

The idea is to define that given circle on a sphere with the axis that goes from the center of the sphere through a center of a circle. This axis would be z-axis of spherical coordinate system, and make the given circle one of latitudes:

enter image description here.

Now, if you observe only the angle $\varphi$ (azimuth angle or longitude) of the uniformly random points on a sphere, this will give you a uniform sample of points on a circle, because a point on a circle can easily be located by that angle.

Now, for a general D-1 sphere, we have the same approach. We define a circle on the sphere by the z-axis. After that azimuth angle can be calculated easily by projecting the points on sphere to the hyperplane that is orthogonal to this z-axis. Then you calculate the cosine (azimuth angle) to any fixed vector on that hyperplane that gives through the center of the D-sphere.

A disk can be sampled from a ball in a similar way. The difference is that for a disk we need two spherical coordinates: an azimuth angle and the distance to the point from the center of a disk. We then re-scale the distance so that it corresponds to the distance on the given disk.

Examples for a circle

Here's an example. I sampled 100 points on a sphere, shown in blue, using Marsaglia's algorithm. Next, I converted the cartesian coordinates into spherical coordinates. Assuming that $x_1$ is my z-axis, I proceeded replacing $\varphi_1$ with a given angle $\pi/6$ that defines the circle. The resulting points are shown in black, and lie on a circle, as expected.

enter image description here

Here's an example in 4-dimensions. Since I can't plot 4 dimensional objects, only the projected points will be shown. So, I sampled from 3-sphere in 4 dimensions. Then proceeded applying the same algorithm to project the points onto a 2-sphere in 3 dimensions. The result is shown below. As you can see the sphere is, of course, smaller than the unit sphere, but the points are uniformly distributed on it.

enter image description here

Aksakal
  • 61,310
1

Is it possible to uniformly draw points over a D−2 sphere, given that one has an algorithm to draw over the D−1 sphere in D-dimensional space?

You can consider an n-sphere as a sum of (n-1)-spheres.. An n-sphere can be constructed by stacking scaled (n-1)-spheres.

n+1 ball as sum of n-balls

And you can turn around that process.

The n-sphere has n+1 coordinates and if you take n of the coordinates and scale them to get the appropriate length of the desired radius of the sphere, then you have the n coordinates of a n-1 sphere.

Further, suppose now that I have a uniform random sampling algorithm over an arbitrary Riemannian manifold. Would the same principles necessarily apply?

The case of spheres has a simple solution. But for other surfaces/spaces you will need to take another approach to get the slice (like rejection sampling and taking only points in a small range of distance to a plane). Also the slice will not have a uniform distribution.

E.g take a slice of carambola. If you trace that slice with a measuring tape and compute for each amount of length that you go around the amount of surface that you have, then there will be a difference, the points have more surface. The same is true when you cut a cucumber at an angle (and this you could model like cutting an ellipsoid at an angle).

So a D-2 dimensional hyperspace slice from a uniform distribution on a D-1 hyperspace may not itself have a uniform distribution. If your question is about "how to resolve this?" or "how to get a slice with a uniform distribution?" then you could apply the rejection sampling method that is an answer to the question How to sample uniformly from the surface of a hyper-ellipsoid (constant Mahalanobis distance)?

Sextus Empiricus
  • 77,915
0

$\newcommand{\v}{\boldsymbol v} \newcommand{\w}{\boldsymbol w}$

Given a unit vector $\v_1$ and a positive length $c<1$, you can sample the points $\v$ in $R^d$ with $\v\cdot \v=1$ and $\v\cdot v_1=c$ as follows:

  1. Choose vectors $\v_2,\dots \v_d$ which are mutually orthogonal and orthogonal to $\v_1$.

  2. Generate independent standard normals $z_2,\dots z_d$.

  3. Let $\w=\sum_{i=2}^d z_i \v_i/|\v_i|$.

  4. Let $$\v = c \v_1 + \sqrt{1-c^2}\frac{\w}{|\w|}$$

Now $\v$ has the right distribution. The key is that the joint distribution of $z$’s is proportional to $\exp(-\sum z_i^2/2)$, so any two possible $\v$’s at the same distance from $cv_1$ will be equally probable.

Matt F.
  • 4,726
  • The question isn't how to sample (that has been answered in several other threads here on CV): it concerns how to adapt a specific algorithm for obtaining that sample. – whuber Dec 23 '23 at 21:29