next up previous contents
Next: Bundle adjustment Up: Levenberg-Marquardt minimization Previous: Newton iteration   Contents

Levenberg-Marquardt iteration

The levenberg-Marquardt iteration is a variation on the Newton iteration. The normal equations ${\bf N}\Delta = {\bf J}^\top{\bf J}\Delta = {\bf J}^\top {\tt\hat{e}}$ are augmented to ${\bf N}'\Delta = {\bf J}^\top {\tt\hat{e}}$ where $N'_{ij}=(1+\delta_{ij}\lambda)N_{ij}$ with $\delta_{ij}$ the Kronecker delta.

The value $\lambda$ is initialized to a small value, e.g. $10^{-3}$. If the value obtained for $\Delta$ reduces the error, the increment is accepted and $\lambda$ is divided by 10 before the next iteration. On the other hand, if the error increases then $\lambda$ is multiplied by 10 and the augmented normal equations are solved again, until an increment is obtained that reduces the error. This is bound to happen, since for a large $\lambda$ the method approaches a steepest descent.

Marc Pollefeys 2002-11-22