[jira] [Commented] (MATH-931) Speed up UnitSphereRandomVectorGenerator for high dimensions

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-931) Speed up UnitSphereRandomVectorGenerator for high dimensions

ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/MATH-931?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13567097#comment-13567097 ]

Sean Owen commented on MATH-931:
--------------------------------

You can omit that test, of the two. The original motivation here was that the method could take minutes or hours to run when dimensions got to high tens. That just asserted that it ran in 10 seconds -- should be like a nanosecond now.
               

> Speed up UnitSphereRandomVectorGenerator for high dimensions
> ------------------------------------------------------------
>
>                 Key: MATH-931
>                 URL: https://issues.apache.org/jira/browse/MATH-931
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.1.1
>            Reporter: Sean Owen
>            Priority: Minor
>         Attachments: MATH-931.patch
>
>
> 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 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