Gauss-Newton algorithm - Definition and Overview

In mathematics, the Gauss-Newton algorithm is used to solve nonlinear least squares problems. It is a modification of Newton's method that does not use second derivatives.

The problem

Given m functions f₁, ..., f_m of n parameters p₁, ..., p_n with m≥n, we want to minimize the sum

<math> S(p) = \sum_{i=1}^m (f_i(p))^2. <math>

Here, p stands for the vector (p₁, ..., p_n).

The algorithm

The Gauss-Newton algorithm is an iterative procedure. This means that the user has to provide an initial guess for the parameter vector p, which we will call p⁰.

Subsequent guesses p^k for the parameter vector are then produced by the recurrence relation

<math> p^{k+1} = p^k - (J_f(p^k)\,J_f(p^k)^\top)^{-1} J_f(p^k) \, f(p^k), <math>

where f=(f₁, ..., f_m) and J_f(p) denotes the Jacobian of f at p (note that J_f is not square).

The matrix inverse is never computed explicitly in practice. Instead, we use

<math> p^{k+1} = p^k + \delta^k, <math>

and we compute the update δ^k by solving the linear system

<math> J_f(p^k) \, J_f(p^k)^\top \, \delta^k = -J_f(p^k) \, f(p^k). <math>

A good implementation of the Gauss-Newton algorithm also employs a line search algorithm: instead of the above formula for p^k+1, we use

<math> p^{k+1} = p^k + \alpha^k \, \delta^k, <math>

where the number α^k is in some sense optimal.

Other algorithms

The recurrence relation for Newton's method for minimizing a function S is

<math> p^{k+1} = p^k - [H (S)(\mathbf{p}_k)]^{-1} J_S(p^k), <math>

where <math>J_S<math> and <math>H(S)<math> denote the Jacobian and Hessian of S respectively. Using Newton's method for our function <math>S(p) = \sum_{i=1}^m (f_i(p))^2<math> gives <math> J_S(p) = 2 J_f(p)\,f(p)<math> and

<math>\quad H(S)(p) = 2 J_f(p) \, J_f(p)^\top + 2 \sum_{i=1}^m f_i(p) \, \nabla^2 f_i(p), <math>

where ∇² denotes the Laplacian. We can conclude that the Gauss-Newton method is the same as Newton's method with the Σ f ∇²f term ignored.

Other algorithms for solving least squares problems include the Levenberg-Marquardt algorithm and gradient descent.