13
$\begingroup$

Could anyone recommend a method for the following least-squares problem:

find $R \in \mathbb{R}^{3 \times 3}$ that minimizes: $\sum\limits_{i=0}^N (Rx_i - b_i)^2 \rightarrow \min$, where $R$ is a unitary (rotation) matrix.

I could get an approximate solution by minimizing $\sum\limits_{i=0}^N (Ax_i - b_i)^2 \rightarrow \min$ (arbitrary $A \in \mathbb{R}^{3 \times 3}$), taking matrix $A$ and:

  • computing SVD: $A = U \Sigma V^T$, dropping $\Sigma$ and approximating $R \approx U V^T$
  • computing polar decomposition: $A = U P$, dropping scale-only symmetric (and positive definite in my case) $P$ and approximating $R \approx U$

I could also use QR decomposition, but it wouldn't be isometric (would depend on the choice of the coordinate system).

Does anyone know of a way to do this, at least approximately, but with better approximation than the two methods above?

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ I used Kabsch's algorithm for a similar problem, which is essentially the SVD method you mentioned en.wikipedia.org/wiki/Kabsch_algorithm if i'm not wrong the svd method minimizes the equation, I'm not sure what you mean by a 'better' method? $\endgroup$
    – isti_spl
    Jan 20, 2014 at 20:22
  • 2
    $\begingroup$ OMG I just got the same reply IRL. Thanks! Apparently dropping $\Sigma$ works unless $det(UV^T)$ is negative, in which case the optimal rotation includes a reflection (and any rotation is equally bad). This technically answers the question, however, does anybody know of a cheaper method than computing SVD? It's a 3x3 SVD, but I need to do a lot of them (this is for FEM simulation, and the problem is computed for each FE) Also, the problem is apparently called Wahba's problem, and it apparently appears in aeronautics to determine a craft orientation. $\endgroup$
    – Sergiy Migdalskiy
    Jan 20, 2014 at 20:26
  • $\begingroup$ i've seen this related problems:scicomp.stackexchange.com/questions/7552/… $\endgroup$
    – isti_spl
    Jan 20, 2014 at 20:35
  • $\begingroup$ and this one:dsp.stackexchange.com/questions/1911/… $\endgroup$
    – isti_spl
    Jan 20, 2014 at 20:37
  • $\begingroup$ @isti_spl: Could you please migrate your comment to an answer? $\endgroup$
    – Geoff Oxberry
    Jan 20, 2014 at 23:19

1 Answer 1

Reset to default
10
$\begingroup$

The problem is called Wahba's problem, one algorithm for it is called Kabsch algorithm, and the later more popular is called Davenport q method. It's apparently used and studied in aeronautics to determine a craft orientation. There are lots of reviews about the methods.

Beware that the best fit may include reflection.

Kabsch method computes a 3x3 covariance matrix SVD and drops the $\Sigma$ term (modulo one reflection, which usually is accounted for by negating the last column of $U$ in the SVD). It's very straightforward to generalize to other number of dimensions.

Davenport q method is often touted as the first practical algorithm, perhaps someone can comment why. It also constructs a 3x3 covariance matrix, but then parametrizes the rotation matrix as a function of a quaternion, and the problem becomes that of computing the max-eigenvalue eigenvector of a symmetrical 4x4 matrix.

(Some of) the most popular numerical implementations are called QUEST and FOMA. These methods are usually a variation on the theme of computing the max eigenvalue by writing out and optimizing the characteristic polynomial (a quartic), and either solving it analytically (pretty involved computations, going through Kardano formulae), or with Newton iteration.

Schuster also developed and analyzed some iterative algorithm variants.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ For some history in the aerospace community, take a read of Humble Problems by Markley. $\endgroup$
    – Damien
    Jan 21, 2014 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.