1
$\begingroup$

My supervisor and I were discussing a specific optimisation problem this afternoon.

To be simple: solve for $R$ in the equation $Rx=y$, where $x$, $y$ are made of samples in two difference coordination frames, with the constraint that $R$ is a rotational matrix, i.e. unit orthogonal matrix.

I know there is a paper [Horn1987] solving the problem, which gives an analytic solution.

But my supervisor argues that we should solve it iteratively for a ROBUST and STABLE solution by asserting that the iterative way is more ROBUST and STABLE than analytic one.

I think this concept is ridiculous, but I don't know how to point out his error, since I search with google but could not find some hard proof related.

So, my question is:

  1. In this problem ($Rx=y$), is the solution given by Horn better than a direct minimisation method, for example solving $\hat{R} = \mathrm{argmin}\,(|Rx-y|^2)$ with COBYLA algorithm.

  2. Generally speaking, is an iterative solution for a minimisation problem alway more stable and robust than a analytic solution if the latter exists?

[Horn1987] B. K. P. Horn, “Closed-form solution of absolute orientation using unit quaternions,” Journal of the Optical Society of America, vol. 4, no. 4, pp. 629–642, April 1987

$\endgroup$
5
  • $\begingroup$ I formatted your question a bit, but without a reference to the paper you mention, and without a more concrete question, this may be closed... $\endgroup$ Nov 10, 2014 at 15:21
  • 4
    $\begingroup$ The question is rather unclear. Where is the mentioned optimization problem? Or is it really all about rotating a given vector x to another given vector y? $\endgroup$ Nov 10, 2014 at 15:31
  • $\begingroup$ @RodrigoA.Pérez Thanks for pointing out. I edited the problem a little to point out the original problem. $\endgroup$
    – squid
    Nov 11, 2014 at 3:17
  • $\begingroup$ @PietroMajer When I mentioned the optimisation problem, I'm not referring to a specific one. I mean we can directly use a general optimisation algorithm (Gradient descendent, for examle) to minimize, for example, $f(A) = |Ax-y|^2$. $\endgroup$
    – squid
    Nov 11, 2014 at 3:18
  • $\begingroup$ There are exact formulas that are less accurate than an iterative algorithm. There should be examples for problems as simple as solving a quadratic, if you take a case when the "textbook" exact formula uses dangerous subtractions. $\endgroup$ Nov 11, 2014 at 10:51

2 Answers 2

3
$\begingroup$

It may very well be that the evaluation of the analytical solution you are referring to poses some problems. An elementary example is an analytical formula for the solution of $Ax=y$ where $A$ is an arbitrary invertible matrix, i.e. $x = A^{-1}y$. It is a nice formula, but its numerical evaluation is a horrible idea.

Quick googling for Horn's algorithm produces a lot of different results, but if we are to assume that this is the one you had in mind, the authors state in Abstract that their method requires a square root of a symmetric matrix, I presume $\sqrt{A}$. I not versed well enough in numerical mathematics to judge whether there is a stable and robust algorithm for evaluating $\sqrt{A}$, but I hope I've at least given you a clue.

$\endgroup$
2
  • $\begingroup$ Thanks for pointing out. It is indeed the paper I have in mind. I added the paper reference to the question. May I translate your opinion as: "it is the machine-espsilon that caused the unstableness if the unstableness exists"? $\endgroup$
    – squid
    Nov 11, 2014 at 3:02
  • $\begingroup$ No. :) Machine-epsilon doesn't cause the unstableness, it just makes it manifest. My opinion is simply that sometimes analytic formulae are hard to evaluate directly and it is much better to use indirect approach. I think the example with $A^{-1}$ is quite instructive. $\endgroup$ Nov 11, 2014 at 10:23
1
$\begingroup$

Without knowing your exact details I know one related example: to compute the inverse of a matrix one can apply the SVD-decomposition, which essentially is a rotation, to make the computation "more stable". The reason is, that direct inversion might introduce divisions by difference, which are as small as the "machine-epsilon" , namely when some eigenvalues of the matrix are near zero. The SVD as a rotational procedure does row- and then column-rotations, whose internal computations is numerically more stable (using cos() and sin()-multiplications). (As to references for this:I've only read that remark in some books so far, never saw an explicite proof, but maybe it is simple to do) Then only the scalar elements in the remaining diagonal need be "inverted" (means: replaced by their reciprocals) for which we have then a far better control on the error. There are more examples like this in the mathematics of the factoranalysis but I've no doubt that there are a lot of problems where this concept of preprocessing a problem by rotations stabilizes the internal computations and thus the results. (perhaps you find more searching for the term "Givens-rotation")

$\endgroup$

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