Quaternion
Background
Quaternions are a number space that can be represented as a 4D point \(\displaystyle q = (q_0, q_1, q_2, q_3) = (q_0, \mathbb{q})\) with unit norm. Here, \(\displaystyle \mathbf{q}\) represented the imaginary part.
Conjugation is \(\displaystyle \bar{q} = (q_0, -\mathbf{q}\).
Multiplication is \(\displaystyle q * p = (q_0 p_0 - \mathbf{q} \cdot \mathbf{p}, q_0 \mathbf{p} + p_0 \mathbf{q} + \mathbf{q} \times \mathbf{p})\).
Rotations
Quadratically conjugating a quaternion as follows is equivalent to applying a rotation on \(\displaystyle \mathbf{x}=(x,y,z)\):
\(\displaystyle q * (c,x,y,z)*\bar{q} = (c, R(q) \cdot \mathbf{x})\)
Here, \(\displaystyle R(q)=R(-q)\) is a two-to-one mapping from quaternions to 3x3 rotation matrices.
Quaternion multiplication corresponds to composing rotations:
\(\displaystyle R(q*p) = R(q) \cdot R(p)\)
The quaternion \(\displaystyle q=(\cos(\theta/2), \hat{n}_1 \sin(\theta/2), \hat{n}_2 \sin(\theta/2), \hat{n}_3 \sin(\theta/2))\) is equivalent to the rotation around axis \(\displaystyle \hat{n}\) by angle \(\displaystyle \theta\).
Slurp
Slerp, or spherical linear interpolation is done as: \[ slerp(q_0, q_1, s) \equiv q(s)[q_0, q_1] = q_0 \frac{\sin((1-s)\phi)}{\sin \phi} + q_1 \frac{\sin(s\phi)}{\sin \phi} \] Here \(\displaystyle \phi\) is the angle between the two quaternions: \(\displaystyle \cos(\phi) = q_0 \cdot q_1\).
Spatial Alignment Problem
Also known as the RMSD problem.
Let \(\displaystyle \{y_k\}\) be a data array with N columns of D-dimensional points, known as the reference structure.
Let \(\displaystyle \{x_k\}\) be a data array of matched points, known as the test structure.
The goal is to rotation \(\displaystyle \{x_k\}\) by a rotation matrix \(\displaystyle R_{D} \in SO(D)\) to minimize the mean squared distance:
\[
\mathbf{S}_D = \sum_{k=1}^{N} \Vert R_D \cdot x_k - y_x \Vert^2
\]
The paper by Hanson focuses on 3D points.
Cross-term maximization
It can be shown that the least squares minimization problem can be converted to a cross-term maximization: \(\displaystyle \begin{aligned} \mathbf{S}_D &= \sum_{k=1}^{N} \Vert R_D x_k - y_k \Vert^2\\ &= \sum_{k=1}^{N} (R_D x_k - y_x)^T(R_D x_k - y_k)\\ &= \sum_{k=1}^{N} ( x_k ^T R_D^T - y_k^T)(R_D x_k - y_k)\\ &= \sum_{k=1}^{N} ( x_k ^T R_D^T - y_k^T)(R_D x_k - y_k)\\ &= \sum_{k=1}^{N} - 2(R_D x_k) \cdot y_k\\ \end{aligned} \)
So minimization of \(\displaystyle \mathbf{S}_D\) is equivalent to maximization of \(\displaystyle \sum_{k=1}^{N} (R_D x_k) \cdot y_k = tr R_d \cdot E\) where \(\displaystyle E_{ab} = \sum_{k=1}^{N} [x_k]_a [y_k]_b = [X \cdot Y^T]_{ab}\). This is also equivalent to solving \(\displaystyle \delta(q) = q M(E) q^t\).
Algebraic Solutions
There are expressions for solving the eigenvalues of \(\displaystyle M\).