0
$\begingroup$

Apologies if this is a trivial question. If that is the case I imagine I would benefit from someone explaining where my understanding is lacking.

I am having some trouble interpreting the (putatively optimal) spherical codes listed on the website of N. Sloane here.

For example, the first coordinate for the best known spherical code in dimension 5 for 40 points is listed here as

7.071067811865475700e-01
7.071067811865475700e-01
-2.531063763564293100e-21
2.856464746130754600e-21
8.243943086078260200e-21

This is supposed to lie on the 5-dimensional unit hypersphere, so its norm should be one.

If I test this with numpy:

a = np.array([7.071067811865475700e-01,
    7.071067811865475700e-01,
    -2.531063763564293100e-21,
    2.856464746130754600e-21,
    8.243943086078260200e-21])

I get that

np.linalg.norm(a) == 1.0

outputs True, which seems good. But then I find that

np.linalg(a[0:2]) == 1.0

also output True. So it seems that the other numbers are too small for numpy.

I have played around with e.g. using dtype=np.longdouble, but that seems to make the problem worse, as the norm is then calculated to be 1.0000000000000000683.

I assume the the issue is simply that we are dealing with finite precision arithmetic, so we cannot expect to obtain 'exactly' one. If that is the case, what computational method can be used to confirm that the linked configuration is, in fact, a good spherical code? Alternatively, I imagine pointing me at (or outlining!) the algorithm used to generate these spherical codes would probably also clear up my confusion - they do not appear to be listed on the website.

edit: I was going to delete this question, as it is insufficiently well-posed, but site policy discourages deleting questions that have received upvoted answers, so I will leave it here. A new, hopefully better formulated question, can be viewed here.

$\endgroup$
5
  • $\begingroup$ Indeed, double precision cannot accurately handle such a discrepancy in the components. You can try using arbitrary precision packages like mpmath for Python and compute the norm of your vector with that. $\endgroup$ – Laurent90 Apr 3 at 9:45
  • 2
    $\begingroup$ In the given accuracy, you can consider the e-21 numbers as essentially zero. That they are given in this form is a result of the optimization algorithm used to generate the list. You might want to test if the minimal distance for the rounded list has still the given maximal value. $\endgroup$ – Lutz Lehmann Apr 3 at 12:02
  • $\begingroup$ @Laurent90 I have done as you suggested. I set mpmath.mp.dps = 200 (200 digits of precision). mpmath.mp.norm(a) then gives 1.00000000000000006835...[more digits], which is still not one. $\endgroup$ – Martin C. Apr 3 at 15:00
  • $\begingroup$ @LutzLehmann thanks for the comment - what do you mean by 'the rounded list'? Also, if you know anything about the optimization algorithm used to generate the list, please share! $\endgroup$ – Martin C. Apr 3 at 15:03
  • $\begingroup$ No, I do not know the algorithm. Just from the results there appears to be some mechanism to generate as many zero entries as possible, at least in the first points. Then there is some iteration up to some numerical convergence and the result is just dumped in the list without cleaning it up (using something like x=(1+x)-1). If these subtle non-zero entries were essential, the other coordinates would have been (computed and) saved with more digits. $\endgroup$ – Lutz Lehmann Apr 3 at 15:58
4
$\begingroup$

If that is the case, what computational method can be used to confirm that the linked configuration is, in fact, a good spherical code?

You can't, with the given data. With only 16 significant digits available, you will never know if that quantity is exactly 1 or not. Or even if you were given Float128s, or numbers with 2000 significant digits, for that matter. If you want to know if the norm is exactly one, you'll need exact expressions for those numbers, and arithmetic operations that allow you to compute exact results from them (symbolic computation). This is not a problem that floating point arithmetic can solve.

$\endgroup$
4
  • $\begingroup$ Yes, I agree! But that doesn't help me figure out what computational method actually is appropriate to confirm that that a given code is, in fact, a valid spherical code :). $\endgroup$ – Martin C. Apr 3 at 15:06
  • 1
    $\begingroup$ That problem seems difficult to define. How do you confirm that $\sqrt{2}$ is exactly a solution of $x^2=2$? You can't. You just define it to be so, and compute numerical approximations to it. I have no idea what a spherical code is, but I suppose that something similar is going on. $\endgroup$ – Federico Poloni Apr 3 at 15:09
  • 1
    $\begingroup$ Ok. I think I need to ask a better defined question. Thank you for taking the time to answer. What would you recommend - editing this existing question or deleting it and asking a new one? $\endgroup$ – Martin C. Apr 3 at 15:32
  • 2
    $\begingroup$ @MartinC. I guess that you could ask a new question and start by defining what do you mean by "Spherical code". $\endgroup$ – nicoguaro Apr 3 at 23:15
2
$\begingroup$

The program solves the problem

Place n points on a sphere in d dimensions so as to maximize the minimal distance (or equivalently the minimal angle) between them.

As an aside, let's take $n = 3$ and $d = 2$. Then the solution is three points on a circle 120° apart. But that means we have coordinates $(0,0)$,$(cos(2\pi/3),sin(2\pi/3))$ and $(cos(2\pi/3),-sin(2\pi/3))$. That means that a perfect solution cannot be described in finite precision arithmetic, so no program could ever return it.

To test it, you want to make sure that the program returns points that are at least very very close to the intended solution. So if $x^*$ is the real solution and $x$ the solution returned by the program, you want to have that $||x^* - x|| \le \epsilon$, where $\epsilon$ represents some small tolerance, usually the machine precision.

In almost all applications, such a solution is good enough.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.