Levenberg-Marquardt Method and Minimization

[gusciora@…]

I have questions on the new LMM API and algorithm. The SDRS states that the
psMinimizeLMFunc() shall take (possibly several) coordinate vectors and
compute a single floating-point value from it. However, the ADD states, in
equation (21) that the function is supposed to be calculated for each data
point: f(x_i). I'm not sure if something is worded incorrectly, or if I'm
missing something. Can you help me make sense of that? Could it be that the
psMinimizeLMFunc() function ought to return a vector of floats, each
cooresponding to a coordinate?

Also, the SDRS states that an argument to this function is of type
psMatrix. This type was removed from the psLib months ago, I believe.
Should this argument be of type psImage, or psArray?

The last paragraph of the LMM section states that the covariance matrix is
calculating by inverting the alpha matrix. That's fine by me: the covariance
matrix is then returned as output from this function. The rest of the
paragraph goes on to explain confidence limits. That confuses me. Why do
we need confidence limits? Is that information to be returned somehow from
this function? Is that information to be used somehow in the iterative
process?

[Paul Price]

psMinimizeLMFunc returns a single value, corresponding to the value of the
function at the given coordinates, for the given parameters. For example, we
might have a psMinimizeLMFunc chiSquared, which returns the value of chi^{2 for a
fit to some function. In this case, the "psArray *coord" that gets passed to it
would include the x vector, the y vector, and the dy vector, in order to
calculate chi}2 = sum [(y - f(x))/dy]^{2. That means that the function must be
called each time you want to evaluate the function, so if you want to evaluate
the function at N different points, then you must call the psMinimizeLMFunc N times.
Added a similar explanation to the SDRS.}

Yes, the psMatrix should be a psImage --- updated the SDRS.

The bit in the ADD on confidence limits is a relic of the Pilot Project ADD ---
there's no need to worry about it. In fact, I've removed it now, since it
wasn't relevant.

[gusciora@…]

I think I'm still confused. In the description of LMM in the ADD, there are a
few "f(x_i)" terms. What do they correspond to? My current interpretation of
your answer seems to be that there is a single x_0, which corresponds to all of
the coords that the function is called with.

And on that note, the LMM as defined in the ADD is a chi-squared minimizer: it
fits a function to a set of data points. However, the psMinimizeLM() function
as defined in the SDR is simply a minimizer. Does that make sense? If I were
to use the algorithm in the ADD, what do the y_i values in equation (21)
correspond to?

[Paul Price]

Revised ADD

[gusciora@…]

Okay, that sounds good. I have coded the algorithm and am now testing it.

I have a question about the paramMask. It's not immediately obvious to me how
to apply those masks to the mastrix of equations. I suppose I could zero out
any row and column that corresponds to a masked parameter, but I haven't
analyzed the math enough to know if that will cause other problems.

My current solution is that for any paramater that is masked, I save that
parameter and always set that parameter to its original throughout the iterative
steps of the algorithm. Also, whenever the derivative is calculated, I manually
set the partial derivative with respect to that parameter to zero. Does that
make sense to you?

[Paul Price]

After checking that all entries in the paramMask are 1 or 0, when forming the A
matrix from alpha, try this:

A[i][i] = (1 + lambda*paramask[i]) * alpha[i][i];

[gusciora@…]

I implemented the algorithm in the latest ADD, and I could not successfully
minimize my example functions. I read through the LMM section in Numerical
Recipes and although I don't have the time to fully scrutinize the math, I did
notice some things which are different from the ADD.

Equation 21 of the ADD. Shouldn't there be a minus sign on the righthand side?

This corresponds roughly to equation 15.5.8 of NR. I noticed in my testing of

the ADD algorithm that in all cases, each minimization step increased, not
decreased, the value of the function. Is there a missing "minus" somewhere?

Equation 25 of the ADD describes how to calculate the new parameters. I noticed
in my testing that these new parameters were very small. This corresponds
roughly to equation 15.5.9 in NR. Shouldn't ADD (25) be the change in the
parameters, not the actual new parameters themselves?

Is LMM minimization even possible? The key to LMM minimization is the
calculation of the second-order derivatives: the Hessian matrix. NR states that
this is only possible when doing chi-squared minimization, not general
minimization, since we already know the formula for chi-squared. If I am
interpreting NR (bottom of page 681 and top of page 682) correctly, than LMM
minimization should not be possible.

[Paul Price]

Closing subsequent to release of SDRS-08, ADD-07.