The background of this question is how a random variable $X$ on the orthogonal group $O(n)$ whose distribution is the normalized Haar measure $\mu$, i.e., $\mu( O(n) ) = 1$, can be realized on a computer that has access to a number of "simpler" random variables, like:

  • a perfect coin
  • the uniform probability measure on $[0,1]$ or $S^1$
  • Gaussian variables on $\mathbb R$ with arbitrary standard deviation.

An algorithm needs to use the random variable $X$, but I am not aware of an explicit formula that would allow for such a reduction.

  • 2
    $\begingroup$ Pick a first unitary vector $v_1$ at random by renormalising a standard Gaussian random variable in $\mathbb{R}^n$. Generate a second vector $v_2$ by generating a standard Gaussian vector, project it onto $v_1^{\perp}$ and renormalize it. Generate a third vector $v_3$ by generating a standard Gaussian vector, project it onto $\text{span}(v_1,v_2)^{\perp}$ and renormalize, etc... The vectors $v_1, \ldots, v_n$ are the column of the matrix you are looking for. $\endgroup$ – Alekk Jun 12 '13 at 7:30
  • 1
    $\begingroup$ @Alekk: Gram-Schmidt is a numerically unstable algorithm for producing a QR decomposition. It is better to used a canned QR decomposition routine from a numerical library. $\endgroup$ – Yoav Kallus Jun 12 '13 at 18:03

Starting from a real $N\times N$ matrix and essentially performing a $QR$ decomposition, then if the initial real matrix elements are independent identically distributed Gaussian, then the matrices $Q$ will be Haar-distributed on $O(N)$. Please see the full construction in the following article by: Francesco Mezzadri


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.