Nonlinear Least Squares: Gauss-Newton and Levenberg-Marquardt

When the model is nonlinear, there is no one-step formula. Gauss-Newton repeatedly makes a linear guess and solves it. Levenberg-Marquardt adds a safety dial that blends in cautious gradient steps. Nearly every SLAM and calibration solver uses one of the two.

Starting damping λ (LM)

Click on the cost map to pick a new starting guess.

The model

We fit $y = a\,e^{b x}$ to noisy data, so the unknowns are $\mathbf{p} = (a, b)$. With residuals $\mathbf{r} = \mathbf{y} - f(\mathbf{p})$ and Jacobian $J = \partial f / \partial \mathbf{p}$, each method solves a small linear system for its step $\Delta$:

$$\text{Gauss-Newton:}\quad (J^\top J)\,\Delta = J^\top \mathbf{r} \qquad\qquad \text{LM:}\quad \left(J^\top J + \lambda\,\mathrm{diag}(J^\top J)\right)\Delta = J^\top \mathbf{r}$$

LM raises $\lambda$ after a step that makes the cost worse, which shortens the step and turns it toward plain gradient descent. After a good step it lowers $\lambda$, which makes it behave more like Gauss-Newton.

What to notice

From a start near the answer, both methods reach it in a few steps. Click a start far away, such as high $b$ and low $a$. Gauss-Newton may jump far past the valley or run off the map, because its linear guess is poor there. LM rejects bad steps and creeps in safely. The darker the map, the lower the cost.