Uploaded image for project: 'Commons Math'
  1. Commons Math
  2. MATH-931

Speed up UnitSphereRandomVectorGenerator for high dimensions

Rank to TopRank to BottomVotersWatch issueWatchersConvert to sub-taskLinkCloneUpdate Comment AuthorReplace String in CommentUpdate Comment VisibilityDelete Comments
    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Minor
    • Resolution: Fixed
    • Affects Version/s: 3.1.1
    • Fix Version/s: 3.2
    • Labels:
      None

      Description

      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.

        Attachments

          Activity

          $i18n.getText('security.level.explanation', $currentSelection) Viewable by All Users
          Cancel

            People

            • Assignee:
              Unassigned
              Reporter:
              srowen Sean R. Owen

              Dates

              • Created:
                Updated:
                Resolved:

                Issue deployment