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.