Haar Measure and Random Sampling
The problem of sampling uniformly randomly from a set is related to the definition of the 'measure', a function over the set that is kind of analagous to mapping the elements to numbers along the real line. Here, we discuss the notion of a Haar measure on groups of matrices and define how to sample randomly according to this measure.
Side-note:This definition leans heaviliy on wikipedia but is sufficient for getting intuition as to what a measure is.
Consider a set . We can define a so called -algebra over as a collection of subsets that includes the empty set, is closed under complement, and is closed under countable unions and countable intersections. There are a few extra notions to define there
- Complement: Given , it's complement .
- Countable union/intersection: A union of a finite number of subsets
As an example, consider . It has a -algebra given by . We can see that the last subset is given by the union of the two-element subsets, and the null set is given by their intersection. We can also see that the complement of any set in is another subset.
Given a -algebra then, a measure is defined as a function from the subsets to the 'extended real number line'.This function must be
- Null for the empty set:
- Countably Additive: For all countable collections of disjoint subsets of pairwise disjont sets in , then .
A simple example of a measure is the counting measure, given by .
We define the followung groups and sets that will appear throughout these notes.
- , the orthogonal group
- , the special orthogonal group
- - the unitary group
- , the special unitary group
- , the general linear grop over
- , the unit sphere in with surface dimension .
We note that definitionally, the columns of an orthogonal matrix form an orthogonal basis in , and the same is true of both the columns and rows of a unitary matrix.
The Haar Measure
Consider a function defined on a group . We thus have that for any , the integral of over is invariant under a transform . Namely
Similarly, we can define a translational invariance on many other groups. For a good choice of measure on , then forall elements :
If our measure is non-zero such that such that where , then we say it is a Haar Measure. It is invaraint over all the cosets of a subgroup.
If in addition we set , then is clled a probability measure on the group . We can see this by noting that, given a probability distribution of ad defining , then the total probability of the subgroup S.
Uniform Random Sampling
We want to sample from certain groups such that the resulting distribution has the invariance properties of a Haar measure. In this section, we will go through a series of examples that culminate in a method for sampling Haar random unitary matrices.
The elements of and can be paramterised by a number , giving and
We can clearly sample uniformly from both spaces by sampling uniformly from the range of .
Sampling from and
The 2-sphere can be paramterised as a pair of angles, such that the coordinates in are given by where . Sampling uniformly over and is not sufficient as the area element of the surface is defined as . Thus, we instead sample and compute .
Alternatively, we can sample using a standard normal distribution, sampled independently for each coordinate. The resulting normalised vector is uniformly distributed on .
One clear advantage of this method is that it can be generalised to by taking independent samples of the normal distribution.
This can then be applied to sample from , where the elements are parameterised as
We can set , and defining a global phase , we can write for .
To sample meaningfully from this set, we need to know the expression for the volume element in . This is known to be We thus sample , and where we then compute .
We note that these unitaries can then be used to build up Givens rotations, a set of rotations which are equal to the identity matrix with elements replaced by a matrix. These Givens rotations can be put together in to an arbitrary matrix.