algorithm for generating uniformly distributed random points on the N-sphere

1
votes

I have not found an implementation of such an algorithm on Python

Something like this:

There are two input arguments:

  • n - dimension of space.
  • m - number of points on the n-1 sphere.

I need to approximately evenly arrange them on the surface of the n-sphere.

Coordinate axes are located in the center of n-1 sphere. For example in 3d on a regular sphere it's possible to position the points like this

In my opinion, the Fibonacci algorithm is very good visually. I don't know if there is something similar for n-sphere. I have 512D space and I'm going to place 1000 or even 10,000 points in it.

How to do this in python?

2
pythonmath
(1) Generate n d-tuples of samples from a mean 0, variance 1 Gaussian distribution, and normalize each d-tuple to length 1. Then your n d-tuples are approximately uniformly distribution on the surface of the (d - 1)-sphere. (By d, I assume you mean the embedding dimension of the sphere and not the dimension of the sphere itself. E.g. a 2-sphere is something locally 2 dimensional, which lives in a 3 dimensional space.) This approach is the same as what's posted below by another respondent, but I think it's clearer to explain it this way. – Robert Dodier
(2) Stratified sampling: divide the sphere into a number of pieces of equal area and sample from each piece. You mention that you have n which is not too much larger than d, which means that purely random sampling is going to leave a lot of gaps. My guess is that stratified sampling, or another method which samples more evenly, is going to work better on this problem. As to other methods for more even sampling, maybe you can find something about low-discrepancy sequences (a.k.a. quasirandom numbers) on the sphere. – Robert Dodier
It is the same as hypersphere. From you link: An n-sphere embedded in an (n + 1)-dimensional Euclidean space is called a hypersphere. You only need to avoid off-by-one errors. (2-sphere is surface in 3d- space etc) – MBo
I woulkd start with reversing and porting to ND of this: Procedural generation of stars with skybox so simply n times generate pseudo random ND vector v with coordinates in range <-1,+1> and then change the length of vector to r by v = v*r/|v|. There is also a very good duplicate for this in here (not sure how old but at least a year or two) but can not find it now (about generating pseudorandom hyperspheres with normal distribution of points) – Spektre
OP, another approach is to generate a non-uniform distribution and then weight the points differently (namely, giving more weight to points in the less-dense regions). Whether that's a workable approach depends on what you're trying to do. Maybe you can say more about your larger goal here. – Robert Dodier

2 Answers

2
votes

There is simple Muller and Marsaglia approach to generate uniform distribution on the surface of the hypersphere.

Generate n variables with gaussian distribution (list l here). They form some vector.

Find length of that vector and normalize its components to provide unit length result

Example shows generation of one point on sphere in 10d space and also visually checks uniformity for pack of points at the circle (sphere in 2d, hystogram values should be close)

import random, math

#muller-marsaglia method
def spherepicking(n):
    while True:           #to get rid off [0,0,0,0] case
        l = [random.gauss(0, 1) for i in range(n)]
        sumsq = sum([x * x for x in l])
        if sumsq > 0:
            break
    norm = 1.0 / math.sqrt(sumsq)
    pt = [x * norm for x in l]
    return pt

print(spherepicking(10))

cnt = [0] * 18
for i in range(10000):
   pt = spherepicking(2)
   an = math.atan2(pt[1], pt[0]) + math.pi / 2
   cnt[math.floor(an * 9 / math.pi)] += 1
print(cnt)

-0.31811419572739935, 0.2845442135156396, -0.2849019746359018,
-0.1326796017012003, 0.7388447238721524, -0.287062305232526, 
-0.08794741714783766, 0.131707880836534, 0.22059937624019868, 
-0.13047162618106062]

[554, 560, 529, 589, 534, 538, 550, 558, 578, 556, 522, 553, 561, 513, 592, 583, 593, 537]
1
votes

Using the same argument as MBo: (Muller 1959, Marsaglia 1972) -[https://mathworld.wolfram.com/HyperspherePointPicking.html] I present my implementation in python using numpy:

import numpy as np

def getRandomSamplesOnNSphere(N , R , numberOfSamples):
    # Return 'numberOfSamples' samples of vectors of dimension N 
    # with an uniform distribution on the (N-1)-Sphere surface of radius R.
    # RATIONALE: https://mathworld.wolfram.com/HyperspherePointPicking.html
    
    X = np.random.default_rng().normal(size=(numberOfSamples , N))

    return R / np.sqrt(np.sum(X**2, 1, keepdims=True)) * X

On the surface And if you need to generate points inside an N-Sphere you can do this (reference: https://math.stackexchange.com/q/87238)

import numpy as np

def getRandomSamplesInNSphere(N , R , numberOfSamples):
    # Return 'numberOfSamples' samples of vectors of dimension N 
    # with an uniform distribution inside the N-Sphere of radius R.
    # RATIONALE: https://math.stackexchange.com/q/87238
    
    randomnessGenerator = np.random.default_rng()
    
    X = randomnessGenerator.normal(size=(numberOfSamples , N))
    U = randomnessGenerator.random((numberOfSamples , 1)) 
    
    return R * U**(1/N) / np.sqrt(np.sum(X**2, 1, keepdims=True)) * X

Inside the circle of radius 1