Numerical recipes / Multidimensional root search (using newt) : How to minimize the maximum error

Question

This question is related to the "numerical recipes in C++" book, so it will be reserved to people knowing a little about it as well as about multidimensional optimization.

I am writing a program that needs to search for a multidimensional root, and in order to solve it, I am using the multidimensional newton root finding method, namely the "newt" procedure.

For those interested in the details, I am trying to fit a deformable 3D model to a steresocopic view of an object, based on a few feature points (feature points which are seen by two cameras).

For this, I am using the newt procedure with the following :

• 11 Input parameters : my deformable model can be modeled with 11 parameters (composed of 5 geometric parameters and 6 deegres of freedom for the 3D object location) :
• 14 Output parameters for which I need to find the root : based on feature points which are identified by the camera, and given a set on "input parameters", I can calculate a set of distances between the feature points seen by the camera and their theoretical location. I have 7 of those points, so that gives me 14 parameters (7 distances times 2, since I calculate the distances on both cameras)

My problem is that I have more output parameters (14) than input parameters (11) : whenever I call "newt", the algorithm always converges, however it will find a solution that minimizes almost perfectly the 11 first output parameters, but that has lots of errors on the 3 remaining parameters.

However I would like the errors to be uniformly divided among the output parameters.

I already tried the approaches described below :

1. Try to combine the 14 output parameters into 11 parameter (for example, you take the average of some distances, instead of using both distances). However I am not 100% satisfied with this approach
2. Mix several solutions with the following principle :
   • Call mnewt and memorize the found root
   • Change the order of the 14 output parameter
   • Calling mnewt again and memorize the found root
   • Compute a solution is the average of the two found roots

Does anyone know of a more generic approach, in which the root finding algorithm would favor an error that is uniformly divided among the output parameters, instead of favoring the first parameters?

Gytle

Why not setup a single "distance metric", e.g. sum of squared distances over all your 7 feature points, and then run some optimization routine. Levenberg-Marquardt seems fitting. – Fbi

I tried that already, and it was a failure. If you read the multidimensional optimization of the NR book, you will see (and I believe them) that it is a bad idea to try and tranform a multidim root search into a minimum search (as per your suggestion) : you end up trying to minimize a function which has lots of local minima and lots of flat zones in one direction (ie the derived on one component is null : a nightmare for newton-like methods) – Gytle

However, I will try to run a minimization around the starting point given by newt. Maybe it will be less prone to converging to a false local minimum. – Gytle

I tried again, and I confirm : minimization does not work here, since there are two many local minimas and too many flat zones even with a good starting point. – Gytle

If you problem where a linear one, SVD (singular value decomposition) does exactly what you want. Perhaps you can re-code the Newton-Raphson step each time to use SVD instead of whatever it does to solve the linear approximation ? – Solanum

Walter, I like your suggestion ! I do not yet have a linear expression for my problem, but I will try to express one. – Gytle

@PascalT.: What minimization routines did you try with Pascal's method ? In similar situations, I recall that Levenberg-Marquardt performs poorly if you don't have an excellent first guess. – Nuncle

Answer 1

You try to minimize F(x) by solving f(x)=0 where x is an m-dimensional vector and f maps this to an n-dimensional vector. Your optimization problem is underdetermined if m < n (in your case 11 < 14).

For such systems, the generic way to solve them is to minimize a vector norm on x. You can do this by minimizing the system x^T A x + c f(x)^T f(x) with respect to both x and the Lagrange-multiplier c. Without further information, you could take A to be the nxn identity matrix. This will find the x that solves f(x)=0 while having the smallest norm.

For more details on doing this with Newton's method, see e.g. this paper.

Mayo