Sampling $Q$ uniformly where $Q^TQ=I$

(This is related to this question)

$Q \in \mathbb{R}^{n\times k}$ is a random matrix where $k<n$ and the columns of $Q$ are orthogonal (i.e. $Q^T Q = I$). To examine $E(QQ^T)$, I conducted monte carlo simulations (using matlab):

[Q R] = qr(randn(n,k),0);


In other words, I just sampled a $\mathbb{R}^{n\times k}$ matrix from a standard gaussian, then did QR decomposition on it and assumed $Q$ is uniformly distributed in the space where $Q^TQ=I$. Joriki's answer and my simulations aligned so I assume there's nothing majorly wrong with how I obtained samples.

I have two questions (in order of importance)

1. How does one prove that the $Q$ sampled as above is uniformly distributed in the space where $Q^TQ=I$?
2. Are there more efficient methods of sampling orthogonal $Q$?
• That works. When you do gram schmidt orthogonalization on the guassian you get uniform on orthogonal. This corresponds pretty directly to the first column being uniform on $S^n$. You just normalize the gaussian first column and it it uniform on the sphere, then the second should be uniform on vectors orthogonal to first, and conditonally on the first it has a normal distribution that makes the property pretty apparent.
– mike
Apr 29, 2012 at 19:34
• @mike I can see that it works and (now that I think of it) that the first column would be uniform on $S^n$. I am still unclear on how the rest of what you state is "pretty apparent". I appreciate the response but can you lay out a fleshed out proof without stating that it's apparent? (I tried doing a proof using gram-schmidt, but couldn't prove that the $k$-th orthonormal vector obtained is uniformly distributed assuming that the $(k-1)$-th vector is uniformly distributed in the orthogonal space.) Apr 29, 2012 at 21:43
• @mike I think it might be easier if you replied in an answer. Apr 30, 2012 at 0:58

The claim is that if you apply gram schmidt to the columns of a matrix whose entries are i.i.d normal the resulting distribution is Haar measure on orthogonal matrices. Gram-Schmidt gives you an orthogonal matrix so invariance of the distribution under orthogonals is the issue. It is true because the orthogonals preserve i.i.d normals and also all elements of the gram-schmidt procedure, i.e. inner products. Suppose you have a $2 \times 2$ matrix $X$ , the general case being the same, with columns $x_1, x_2$. Gram schmidt gives an orthogonal matrix with columns $\frac {x_1}{\Vert x_1 \Vert},\frac {x_2 - \langle x_1,x_2 \rangle \frac {x_1}{\Vert x_1 \Vert}}{\Vert \text {the numerator }\Vert }$. Call that $X_{GS}$. If O is an orthogonal matrix $OX$ has columns $Ox_1, Ox_2$, and when you apply gram schmidt to it you get $\frac {Ox_1}{\Vert Ox_1 \Vert},\frac {Ox_2 - \langle Ox_1,Ox_2 \rangle \frac {Ox_1}{\Vert x_1 \Vert}}{\Vert O\text {the numerator }\Vert }$. Using orthogonality of $O$ once this has the same distribution as $X_{GS}$ since $Ox_i$ are i.i.d. with the same distribution as $x_1,x_2$,and that determines the distribution, and using it again the matrix is equal to $\frac {Ox_1}{\Vert x_1 \Vert},\frac {Ox_2 - \langle x_1,x_2 \rangle \frac {Ox_1}{\Vert x_1 \Vert}}{\Vert \text {the numerator }\Vert }$ since norms and inner products are the same. The last expression is $OX_{GS}$, and this shows that the distribution of $X_{GS}$ is invariant under orthogonal matrices.
• Thanks. I can understand the second part of the argument of how $X_{GS}$ and $OX_{GS}$ would have the same density due to invariance under rotation. But you lost me on the first part. I have never heard of Haar measure before and googling it hasn't helped me at all. Apr 30, 2012 at 22:17