How does Levenberg-Marquardt algorithm work in GTSAM

[sen.zep...@gmail.com]

Hi all,

I find it difficult to apply the updating formulate of LM to example cases. The updating formula should follow:

as described in Prof. Dellaert's book about factor graphs. However, in a simplified case where there is only one factor graph which contains only one factor, the 'Delta' does not seem so, as the screenshot shows:

When the Jacobian is 86.91, and b is 124.96, lambda = 1000, noise sigma=1.0, the delta calculated is -1.26966, but the formula above should give 0.001436. 

The code is used to optimize a simple 1D function: 

                                                         x^3 + sin(x) + cos(3x^2) 

without constraints, and is initialized at x=5.This screenshot can be reproduced from the cpp file attached. 

  

Considering that LM is so fundamental in gtsam, I suppose there is more likely to be something wrong in my understanding. Any help would be appreciated! Thanks!

Best,

Sen

[sen.zep...@gmail.com]

By the way, if I change the optimizer to Gauss-Newton, then the steps calculated are consistent as the code output.

[Dellaert, Frank]

Sen

Thanks! I don;t have the time to repro from your file, bit​ if you submit a PR with a failing unit test (presumably a new test in

testNonlinearOptimizer.cpp or test_NonlinearOptimizer.py) from a fork I'll git checkout the branch. Or send me a test_NonlinearOptimizer.py with a failing test in attachment.

FD

---

From: gtsam...@googlegroups.com <gtsam...@googlegroups.com> on behalf of sen.zep...@gmail.com <sen.zep...@gmail.com>
Sent: Thursday, May 12, 2022 21:54
To: gtsam users <gtsam...@googlegroups.com>
Subject: [GTSAM] Re: How does Levenberg-Marquardt algorithm work in GTSAM

 

--
You received this message because you are subscribed to the Google Groups "gtsam users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gtsam-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/gtsam-users/a341e730-cd41-4e34-b6b5-a43f39af31can%40googlegroups.com.

[voltron]

If you are looking to learn LM, I recommend going through this.

"A memo on how to use the levenberg-marquardt algorithm for refining camera calibration parameters"

https://engineering.purdue.edu/kak/computervision/ECE661_Fall2012/homework/hw5_LM_handout.pdf

In the memo's implementation:

% Apply the damping factor to the Hessian matrix

H_lm=H+(lamda*eye(Nparams,Nparams)); 

 % Compute the updated parameters 

 dp=-inv(H_lm)*(J'*d(:)); 

The difference I see between the memo and gtsam is the dampened hessian:  

H_LM = H+lambda*eye(N)   //memo

H_LM = H+lambda*diag(H) // gtsam docs.

is it just an error in the docs?

[José Luis Blanco-Claraco]

The dampened Hessian with the identity matrix is the original form.
The one with the Hessian diagonal is the "improved" method.
Refer to the last paragraphs of this Wikipedia section for the exact references:
https://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm#The_solution

Best,
JL

>> as described in Prof. Dellaert's book about factor graphs. However, in a simplified case where there is only one factor graph which contains only one factor, the 'Delta' does not seem so, as the screenshot shows:
>>

>> When the Jacobian is 86.91, and b is 124.96, lambda = 1000, noise sigma=1.0, the delta calculated is -1.26966, but the formula above should give 0.001436.
>> The code is used to optimize a simple 1D function:
>> x^3 + sin(x) + cos(3x^2)
>> without constraints, and is initialized at x=5.This screenshot can be reproduced from the cpp file attached.
>>
>> Considering that LM is so fundamental in gtsam, I suppose there is more likely to be something wrong in my understanding. Any help would be appreciated! Thanks!
>>
>> Best,
>> Sen
>>
>> --
>> You received this message because you are subscribed to the Google Groups "gtsam users" group.
>> To unsubscribe from this group and stop receiving emails from it, send an email to gtsam-users...@googlegroups.com.
>> To view this discussion on the web visit https://groups.google.com/d/msgid/gtsam-users/a341e730-cd41-4e34-b6b5-a43f39af31can%40googlegroups.com.
>
> --
> You received this message because you are subscribed to the Google Groups "gtsam users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to gtsam-users...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/gtsam-users/dc92782d-2e48-45c6-b683-0e99350c73a7n%40googlegroups.com.



--

/**
* Jose Luis Blanco-Claraco
* Universidad de Almería - Departamento de Ingeniería
* [Homepage]( https://w3.ual.es/~jlblanco/ )
* [GH profile]( https://github.com/jlblancoc )
*/

[sen.zep...@gmail.com]

Hi Frank,

Thanks for being willing to help. I still feel there's something wrong with my code that I just don't know yet. Anyway, I'm working on a paper submission recently, but will try to do more debug or create a pull request and let you know.

Best,

Sen

[sen.zep...@gmail.com]

I figure it out! By default, setDiagonalDamping in LM's parameter is false, and so LM optimizer actually uses Levenberg's version to update, i.e.,

(A^T A + \lambda I) \Delta = A^T b

If changing DiagonalDamping as true, then gtsam will update following LM's version and return right result.

Thanks!

Best,

Sen