Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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. –  Alekk Jun 12 '13 at 7:30
1  
@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. –  Yoav Kallus Jun 12 '13 at 18:03

1 Answer 1

up vote 10 down vote accepted

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

share|improve this answer
    
Your link appears to be broken... –  MTS Jun 11 '13 at 17:02
2  
this is arXiv link to Mezzadri's paper: arxiv.org/abs/math-ph/0609050 –  Carlo Beenakker Jun 11 '13 at 20:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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