How to introduce Levenberg-Marquardt?

Question

How would you introduce the Levenberg-Marquardt algorithm:

1. To someone who understand the concept of minimisation and derivative.
2. By using intuition instead of equation if possible.

For instance a way to explain Newton, Gauss-Newton or Gradient-descent algorithms is to use such illustrations:

Animated illustration of the Newton algorithm

Next iteration where the first derivative = 0.

Animated illustration of the Gauss-Newton algorithm

Next iteration where the second derivative is minimal.

[Animated illustration of the Gradient algorithm: i.stack.imgur.com/X93yc.gif][3]

Step size increases if direction stays the same and is dropped when the gradient has changed its direction

Is there any equivalent illustration for the Levenberg-Marquardt algorithm?

Answer 1

An intuitive animation of gradient descent (GD) is pretty easy to come up with. But I think a better intuitive explanation of Gauss-Newton (GN) when dimensions are higher is this: Consider gradient descent, in each step you move in the opposite direction of the gradient by a step of a given size. In GN (assuming you are near the solution), you also take a step in the opposite direction of the gradient, but you distort your step to match the curvature of the surface*.

The Levenberg-Marquardt algorithm, just as @Nir Regev said, is an attempt at oscillating between GN (when we are near a solution, and seek to refine it) and GD (When we are far from an optimium, and need to make large jumps on the surface).

*: (this could be seen as the result of the relationship between the hessian and covariance matrices)

Answer 2

The way to understand the LM algorithm is by reading about Tikhonov regularization and its usage as a "penalty" term.

Intuitively, illustratively, you can take the coefficient of the regularization to zero and get GN or take it to infinity and get GD. When it's in between its compensating for cases when the problem is ill posed and the model cannot be approximated by a first order Taylor expansion accurately. (The approximation GN use)

Notations: GN - Gauss Newton. LM - Levenberg Marquardt. GD - Gradient Descent.