Poor conditioning and different results

[m.elha...@gmail.com]

Hi Sameer,

I noticed in previous threads you discussed the potential reasons behind getting different results with the same problem (specifically, bundle adjustment case), where you mentioned one of the reasons may be the poor conditioning. Would you please elaborate more on this and why this cause randomness in the results and point to me where to learn more about such case and how to solve this issue? And why sometimes the results may look good if the problem is poorly conditioned?

Sorry, I don’t have enough mathematical background, and thanks for your help!

[Sameer Agarwal]

This is an interesting question.

When you observe randomly changing results like this, there are two things which are interacting.

The first is the fact that floating point arithmetic is not associative. 

So (a+ b) + c can be different from the value of a + (b + c), depending on the values a and b and c. In ceres, there can be two sources of re-ordering which can cause these kinds of associative errors to show up. 

The first is multi-threading, where depending on the behavior/scheduling of the threads different parts of the computation will arrive in different order, leading to different results.

The second is that ceres internally for some problems like bundle adjustment will re-order the problem itself. This is needed for example to use the schur based linear solvers. Here often there are ties that need to be broken, and that can also lead to non-determinism.

But I am sure you are thinking, if floating point arithmetic is so bad then how does the world continue to function ? :)

In reality, in a lot of cases the effects of non-associativity are very small on the order of a few ULPs(~10^-16), and you do not see their effect in your output.  This is where the concept of conditioning comes in.

Now let's suppose you are doing a two stage computation. 

let x = a + b + c

    y = f(x)

and in one instance you evaluate x as (a+b) + c and in another you evaluate it as a + (b+c).

so when you compute y you are operating with different values of x, lets call this difference dx.

now recall observe that 

f ( x + dx) ~ f(x) + f'(x) dx.

so if f'(x) has a large magnitude, it can magnify the effect of dx. Indeed the absolute condition number of f is roughly speaking |f'(x)|.

The way this will show up in ceres for example is that if your problem is poorly conditioned, which in turn means the Jacobian is has poor conditioning, what it actually means is that the function that computes the solution to the Gauss-Newton/Levenberg-Marquardt step has a very high derivative as a result and small changes to the input will result in very different solutions and when you chain these steps together you can get very different final results.

An excellent and very readable (and short) reference on this is Michael Overton's book -  Numerical Computing with IEEE Floating Point Arithmetic. Especially chapters 12 and 13 which discuss conditioning and stability of numerical algorithms. I learned a lot of what I know about floating point arithmetic from it and I cannot recommend it highly enough.

Sameer

 

--
You received this message because you are subscribed to the Google Groups "Ceres Solver" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceres-solver...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/0ecc99c5-1bf1-45c3-b52d-62d96bd0d153n%40googlegroups.com.

[m.elha...@gmail.com]

Thanks so much for the detailed explanation.

I want to follow up with a question in the essence of the BA problem. So for this part:

"The way this will show up in ceres for example is that if your problem is poorly conditioned, which in turn means the Jacobian is has poor conditioning, what it actually means is that the function that computes the solution to the Gauss-Newton/Levenberg-Marquardt step has a very high derivative as a result and small changes to the input will result in very different solutions and when you chain these steps together you can get very different final results."

What can cause the problem/Jacobian to be poorly conditioned, or what can cause a very high derivative that amplifies this small change between two results?

I have tried to center and scale the initial reconstruction and fix the first two cameras to fix the origin and scale, but it did not help solve this randomness.

[Sameer Agarwal]

The problem is not the scale/position of the reconstruction. 

The problem is how the objective function depends on the various parameters. For example one common cause of poor conditioning is the presence of radial distortion, where very small changes to the radial distortion parameters will lead to very large changes to the reprojection error. There can be other causes too, but this is a common problem. 

Sameer

To view this discussion on the web visit https://groups.google.com/d/msgid/ceres-solver/e8e7d18c-575d-4a94-b4b5-40355f536d87n%40googlegroups.com.

[m.elha...@gmail.com]

Thanks for your suggestion.

I also suspected the distortion parameters before and fixed the intrinsic parameters + distortions but still, results are not consistent.