6
$\begingroup$

The step size is computed by solving $$ (A + \mu I) h = -g $$

I could find in some literature that one can compute the step size by solving $$ (A + \mu \operatorname{diag}(A) ) h = -g $$ It is said that this is helpful for error valley problems, where the error surface at minima is flat and long. I am not able to decide whether the diagonal of $A$ should be used in general for all cases, or the identity matrix $I$ is more appropriate.

Some information:
Levenberg-Marquardt algorithm: An iterative technique that locates the minimum of a function that is expressed as the sum of squares of nonlinear functions.
$g$: Gradient matrix (Jacobian x Function values)
$A$: Approximate Hessian matrix (JacobianTransposed x Jacobian)
$\mu$: Damping factor
$h$: Step size

$\endgroup$
  • $\begingroup$ Welcome to scicomp. Your question seems very suitable for this site. You might improve it by using the Latex or code formatting. Also you might provide some more explanation of the problem. What is $A$, what is $\mu$ and so on, and what is Levenberg-Marquardt. So that people don't have to ask google first to answer your problem. $\endgroup$ – Jan Mar 5 '15 at 9:03
7
$\begingroup$

This is rather a note than an answer, but you can't always use the form with $\mu \text{diag}(A)$. In particular, if you have a case where $A$ has zeros or negative elements on the diagonal, then it is no longer guaranteed that you get a descent direction and, consequently, you may not converge.

$\endgroup$
  • $\begingroup$ In fact, $A+\mu \mbox{diag}(A)$ can be singular so that the linear system of equations for the step has no solution. $\endgroup$ – Brian Borchers Mar 5 '15 at 14:16
  • $\begingroup$ Indeed, as is easy to see by example :-) $\endgroup$ – Wolfgang Bangerth Mar 6 '15 at 12:56
  • $\begingroup$ In what case could elements in $diag(A)$ become negative? My understanding is that the $i$th diagonal element is the sum of squares of the $i$th column in $A$, which is nonnegative. $\endgroup$ – fangda May 10 '18 at 19:40
3
$\begingroup$

Using $\mu\operatorname{diag}\left(A\right)$ instead of $\mu I$ is in general superior. When you use $\mu I$ you have step width $\mu$ in every direction. If you use $\mu\operatorname{diag}\left(A\right)$, the $i$th component is $\mu a_{i,i}$, when $a_{i,i}$ is the main diagonal element of $A$ at position $\left(i,i\right)$. Therefor you have a variable step width in every direction. As Levenberg-Marquardt is essentially a mixture of Gauss–Newton and gradient descent depending on wether the damping parameter $\mu a_{i,i}$ is small or big, you can have this two algorithms combined in one iteration step for different directions.

$\endgroup$
  • $\begingroup$ Thanks Marco for the comment. Can you please elaborate on combining the two algorithms - do you mean μI should be used first and then again run the LM with μdiag(A) so that if the solution has a scope to improve, it can? $\endgroup$ – Umesh Tiwari Mar 5 '15 at 8:42
  • $\begingroup$ No, the Levenberg-Marquardt (LM) algorithm is itself a mixture of both algorithms. In the simple case with damping $\mu I$ Levenberg-Marquardt behaves like a Gauss-Newton (GN) algorithm for $\lambda$ small and like a gradient descent (GD) algorithm for $\lambda$ big. In every iteration step the parameter $\lambda$ is adjusted and therefore in each iteration step LM can behave more like GN or more like GD. With $\operatorname{diag}\left(A\right)$ instead of $I$ the LM algorithm can behave like GN or GD in one single iteration, but in different directions. $\endgroup$ – Marco Breitig Mar 5 '15 at 10:42
  • $\begingroup$ I can only comment on my own answer since I do not have enough reputation to comment on @wolfgang-bangerth answer. When I answered umesh-tiwari did not specify what he meant by the symbols, especially $A$. The original LM algorithm is a mixture of Gauss-Newton and gradient descent. For Gauss-Newton one does not compute the Hessian $A$, but approximates it with $J^{T}J$ when $J$ is the Jacobian. If that is the case, the diagonal elements of $A=J^{T}J$ will be non-negative. And what Brian said. $\endgroup$ – Marco Breitig Mar 5 '15 at 16:22
  • $\begingroup$ You can also plug in covariance matrix or weights instead of $I$, if you know scales of your variables. I agree that $diag(A)$ is generally better than $I$ - I think this is actually the Marquardt's contribution to Levenberg method. $\endgroup$ – Libor Mar 6 '15 at 16:24
  • $\begingroup$ In Marquardt's paper "An Algorithm for Least-Squares Estimation of Nonlinear Parameters", the scaling does not look like simply adding a diagonal matrix or weights. It scales the approx. Hessian matrix, gradient matrix and the steps sizes. Can anyone comment whether Marquardt's scaling is equivalent to adding a diagonal matrix? $\endgroup$ – Umesh Tiwari Mar 17 '15 at 11:03
2
$\begingroup$

The book "Nonlinear regression" by Seber and Wild references quite some paper on that matter. I think most implementations use $\mu\text{diag}(A)$ instead of $I$ in general, although I can not proof that it does perform better in all cases.

To answer Umesh Tiwari's comment (I could not comment myself): $[A + \mu\text{diag}(A)]h=−g$ is indeed equivalent to what Marquardt did propose. He formulated: $(A^*+\mu I)h^*=−g^*$ which can be modified as follows: \begin{align} (A^*+\mu I)h^* =& −g^* \\ A^*Dh +\mu Dh =& −D^{-1}g \\ DA^*Dh +\mu D^2h =& −g \\ Ah +\mu D^2h =& −g \\ (A +\mu D^2)h =& −g \\ \end{align} where $D^2$ is the diagonal of A.

$\endgroup$
0
$\begingroup$

The form $(A+μdiag(A))h=−g$ can be used always and it gives better results than $(A+μI)h=−g$ in practice. The reason given by the OP is right. It moves faster along flatter directions in error valleys because it considers curvature information better. However, Levenberg-Marquardt is a heuristic method and doesn't possess well defined guarantees on speed and convergence.

Also, Levenberg-Marquardt deals with the situation when $(A+μdiag(A))h=−g$ does not give a descent direction. Note that this method is one of the ancestors of trust region methods. So, if an iteration does not give a descent direction, then do not take the step, increase $\mu$ and proceed to the next iteration.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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