Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to sample subspaces uniformly

  1. Sep 15, 2013 #1
    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.
     
  2. jcsd
  3. Sep 15, 2013 #2
    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.]
     
  4. Sep 15, 2013 #3
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook