How to generate a net on a 8-dimensional sphere

Question

Using Matlab, how to generate a net of 3^10 points that are evenly located (or distributed) on the 8-dimensional unit sphere?

Thanks for any helpful answers!

Answer 1

If it's really important for the points to be evenly distributed, and you don't mind doing a lot of calculation to get them that way, you can start with a randomly distributed set and then iterate over the entire set repeatedly, allowing each point in turn to make whatever small adjustment improves your chosen definition of uniformity, and repeat this until the set of points converges. If you're even pickier than that, and not satisfied by just a locally optimal arrangement, the canonical next thing to try is simulated annealing.

For picking points at random, I agree with Peter Shor that taking the time to implement a one-to-one volume-preserving map from a product of intervals to a high-dimensional sphere would be much more wasteful (of time; you would learn a lot) than throwing away 98% of your random numbers. It's an interesting question, though, whether systematically chosen points in a product of intervals can be well-distributed under one of these volume-preserving (but distance-destroying) maps. The first interesting case of such a map is the axial projection from the curved surface of a cylinder of height 2 and radius 1 to the surface of the unit sphere it contains: projecting straight to the axis, one direction gets stretched out in exact counterbalance to the compression of the other direction. Call the coordinates of the cylinder surface z ∈ [$-1$, $1$] and θ ∈ [$0$, $2\pi$]. Choosing an ordinary regular rectangular grid in z and θ does terrible things to the projection. On the other hand, for any $N$, setting z_i = $(-N+2 i - 1)$/$N$ and θ_i = $2\pi (\phi i$ mod $1$), where $\phi$ is the golden mean, actually gives a very nice distribution of points after projection. It's possible that in any dimension there is such a lattice in the cube that projects nicely, for any N, to the sphere.

Answer 2

If you're looking for points on the 8-dimensional sphere, another thing you could do is go to Neil Sloane's table of spherical codes, scroll down until you get to dimension 8, and obtain a sphere covering which has 2160 points fairly evenly distributed (obtained from second shell of vectors in the E8 lattice). Now, if you apply $3^{10}/2160 \approx 27$ random orthogonal matrices to this set, you'll get a set of points distributed on the 8-dimensional sphere which is presumably somewhat more uniform than a set of random points. Since I don't know why you want these vectors, I don't know how much an improvement this is over random points, and whether it's worth all the extra work.

You can get random orthogonal transformations by starting with an $8 \times 8$ matrix with random Gaussian entries. First, normalize the top row to make it a length 1 vector. Next, subtract a multiple of the top row from the second row to make it perpendicular to the top row, and then normalize to make the second row a length 1 vector, and so on.

Answer 3

In case the goal is to draw points inside the sphere, the discussion Intuitive proof that the first (n-2) coordinates on a sphere are uniform in a ball seems relevant.

In other words, one simply draws random points on the 10-dimensional sphere (by drawing a normal vector and normalizing it) and discards the last two coordinates.

Answer 4

Forgetting Matlab, the 'best' way to...hold on, do you mean -in- the sphere or -on- the sphere?

For -in- the sphere, create 8-tuples where each element is from the uniform distribution from 0 to 1. Ignore those tuples whose Euclidean norm $\sqrt{\sum x_i^2} $ is greater than 1. Do this until you have $3^{10}$ points. This is a uniform distribution over the sphere.

For -on- the sphere, create 8-tuples as before, but then divide each point by the norm (of course throw out $\langle 0,0,0,0,0,0,0,0\rangle$ ). This will place a point on the surface. Do this $3^{10}$ times. This is not an exact uniform distribution but is a very good approximation to one, and is very easy to do.

Answer 5

In general, for generating extra-regular but not-too-regular distributions of points (in a technical sense, "low discrepancy", meaning that the variance in the length of gaps between points is smaller than a uniform distribution), you can use a class of methods called quasi monte carlo methods. There are libraries in MATLAB.

http://en.wikipedia.org/wiki/Quasi-Monte_Carlo_method

http://www.mathworks.com/matlabcentral/fileexchange/17457-quasi-montecarlo-halton-sequence-generator

Though if you want a totally uniform set of points, these won't help you.

Answer 6

Shells of evenly spaced lattice points:

To generate evenly spaced sets of non-random points on an n-sphere, start with the permutations of { 0 1 1 ... 2 2 ... }, then make 2^n flips of that. For example, in 4-space start with the 12 permutations of { 0 1 1 2 }. Each point is √6 from the origin, and each has 4 neighbours √2 away (+1 here, -1 there):

0 1 1 2

0 1 2 1
0 2 1 1
1 0 1 2
1 1 0 2

Make 2^4 sign-flipped copies of this, i.e. multiply by { 1 1 1 1 } .. { -1 -1 -1 -1 } except where there's a 0. This gives a shell of 96 points, 0 1 1 2 .. 0 -1 -1 -2. Each is √6 from the origin, and each now has 6 neighbours √2 away.

For the 8-sphere, start with the 280 permutations of { 0 1 1 1 1 2 2 2 }. Each has of course the same distance from the origin, and each has 12 neighbours √2 away — a nice, regular graph. The shell of 280 * 2^7 = 35840 sign-flipped points is not quite 3^10, but.

(I'd appreciate links to papers or programs on such graphs.)

Answer 7

Talking out of my depth so I am not sure this work, but here is a start of an idea... Say you were finding points uniformly on $S^3$, couldn't you use Hopf fibration? The idea is you select Hopf fiber uniformly from $S^2$ then it is easy to populate points uniformly on the Hopf fiber, which is a circle in this case. Unfortunately, there is no such relation for $S^8$.

Instead one could potentially use the following

$S^1\hookrightarrow S^3 \rightarrow S^2$

and then

$S^3\hookrightarrow S^7 \rightarrow S^4$

but then one needs to construct uniformly spaced points on $S^4$ from uniformly spaced points in $S^3$ and same for $S^8$ and $S^7$, which doesn't seem that hard.