3

How can I iterate over all possible vectors of d dimensions with specified length (e.g. unit length), where delta is the step-size.

Note that delta can by quite small, such as 1e-3 for a unit vector. d is commonly in the range of [0,5] but this is not a hard restriction!.

The dumb approach would be to use a list of delta*i for i in [0,N) and generate all possible combos like in n choose n and select those which sum up to 1. But this seems to be quite inefficient and I am sure there are better approaches which I am not aware of.

The picks should be at least close to uniformly distributed over the surface.

drahnr
  • 6,782
  • 5
  • 48
  • 75
  • 1
    http://en.wikipedia.org/wiki/N-sphere#Spherical_coordinates – sbabbi Jan 12 '15 at 00:28
  • As I said, `delta` is the smallest change of one dimension that is allowed. That rasterizes the problem and goes from uncountable many to a restricted range. – drahnr Jan 12 '15 at 00:30
  • In 2D, you can just generate a set of angles, from which you can calculate the vector components. In 3D (spherical coordinates), you need 2 angles. I'm sure this generalizes to the D-dimensional case. Edit: see @sbabbi above – JorenHeit Jan 12 '15 at 00:31
  • why don't you just use a N-dimensional spherical coordinates parametrization, then discretize each independent coordinate? The number of possible solutions scales as K^N, where K is the number of steps in a 1-D discretization, and N is the number of dimensions. That is, there are quite a lot of such vectors :) – vsoftco Jan 12 '15 at 00:32
  • 1
    If `delta` is the smallest allowable change along **one dimension**, then you will get unusual concentrations of samples. It will not be close to an even distribution. Is that what you want? *(Put another way, Cartesian coordinates do not map smoothly to a spheroid surface)* – Drew Dormann Jan 12 '15 at 00:36
  • @DrewDormann Having a uniform distribution is a different ball game, a bit more complicated, but see http://mathworld.wolfram.com/SpherePointPicking.html for some hints. And I guess the whole business depends on how you parametrize the manifold. If you use cartesian coordinates, then of course you get far from uniform distributions. – vsoftco Jan 12 '15 at 00:39
  • Uniform distribution over the surface would be preferable. The difficulty is not to implement it for 1,2,3 or 4 dimensions but to make it generic for `d`-dimensions. – drahnr Jan 12 '15 at 00:43
  • @drahnr then generate each component of the vector using a random normal distribution, then normalize it. In MATLAB code (just to illustrate the point): `v = randn(1,3); v = v/norm(v)` assures you that `v` is distributed uniformly on the surface of a unit 3-D ball. So the cartesian coordinates have to be normally distributed. See e.g. http://stackoverflow.com/a/9751925/3093378 Now I am not sure what exactly `delta` is? Is it the difference between 2 such vectors? – vsoftco Jan 12 '15 at 00:45
  • 1
    @drahnr I have to say that the problem doesn't seem so trivial, and I guess it is not at all related to C++, but to math and combinatorics. You should try posting it on mathoverflow also. One thing you may want to check: http://mathoverflow.net/questions/24688/efficiently-sampling-points-uniformly-from-the-surface-of-an-n-sphere – vsoftco Jan 12 '15 at 00:53
  • You should start out by defining "length". 1-norm and infinity-norm have simple solutions, 2-norm is likely very interesting. – Ben Voigt Jan 12 '15 at 03:27
  • This question appears to be off-topic because it is about geometry and combinatorics in general and not a specific programming language or a specific programming question. – vsoftco Jan 12 '15 at 03:57
  • Eh no, it is perfectly on topic. All I need is homegenous spacing of smaple points (like equal distance, not statistically evenly distributed points) on an _n-dimensional_ sphere. My issue here is implementing it for n dimensions. Sure the transformation into r space does work but is not easy for `n>4` and the general case – drahnr Jan 12 '15 at 07:58

1 Answers1

1

Ok, I think I figured out what you need. Basically, if you choose 

X=(X1, X2, ..., Xn)/norm(X)

where X1, X2,..., Xn are normally distributed N(0,1) (mean 0 and standard deviation 1) and norm(X) is the L2 (Euclidian) norm of X, then it is guaranteed that the vector X is uniformly distributed across the surface of the n-dimensional unit sphere.

Now, since you want to discretize, just draw each Xi from a binomial distribution (which at the limit we know it becomes a Poisson distribution, which, via the Central Limit theorem, converges to a Gaussian distribution, see http://www.roe.ac.uk/japwww/teaching/astrostats/astrostats2012_part2.pdf ), and you're done. Of course, you'll get an exponential scaling in the dimension n, but I don't think there is any other way, as the number of such vectors scale exponentially with the dimension.

vsoftco
  • 55,410
  • 12
  • 139
  • 252
  • That is a clever use of the gaussian distribution. – sbabbi Jan 12 '15 at 01:45
  • @sbabbi, I wish the first part was my original idea :) – vsoftco Jan 12 '15 at 02:00
  • discrete Xi aren't helpful, since you need Xi/norm(X) to lie on the lattice – Ben Voigt Jan 12 '15 at 03:28
  • @BenVoigt yes, that's true... seems a bit more complicated than I though, at least more complicated than a Sunday night problem :) One idea is to pick components from `N(0,1)` subjected to a restriction that their norm lies within `epsilon` from the surface (if you want strict equality you get into diophantine equations which are a pain in the neck). But again, I'd love to see a proper rigorous answer to the question, I just gave the physicist's proof :)) And I hope OP posts it on mathoverflow, since that is the site it belongs to, as it has not too much to do with C++ – vsoftco Jan 12 '15 at 03:33
  • But that does not guarantee a spacing of delta, so I not only need homegenous distribution, but also equal distances between the sample vectors. Sorry if misguided you here. – drahnr Jan 12 '15 at 07:41