Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am often doing parameter estimation using Levenberg-Marquard method which involves solving the following linear system at each step:

$$(H+\lambda I)\delta=r_{i}$$

where $H$ is a square Hessian matrix, $I$ is identity matrix, $r_{i}$ is residual vector(at i-th iteration), $\lambda$ is a damping factor, $\delta$ is improvement step to compute.

The $\lambda$ value is decreased when the step improved solution (reduced objective value) and increased otherwise.

The $\lambda$ parameter can allow solving ill-posed problems as it makes the Hessian positive definite.

In most cases $H$ is positive definite by itself, but sometimes not.

What to do in that case? Should I stop the iteration completely or increase lambda until $H$ becomes positive definite and solve the problem normally?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

A similar question has been asked on MO a while ago. The answer is that you should neither stop the iteration, nor increase lambda. You could use a QR decomposition with pivoting, and set very small diagonal elements of R to zero (or use a singular value decomposition if this is a theoretical question). Another suggestion if this is too expensive was to add a small multiple of the identity to $J^TJ$ rather than by multiplying the diagonal elements by $(1+\lambda)$.

This last suggestion actually shows that your presentation of the problem is not accurate. Your are not really solving $(H+\lambda I)\delta=r_{i}$. (In that case, any $\lambda>0$ would make your problem positive definite, because the Hessian $H$ is semi-definite.) Instead, the Levenberg-Marquard method solves

$$(J^T J + \lambda\, \operatorname{diag}(J^T J)) \delta = J^T [y - f(\boldsymbol \beta)]$$

Here, it can indeed happen that the problem stays singular for $\lambda>0$, but increasing $\lambda$ won't help.

share|improve this answer
    
Well the problem is actually that the model fits the data exactly with initial parameters, hence Jacobian is zero and so does Hessian. It was a programming bug because lambda happened to be zero as well and this made the system singular. Thanks for pointing out the effect of any positive lambda - that helped. –  Libor Jun 9 '13 at 17:18
    
The problem actually appeared because I have implemented the method from "Numerical Recipes" book. They suggested to set lambda=0 after several improvements and go for "final solution"... –  Libor Jun 9 '13 at 17:21
    
Okay I have solved it - the model fitted just perfectly on the points and hence the system was singular for $\lambda = 0$... –  Libor Jun 9 '13 at 18:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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