commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Luc Maisonobe (JIRA)" <j...@apache.org>
Subject [jira] [Closed] (MATH-931) Speed up UnitSphereRandomVectorGenerator for high dimensions
Date Sun, 07 Apr 2013 09:19:21 GMT

     [ https://issues.apache.org/jira/browse/MATH-931?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Luc Maisonobe closed MATH-931.
------------------------------


Closing issue as version 3.2 has been released on 2013-04-06.
                
> 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
>             Fix For: 3.2
>
>         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

Mime
View raw message