padraic.xyz

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.

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

  1. Complement: Given , it's complement .
  2. 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

  1. Non-negative:
  2. Null for the empty set:
  3. 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 .

Useful Definitions

We define the followung groups and sets that will appear throughout these notes.

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.

Sampling and

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.