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

Improve this question
$\endgroup$
1
  • $\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, 2015 at 9:03

4 Answers 4

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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, 2015 at 14:16
  • $\begingroup$ Indeed, as is easy to see by example :-) $\endgroup$
    – Wolfgang Bangerth
    Mar 6, 2015 at 12:56
  • 1
    $\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, 2018 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.

Improve this answer
$\endgroup$
5
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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