Levenberg–Marquardt algorithm: Difference between revisions

Revision as of 23:13, 1 November 2004

Revision as of 12:26, 2 November 2004

Line 21:

== The solution ==

Like other numeric minimization algorithms, the Levenberg-Marquardt algorithm is an [[iteration|iterative]] procedure. To start a minimization, the user has to provide an initial guess for the parameter vector '''p'''. In many cases, an uninformed standard guess like '''p'''^T=(1,1,...,1) will work fine; in other cases, the algorithm converges only if the initial guess is already somewhat close to the final solution.

The LMA solves the minimization problem according to

In each iteration step, the parameter vector '''p''' is replaced by a new estimate '''p'''+'''q'''. To determine '''q''', the functions ''f''_''i''('''p'''+'''q''') are approximated by their linearizations

:<math>(J^{T}J + \lambda I)\vec{q} = -J^{T}\vec{f}</math>.

:'''f'''</sub>('''p'''+'''q''') &approx; '''f'''_''i''('''p''') + '''J'''^T'''q'''

where '''J''' is the [[Jacobian]] of '''f''' at '''p'''.

The sum of squares ''S'' becomes minimal if &nabla;_'''q'''=0. With the above linearization, this leads to the following equation

Here <math>J</math> represents the [[Jacobian]] of the function <math>\vec{f}</math>, <math>\lambda</math> the damping factor, which is altered at every iteration, <math>I</math> the [[identity matrix]], and <math>\vec{q}</math> the solution to an [[iteration]] step.

:('''J'''^T'''J''')'''q''' = -'''J'''^T'''f'''

from which '''q''' can be obtained by inverting '''J'''^T'''J'''.

:('''J'''^T'''J''' + &lambda;)'''q''' = -'''J'''^T'''f'''.

The damping factor &lambda; is redetermined at every iteration.

== Weblinks ==