The quaternion estimator algorithm (QUEST) is an algorithm designed to solve Wahba's problem, that consists of finding a rotation matrix between two coordinate systems from two sets of observations sampled in each system respectively.
The key idea behind the algorithm is to find an expression of the loss function for the Wahba's problem as a quadratic form, using the Cayley–Hamilton theorem and the Newton–Raphson method to efficiently solve the eigenvalue problem and construct a numerically stable representation of the solution.
The algorithm was introduced by Malcolm D. Shuster in 1981, while working at Computer Sciences Corporation.
[1] While being in principle less robust than other methods such as Davenport's q method or singular value decomposition, the algorithm is significantly faster and reliable in practical applications,[2][3] and it is used for attitude determination problem in fields such as robotics and avionics.
[4][5][6] Wahba's problem consists of finding a rotation matrix
that minimises the loss function where
are the vector observations in the reference frame,
are the vector observations in the body frame,
is a rotation matrix between the two frames, and
It is possible to rewrite this as a maximisation problem of a gain function
is known as the attitude profile matrix.
In order to reduce the number of variables, the problem can be reformulated by parametrising the rotation as a unit quaternion
, representing the rotation of angle
around an axis whose direction is described by the vector
, subject to the unity constraint
in terms of the quaternion parametrisation as where
with the quaternion representation and simplifying the resulting expression, the gain function can be written as a quadratic form in
matrix is defined from the quantities This quadratic form can be optimised under the unity constraint by adding a Lagrange multiplier
, obtaining an unconstrained gain function that attains a maximum when This implies that the optimal rotation is parametrised by the quaternion
that is the eigenvector associated to the largest eigenvalue
[1][2] The optimal quaternion can be determined by solving the characteristic equation of
and constructing the eigenvector for the largest eigenvalue.
, it is possible to rewrite as a system of two equations where
This permits to construct the optimal quaternion
An alternative expression of the solution that does not involve the Rodrigues vector can be constructed using the Cayley–Hamilton theorem.
is where The Cayley–Hamilton theorem states that any square matrix over a commutative ring satisfies its own characteristic equation, therefore allowing to write where and for
this provides a new construction of the optimal vector that gives the conjugate quaternion representation of the optimal rotation as where The value of
can be determined as a numerical solution of the characteristic equation.
inside the previously obtained characteristic equation gives where whose root can be efficiently approximated with the Newton–Raphson method, taking 1 as initial guess of the solution in order to converge to the highest eigenvalue (using the fact, shown above, that
when the quaternion is close to the optimal solution).