On Wed, Jan 30, 2013 at 12:54 PM, Sean Owen <[email protected]> wrote:
> Hello all, I have a small proposal to improve the speed of > UnitSphereRandomVectorGenerator. This class picks a random point on > the unit n-sphere -- a unit vector, chosen uniformly from all possible > directions. > > It does so using a rejection process -- generates a random point in > the unit n-cube (well, with side lengths 2) and rejects any points > outside the unit n-sphere, then normalizes the length. This is correct > and works well at low dimension. However the volume of the unit > n-sphere compared to the unit n-cube drops exponentially. This method > eventually takes an extraordinary amount of time when dimensions get > past about 20, since virtually no samples are usable. > > For example, here is the time taken to make pick 10 points as a > function of dimension up to 20: > > 1 : 11 > 2 : 1 > 3 : 0 > 4 : 1 > 5 : 0 > 6 : 1 > 7 : 1 > 8 : 17 > 9 : 4 > 10 : 3 > 11 : 13 > 12 : 32 > 13 : 15 > 14 : 41 > 15 : 220 > 16 : 897 > 17 : 1770 > 18 : 7426 > 19 : 48457 > 20 : 122647 > ... > > It's equally correct, and much faster, to generate these points by > picking n standard Gaussians and normalizing. This method takes > negligible time even into thousands of dimensions. > > Is this non-trivial enough that I might propose a patch? I wanted to > ask users first. > Hi Sean, any patch / request for improvement is welcome! Please create a new issue on JIRA for this. Thanks, Thomas
