Generating a random element of $SO(3)$

One has to be very careful about sampling uniformly over the space of rotations. The probability density must correspond to the Haar measure, which means that a random rotation should be obtained by picking a point at random on ${\mathbb{S}}^3$ and forming the unit quaternion. An extremely clever way to sample $SO(3)$ uniformly at random is given in [883] and is reproduced here. Choose three points $u_1,u_2,u_3 \in [0,1]$ uniformly at random. A uniform, random quaternion is given by the simple expression

$$h = (\sqrt{1-u_1}\sin 2 \pi u_2,\; \sqrt{1-u_1}\cos 2 \pi u_2,\; \sqrt{u_1}\sin 2 \pi u_3,\; \sqrt{u_1}\cos 2 \pi u_3) .$$ (5.15)

A full explanation of the method is given in [883], and a brief intuition is given here. First drop down a dimension and pick $u_1,u_2 \in [0,1]$ to generate points on ${\mathbb{S}}^2$. Let $u_1$ represent the value for the third coordinate, $(0,0,u_1) \in {\mathbb{R}}^3$. The slice of points on ${\mathbb{S}}^2$ for which $u_1$ is fixed for $0 < u_1 < 1$ yields a circle on ${\mathbb{S}}^2$ that corresponds to some line of latitude on ${\mathbb{S}}^2$. The second parameter selects the longitude, $2 \pi u_2$. Fortunately, the points are uniformly distributed over ${\mathbb{S}}^2$. Why? Imagine ${\mathbb{S}}^2$ as the crust on a spherical loaf of bread that is run through a bread slicer. The slices are cut in a direction parallel to the equator and are of equal thickness. The crusts of each slice have equal area; therefore, the points are uniformly distributed. The method proceeds by using that fact that ${\mathbb{S}}^3$ can be partitioned into a spherical arrangement of circles (known as the Hopf fibration); there is an ${\mathbb{S}}^1$ copy for each point in ${\mathbb{S}}^2$. The method above is used to provide a random point on ${\mathbb{S}}^2$ using $u_2$ and $u_3$, and $u_1$ produces a random point on ${\mathbb{S}}^1$; they are carefully combined in (5.15) to yield a random rotation. To respect the antipodal identification for rotations, any quaternion $h$ found in the lower hemisphere (i.e., $a < 0$) can be negated to yield $-h$. This does not distort the uniform random distribution of the samples.