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?
Best Answer
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.