[Levenberg-Marquardt]What is the link between positive-definiteness and well-conditioning?

Question

Working on optimization problems through neural networks, I use the Levenberg-Marquardt algorithm. I have read this assertion that I do not understand :

A positive definite diagonal matrix is added to Hessian approximation that is designed to turn the matrix into a positive-definite one in order to avoid the ill-conditioning problem. Google books : gW51UqDZfB8C

The same in an other reference :

The error surface contains many saddle points, so there may be points during training where the Hessian is indefinite (i.e., has both positive and negative eigenvalues) and the condition number does not exist. ftp://ftp.sas.com/pub/neural/illcond/illcond.html

I don't get why having a positive definite matrix helps to avoid the ill-conditioning problem, because the condition number here is defined unless the matrix is singular. For instance Hilbert's matrix are both positive-definite and an exemple of ill-conditionned matrix.

But it appears to be used in LM implentations : https://gist.github.com/rbabich/3539146

Here, line 98 /* ill-conditioned ? */ the author checks the ill-conditioning in his cholesky function (line 103) : that says the matrix is ill conditioned if and only if it is not positive-definite (line 206).

So here's the problem, I'm a bit confused with all these considerations because to me the only two things that positive-definiteness adds in LM is to be sure that the chosen direction is a descent one. And that if the damping factor is huge it adds stability to the gradient descent because the matrix becomes well conditioned (lambda_max/lambda_min ~ 1)

Thank you for your attention!

Answer 1

Those sound pretty important to me! If the direction is not a descent direction then there is no way to guarantee progress towards a minimum; the iterations can oscillate around far away from the optimum without ever converging, even in the limit of infinite iterations.

If the matrix is ill-conditioned, there can be large errors in the update computed by solving the linear system involving that matrix. These large errors can again cause the search direction to not be a descent direction.

But there is another subtle issue. Newton's method without modification is attracted to saddle points. If you have a very good initial guess, so that you start in the basin of convergence to a minimum, this is not a problem; but often one uses Newton's method for global optimization without a great initial guess, so that convergence to a saddle point becomes a real danger, especially in high dimensions. Regularizing the Hessian when it is detected that it is indefinite prevents saddle points from being attractive.