How to sample subspaces uniformly

  • Thread starter wdlang
  • Start date
  • #1
307
0
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.
 

Answers and Replies

  • #2
269
24
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 [itex]N[/itex]-dimensional subspace of [itex]\mathbb C^M[/itex] (the latter with its standard basis). Let [itex]\mathcal U(M)[/itex] denote the space of unitary [itex]M\times M[/itex] matrices. There's a very natural probability measure on [itex]\mathcal U(M)[/itex], called the Haar measure [itex]\mu[/itex]. I would think of a "uniformly chosen [itex]N[/itex]-dimensional subspace" as picking a random [itex]U\in \mathcal U(M)[/itex] via [itex]\mu[/itex] and then picking the span of the first [itex]N[/itex] columns of [itex]U[/itex].

*[It has the property that for any collection [itex]\mathcal S \subseteq \mathcal U(M)[/itex] of matrices with defined probability, and any matrix [itex]U\in \mathcal U(M)[/itex], we have [itex]\mu(U\mathcal S)= \mu(\mathcal S)[/itex]. Moreover, [itex]\mu[/itex] is unique in satisfying this property.]
 
  • Like
Likes 1 person
  • #3
307
0
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 [itex]N[/itex]-dimensional subspace of [itex]\mathbb C^M[/itex] (the latter with its standard basis). Let [itex]\mathcal U(M)[/itex] denote the space of unitary [itex]M\times M[/itex] matrices. There's a very natural probability measure on [itex]\mathcal U(M)[/itex], called the Haar measure [itex]\mu[/itex]. I would think of a "uniformly chosen [itex]N[/itex]-dimensional subspace" as picking a random [itex]U\in \mathcal U(M)[/itex] via [itex]\mu[/itex] and then picking the span of the first [itex]N[/itex] columns of [itex]U[/itex].

*[It has the property that for any collection [itex]\mathcal S \subseteq \mathcal U(M)[/itex] of matrices with defined probability, and any matrix [itex]U\in \mathcal U(M)[/itex], we have [itex]\mu(U\mathcal S)= \mu(\mathcal S)[/itex]. Moreover, [itex]\mu[/itex] 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.
 

Related Threads on How to sample subspaces uniformly

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
17
Views
910
Replies
25
Views
8K
Replies
3
Views
3K
Replies
8
Views
912
Replies
2
Views
398
  • Last Post
Replies
5
Views
694
Replies
2
Views
2K
Top