# 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 $X$. We can define a so called $\sigma$-algebra over $X$ as a collection of subsets $\Sigma$ 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 $E\subseteq X$, it's complement $X\setminus E\equiv \{x\in X:x\notin E\}$.
2. Countable union/intersection: A union of a finite number of subsets

As an example, consider $X=\{a,b,c,d\}$. It has a $\sigma$-algebra given by $\Sigma=\{\emptyset, \{a,b\},\{c,d\},\{a,b,c,d\}\}$. 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 $X$ is another subset.

Given a $\sigma$-algebra then, a measure is defined as a function $\mu:\Sigma\rightarrow \left(\mathbb{R}\cup \{+\infty, -\infty\}\right)$ from the subsets to the 'extended real number line'.This function must be

1. Non-negative: $\forall E\in\Sigma, \mu(E)\geq 0$
2. Null for the empty set: $\mu(\emptyset)=0$
3. Countably Additive: For all countable collections of disjoint subsets $\{E\}_{i=1}^{\infty}$ of pairwise disjont sets in $\Sigma$, then $\mu\left(\cup_{k=1}^{\infty}E_{k}\right)=\sum_{k=1}^{i=\infty}\mu\left(E_{k}\right)$.

A simple example of a measure is the counting measure, given by $\mu(E)=|E|$.

### Useful Definitions

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

• $\text{O}(n)\equiv \{O\in\mathbb{R}^{n\times n}|O^{T}O=\mathbb{I}\}$, the orthogonal group
• $\text{SO}(n)\equiv \{O\in \text{O}(n)|\text{det}\left(O\right)=1$, the special orthogonal group
• $\text{U}(n)\equiv \{U\in\mathbb{C}^{n\times n}|U^{\dagger}U=\mathbb{I}\}$ - the unitary group
• $\text{SU}(n)\equiv \{U\in \text{U}(n)|\text{det}\left(U\right)=1$, the special unitary group
• $GL(n,\mathbb{C})\equiv\{M\in\mathbb{C}^{n\times n}|\text{det}(M)\neq 0\}$, the general linear grop over $\mathbb{C}$
• $\mathbb{S}^{n-1}\equiv\{\mathbf{x}\in\mathbb{R}^{n}|\sum_{i=1}^{n}x_{i}^{2}=1$, the unit sphere in $\mathbb{R}^{n}$ with surface dimension $n-1$.

We note that definitionally, the columns of an orthogonal matrix form an orthogonal basis in $R^{n}$, and the same is true of both the columns and rows of a unitary matrix.

## The Haar Measure

Consider a function $f$ defined on a group $\left(\mathbb{R}, +\right)$. We thus have that for any $a\in\mathbb{R}$, the integral of $f(x)$ over $\mathbb{R}$ is invariant under a transform $x\rightarrow x+a$. Namely

Similarly, we can define a translational invariance on many other groups. For a good choice of measure on $G$, then forall elements $g\in G$:

If our measure is non-zero such that $\mu:G\rightarrow [0,\infty]$ such that $\forall S\subseteq G, g\in G,\;\mu(gS)=\mu(Sg)=\mu(S)$ where $\mu(S)\equiv\int_{g\in S}\mathrm{d}u(g)$, then we say it is a Haar Measure. It is invaraint over all the cosets of a subgroup.

If in addition we set $\mu(G)=1$, then $\mu$ is clled a probability measure on the group $G$. We can see this by noting that, given $f$ a probability distribution of $G$ ad defining $\mathrm{d}\mu(g)=f(g)\mathrm{d}g$, 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 $\mathbb{S}^{1}$ and $\text{SO}(2)$

The elements of $\mathbb{S}^{1}$ and $\text{SO}(2)$ can be paramterised by a number $\alpha\in [0,2\pi]$, giving and

We can clearly sample uniformly from both spaces by sampling uniformly from the range of $\alpha$.

### Sampling from $\mathbb{S}^{2}$ and $\text{U}(2)$

The 2-sphere $\mathbb{S}^{2}$ can be paramterised as a pair of angles, $(\theta,\phi)$ such that the coordinates in $\mathbb{R}^{3}$ are given by where $0\leq\theta\leq\pi,\;0\leq \phi < 2\pi$. Sampling uniformly over $\theta$ and $\phi$ is not sufficient as the area element of the surface is defined as $\sin\theta\mathrm{d}\theta\mathrm{d}\phi=-\mathrm{d}(\cos\theta)\mathrm{d}\phi$. Thus, we instead sample $t\in[-1,1]$ and compute $\theta=\cos^{-1}t$.

Alternatively, we can sample $(x,y,z)$ using a standard normal distribution, sampled independently for each coordinate. The resulting normalised vector $\hat{\mathbf{r}}=\frac{\mathbf{r}}{\norm{\mathbf{r}}}$ is uniformly distributed on $\mathbb{S}^{2}$.

One clear advantage of this method is that it can be generalised to $S^{n}$ by taking $n+1$ independent samples of the normal distribution.

This can then be applied to sample from $\text{SU}(2)$, where the elements are parameterised as

We can set $a\equiv e^{i\psi}\cos\phi,\;b\equiv^{i\chi}\sin\phi$, and defining a global phase $e^{i\alpha}$, we can write for $0\leq\phi\leq\pi/2,\;0\leq\alpha,\psi,\chi <2\pi$.

To sample meaningfully from this set, we need to know the expression for the volume element in $\text{SU}(2)$. This is known to be We thus sample $\alpha,\psi,\chi\in[0,2\pi]$, and $\xi\in[0,1]$ where we then compute $\phi=\sin^{-1}\sqrt{\xi}$.

We note that these $\text{SU}(2)$ unitaries can then be used to build up Givens rotations, a set of $\text{U}(n)$ rotations which are equal to the identity matrix with elements $ii,ij,ji,jj$ replaced by a $2\times 2$ matrix. These Givens rotations can be put together in to an arbitrary $\text{U}(n)$ matrix.