3-D Rotation Problem:
Given
S = s_{0}, s_{1}, ..., s_{n-1}, and
T = t_{0}, t_{1}, ... t_{n-1},
where each s_{i} and each t_{i} is a 3-D vector,
⟨?_{x}, ?_{y}, ?_{z}⟩,
find a rotation, R, by some angle θ, about
some axis, u, through the origin, ⟨0, 0, 0⟩,
so as to minimise the sum of squared errors
between S' = map R S and T, that is
∑_{i}
(norm(s'_{i} - t_{i}))^{2}.
Note, it is given that
s_{i} ~ t_{i}, 0 ≤ i < n.
To find the general rigid-body transformation of S that gives the
least-squares superposition of S on T
(a version of the Total Least-Squares (TLS) problem),
first make the centre of gravity (CoG) of T the origin,
then translate S's CoG (carrying S with it) to that origin, and
finally solve the rotation problem above.
This problem appears in the superposition of two
protein
structures in
Bioinformatics.
Kearsley's Method:
This uses the
quaternion
representation of 3-D rotations, and an
Eigen-value
finding algorithm, such as the
Jacobi algorithm, say.
A pure rotation is represented by a constrained quaternion
-- a general quaternion having four degrees of freedom and
a 3-D rotation only three -- so a
Lagrange
multiplier also gets a look in.
All this leads to an Eigen-value problem on a 4×4 matrix.
The smallest Eigen-value, λ, is the least-square error, and
the corresponding Eigen-vector yields the required rotation (quaternion).