How to sample subspaces uniformly

[wdlang]

i need to sample the N-dimensional subspaces of a M-dimensional linear space over C uniformly.

That is, all subspaces are sampled with equal probability

how should i do it?

would this work? First generate a M*N matrix, the real and imaginary parts of each element is sampled from the normal distribution. Then by using QR decomposition, i can get N orthonormal vectors, which span a N-dimensional subspace. Take it.

 

[economicsnerd]

Are you looking for something reasonably "uniform" that you can put into a computer, or are you looking for a distribution that feels somehow natural?

If the former, I have no idea, and other people may have better ideas.

If the latter, there must be a natural choice, given a fixed basis for the big space. Say we're looking at a random $N$-dimensional subspace of $\mathbb C^M$ (the latter with its standard basis). Let $\mathcal U(M)$ denote the space of unitary $M\times M$ matrices. There's a very natural probability measure on $\mathcal U(M)$, called the Haar measure $\mu$. I would think of a "uniformly chosen $N$-dimensional subspace" as picking a random $U\in \mathcal U(M)$ via $\mu$ and then picking the span of the first $N$ columns of $U$.

*[It has the property that for any collection $\mathcal S \subseteq \mathcal U(M)$ of matrices with defined probability, and any matrix $U\in \mathcal U(M)$, we have $\mu(U\mathcal S)= \mu(\mathcal S)$. Moreover, $\mu$ is unique in satisfying this property.]

 

[wdlang]

Are you looking for something reasonably "uniform" that you can put into a computer, or are you looking for a distribution that feels somehow natural?

If the former, I have no idea, and other people may have better ideas.

If the latter, there must be a natural choice, given a fixed basis for the big space. Say we're looking at a random $N$-dimensional subspace of $\mathbb C^M$ (the latter with its standard basis). Let $\mathcal U(M)$ denote the space of unitary $M\times M$ matrices. There's a very natural probability measure on $\mathcal U(M)$, called the Haar measure $\mu$. I would think of a "uniformly chosen $N$-dimensional subspace" as picking a random $U\in \mathcal U(M)$ via $\mu$ and then picking the span of the first $N$ columns of $U$.

*[It has the property that for any collection $\mathcal S \subseteq \mathcal U(M)$ of matrices with defined probability, and any matrix $U\in \mathcal U(M)$, we have $\mu(U\mathcal S)= \mu(\mathcal S)$. Moreover, $\mu$ is unique in satisfying this property.]

i am actually looking for a numerical method.

my idea is the following. First generate a M*N matrix, the real and imaginary parts of each element of which are drawn independently from the normal distribution. Then do QR decomposition to get the N orthonormal basis vectors spanning the subspace.

i am not sure whether this is the right algorithm.