[ https://issues.apache.org/jira/browse/MATH931?page=com.atlassian.jira.plugin.system.issuetabpanels:alltabpanel
]
Gilles resolved MATH931.

Resolution: Fixed
Fix Version/s: 3.2
> Speed up UnitSphereRandomVectorGenerator for high dimensions
> 
>
> Key: MATH931
> URL: https://issues.apache.org/jira/browse/MATH931
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.1.1
> Reporter: Sean Owen
> Priority: Minor
> Fix For: 3.2
>
> Attachments: MATH931.patch
>
>
> I have a small proposal to improve the speed of UnitSphereRandomVectorGenerator. This
class picks a random point on the unit nsphere  a unit vector, chosen uniformly from all
possible directions.
> It does so using a rejection process  generates a random point in the unit ncube (well,
with side lengths 2) and rejects any points outside the unit nsphere, then normalizes the
length. This is correct and works well at low dimension. However the volume of the unit nsphere
compared to the unit ncube 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 in milliseconds 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.
> Patch coming.

This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
