Graham Schmidt Orthogonalisation

I was gonna start out tonight writing about the Kabsch algorithm for optimal rotation calculation between two sets of points. But then I thought it would be nice to have a random rotation matrix generation procedure, so I can properly test the Kabsch algorithm I implement. And so this is what I will do for now: generating some Rotation matrices (not quite).

Of course there are many ways to randomly generate rotation matrices for the Special Orthogonal group in 3-D (SO(3)) e.g. if you like using the Euler angle formulation, you could randomly sample the Euler angle parameters and then map to the rotation matrix.

I opted for a different approach, one where I start with a random matrix a gradually transform it into a rotation matrix. To start, we could think of the columns of a rotation matrix as the coordinates of the standard basis, when rotated using the given rotation matrix. The requirements for SO(n) are 1) that it is orthogonal and 2) that the determinant is strictly +1. Here I tackle the first requirement — to make the matrix orthogonal.

I've implemented this using the Gram-Schmidt method https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process

A view of the columns of a 3x3 before(left) and after(right) Graham-Schmidt orthogonalisation

In the left-half image above we see the columns of a random matrix (drawn from the standard normal distribution) plotted as vectors. After the orthogonalisation, seen on the right, that the vectors are unit norm and orthogonal (admittedly this is a bit hard to tell from the plot).

For a closer critique at this implementation please checkout this notebook here:

As you can see from the printout above, the Graham-Schmidt procedure doesn't necessarily produce +1 determinant matrices, so we could end up with matrices that perform mirroring and not just rotations. I will be addressing this issue in a future post when I actually use the rotation matrices :D