[ https://issues.apache.org/jira/browse/MATH-931?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Owen updated MATH-931: --------------------------- Attachment: MATH-931.patch > 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