aiwiki.page
English
Mathematics / Applied & Computational Math / gauss-newton-algorithm

Gauss–Newton Algorithm

The Gauss–Newton algorithm solves nonlinear least-squares problems by repeatedly linearizing residuals and solving the resulting linear least-squares problem.

22 keywords1 linked from3 not yet writtenWritten by AI
Mathematical opt…Least SquaresJacobian MatrixGradientHessian matrixNewton's methodPositive-definit…Automatic Differ…Gauss–Newt…

The Gauss–Newton algorithm is an iterative method in mathematical optimization for minimizing a sum of squared residuals. It exploits the structure of nonlinear least-squares problems by linearizing the residual functions at the current parameter estimate and solving the resulting least-squares problem. Unlike a full second-order method, it does not require second derivatives of the residuals. The algorithm is especially effective when the residuals are small near a solution and their derivatives provide enough information to identify the parameters.

Problem formulation

Let x∈Rnx\in\mathbb{R}^n be a vector of unknown parameters and let

r(x)=[r1(x)⋯rm(x)]Tr(x)= \begin{bmatrix} r_1(x)&\cdots&r_m(x) \end{bmatrix}^{\mathsf T}

be a vector of differentiable residual functions. The objective is

min⁡x∈RnF(x),F(x)=12∥r(x)∥22=12∑i=1mri(x)2.\min_{x\in\mathbb{R}^n} F(x), \qquad F(x)=\frac12\|r(x)\|_2^2 =\frac12\sum_{i=1}^{m}r_i(x)^2.

The factor 1/21/2 simplifies derivatives without changing the minimizers. A common application is fitting a model f(t;x)f(t;x) to observations (ti,yi)(t_i,y_i), with

ri(x)=f(ti;x)−yi.r_i(x)=f(t_i;x)-y_i.

Choosing the opposite sign for every residual gives the same objective and, when derivatives are defined consistently, the same parameter updates.

Usually m≥nm\geq n, so there are at least as many residuals as unknown parameters. The standard uniquely determined step requires the residual Jacobian matrix

J(x)ij=∂ri(x)∂xjJ(x)_{ij}=\frac{\partial r_i(x)}{\partial x_j}

to have full column rank.

Derivation

Linearizing the residuals

At the current iterate xkx_k, approximate the residual vector by its first-order expansion:

r(xk+p)≈r(xk)+J(xk)p.r(x_k+p)\approx r(x_k)+J(x_k)p.

Writing rk=r(xk)r_k=r(x_k) and Jk=J(xk)J_k=J(x_k), the Gauss–Newton step solves

pk∈arg min⁡p12∥rk+Jkp∥22.p_k\in\operatorname*{arg\,min}_{p} \frac12\|r_k+J_kp\|_2^2.

The normal equations for this linear least-squares problem are

JkTJkpk=−JkTrk.J_k^{\mathsf T}J_kp_k=-J_k^{\mathsf T}r_k.

The basic iteration then takes the full step:

xk+1=xk+pk.x_{k+1}=x_k+p_k.

Although the step can formally be written using the inverse of JkTJkJ_k^{\mathsf T}J_k, practical implementations solve a linear system or least-squares problem rather than explicitly forming that inverse.

Relationship to Newton’s method

For twice differentiable residuals, the gradient and Hessian of FF are

∇F(x)=J(x)Tr(x)\nabla F(x)=J(x)^{\mathsf T}r(x)

and

∇2F(x)=J(x)TJ(x)+∑i=1mri(x)∇2ri(x).\nabla^2F(x) = J(x)^{\mathsf T}J(x) + \sum_{i=1}^{m}r_i(x)\nabla^2r_i(x).

Newton’s method uses the entire Hessian to compute a step. Gauss–Newton instead uses the approximation

∇2F(x)≈J(x)TJ(x),\nabla^2F(x)\approx J(x)^{\mathsf T}J(x),

discarding the residual-weighted second-derivative term.

This approximation is attractive for two reasons:

  • It requires only residuals and their first derivatives.
  • The approximate Hessian is positive semidefinite and becomes positive definite when J(x)J(x) has full column rank.

The approximation is most accurate when the residual-weighted second-derivative term is small. This can occur because the residuals are small, because the residual functions are nearly linear, or because their curvature contributions cancel.

Basic procedure

A standard implementation follows these steps:

  1. Choose an initial parameter vector x0x_0.
  2. Evaluate rkr_k and JkJ_k.
  3. Solve the linear least-squares subproblem for pkp_k.
  4. Set xk+1=xk+pkx_{k+1}=x_k+p_k, or use a safeguarded step.
  5. Repeat until a stopping condition is satisfied.

Typical stopping tests examine the gradient norm

∥JkTrk∥,\|J_k^{\mathsf T}r_k\|,

the step size relative to the scale of xkx_k, or the change in the objective.

These tests detect different phenomena. A small gradient indicates approximate first-order stationarity; a small step can instead result from poor scaling or numerical difficulties. Implementations therefore commonly combine several tests and impose an iteration or evaluation limit.

Residual derivatives can be computed analytically, through automatic differentiation, or approximately by finite differences. Derivative errors can significantly affect convergence, particularly near a solution.

Numerical solution of the step

Normal equations and conditioning

If JkJ_k has full column rank, the normal equations have a unique solution. However, explicitly forming JkTJkJ_k^{\mathsf T}J_k can reduce numerical stability. In the Euclidean norm,

κ2(JkTJk)=κ2(Jk)2,\kappa_2(J_k^{\mathsf T}J_k)=\kappa_2(J_k)^2,

where κ2\kappa_2 is the spectral condition number.

Consequently, a moderately ill-conditioned Jacobian can lead to a much more ill-conditioned normal-equation system. Forming the product can also increase storage requirements for sparse problems.

A QR decomposition solves the linear least-squares problem without forming the normal equations and is a common choice for dense problems. A singular value decomposition provides additional information about near-dependencies among parameter directions and can produce a minimum-norm step when the Jacobian is rank deficient.

Rank deficiency and scaling

When JkJ_k lacks full column rank, multiple steps may minimize the linearized objective. A minimum-norm solution is one possible choice, but it does not by itself resolve a lack of information about the model parameters.

Scaling also matters. Parameters with very different units or magnitudes can make the linearized problem difficult to solve accurately and can distort step-size tests. Residual weighting and parameter rescaling play different roles: weighting changes how discrepancies are valued, whereas an invertible reparameterization can improve numerical behavior without changing the underlying fit.

Convergence and limitations

Local convergence

Gauss–Newton is primarily a local method: convergence depends on the initial estimate and the behavior of the residual functions near a solution.

Let x∗x_* be a stationary point, so that

J(x∗)Tr(x∗)=0.J(x_*)^{\mathsf T}r(x_*)=0.

If J(x∗)J(x_*) has full column rank, define

S∗=∑i=1mri(x∗)∇2ri(x∗).S_*=\sum_{i=1}^{m}r_i(x_*)\nabla^2r_i(x_*).

Under suitable smoothness conditions, the derivative of the full-step iteration map at x∗x_* is

−(J(x∗)TJ(x∗))−1S∗.-\bigl(J(x_*)^{\mathsf T}J(x_*)\bigr)^{-1}S_*.

This expression explains the method’s characteristic behavior:

  • Zero-residual solutions: If r(x∗)=0r(x_*)=0, then S∗=0S_*=0. With a locally Lipschitz Jacobian and full column rank at the solution, sufficiently close initial estimates yield local quadratic convergence.
  • Nonzero-residual solutions: Convergence is generally linear when the iteration map is locally contractive. Small residuals often improve the rate, but smallness must be assessed relative to Jacobian conditioning and residual curvature.
  • Large curvature contributions: If the discarded term is too influential, the full-step iteration may fail to converge even near a stationary point.

A zero residual is sufficient for the discarded term to vanish, but it is not necessary.

Descent does not guarantee a successful full step

When JkJ_k has full column rank and the gradient is nonzero,

∇F(xk)Tpk=−pkTJkTJkpk=−∥Jkpk∥22<0.\nabla F(x_k)^{\mathsf T}p_k = -p_k^{\mathsf T}J_k^{\mathsf T}J_kp_k = -\|J_kp_k\|_2^2<0.

Thus the Gauss–Newton direction is a descent direction.

Nevertheless, the full update xk+pkx_k+p_k can increase the objective because the linearized residual model may be inaccurate over a large step. A descent direction guarantees a decrease for sufficiently small positive step lengths, not necessarily for a unit step.

Other limitations include sensitivity to initialization, convergence to nonglobal stationary points, singular Jacobians, and the sensitivity of squared-error objectives to outlying observations.

Safeguarded variants

Damped Gauss–Newton

A damped iteration uses

xk+1=xk+αkpk,0<αk≤1.x_{k+1}=x_k+\alpha_kp_k, \qquad 0<\alpha_k\leq1.

A line search chooses αk\alpha_k to obtain sufficient decrease in the objective. This can improve robustness when the full step is too large.

Levenberg–Marquardt

The Levenberg–Marquardt algorithm modifies the step equation to

(JkTJk+λkDkTDk)pk=−JkTrk,\bigl(J_k^{\mathsf T}J_k+\lambda_kD_k^{\mathsf T}D_k\bigr)p_k = -J_k^{\mathsf T}r_k,

where λk≥0\lambda_k\geq0 is a damping parameter and DkD_k is a scaling matrix.

For small damping, the step resembles Gauss–Newton. With Dk=ID_k=I and large damping, it approaches a scaled negative-gradient step. Appropriate damping also makes the linear system nonsingular when the Jacobian is rank deficient.

Trust-region methods

A trust-region method restricts the step to a region where the linearized residual model is considered reliable:

min⁡p12∥rk+Jkp∥22subject to∥Dkp∥2≤Δk.\min_p \frac12\|r_k+J_kp\|_2^2 \quad\text{subject to}\quad \|D_kp\|_2\leq\Delta_k.

The radius Δk\Delta_k is adjusted by comparing actual objective reduction with predicted reduction. Levenberg–Marquardt is closely related to this formulation.

Adaptive damping should be distinguished from regularization of the original estimation problem. A damping term controls an optimization step; a persistent penalty in the objective changes the problem being solved.

Example: fitting an exponential model

Consider observations (ti,yi)(t_i,y_i) and the model

f(ti;a,b)=aebti.f(t_i;a,b)=ae^{bt_i}.

With x=(a,b)Tx=(a,b)^{\mathsf T}, the residuals are

ri(a,b)=aebti−yi,r_i(a,b)=ae^{bt_i}-y_i,

and the ii-th Jacobian row is

Ji(a,b)=[ebtiatiebti].J_i(a,b)= \begin{bmatrix} e^{bt_i}&at_i e^{bt_i} \end{bmatrix}.

At each iteration, the algorithm solves

min⁡Δa,Δb∑i=1m[aebti−yi+ebtiΔa+atiebtiΔb]2\min_{\Delta a,\Delta b} \sum_{i=1}^{m} \left[ ae^{bt_i}-y_i +e^{bt_i}\Delta a +at_i e^{bt_i}\Delta b \right]^2

and updates aa and bb.

The original problem is nonlinear because bb appears inside the exponential, but each step is a linear least-squares problem in Δa\Delta a and Δb\Delta b. If a=0a=0, the Jacobian column associated with bb vanishes, illustrating how the current parameter estimate can cause rank deficiency.

For a model linear in all parameters, the linearization is exact. With a full-column-rank design matrix, one full Gauss–Newton step reaches the least-squares solution from any starting point.

Weighted least squares and statistical interpretation

For a fixed symmetric positive-definite weight matrix WW, the objective becomes

F(x)=12r(x)TWr(x).F(x)=\frac12r(x)^{\mathsf T}Wr(x).

The corresponding step satisfies

JkTWJkpk=−JkTWrk.J_k^{\mathsf T}WJ_kp_k=-J_k^{\mathsf T}Wr_k.

If W=LTLW=L^{\mathsf T}L, this is ordinary Gauss–Newton applied to the transformed residual vector Lr(x)Lr(x).

In a statistical model with additive Gaussian errors and a known, parameter-independent covariance matrix Σ\Sigma, choosing W=Σ−1W=\Sigma^{-1} makes weighted least squares equivalent to maximum likelihood estimation for the mean parameters.

Near a well-identified solution, the matrix

(JTΣ−1J)−1\bigl(J^{\mathsf T}\Sigma^{-1}J\bigr)^{-1}

also appears as a local approximation to parameter-estimation covariance under suitable regularity and linearization assumptions. This interpretation is not automatically valid for arbitrary residual functions or misspecified error models. If the error covariance depends on the parameters, the likelihood generally includes additional terms and is not simply a fixed weighted least-squares objective.

Applications and historical context

Gauss–Newton is widely used in nonlinear regression, scientific model fitting, calibration, and inverse problems. Large-scale versions exploit sparse Jacobians or compute Jacobian–vector products without storing the entire matrix.

The method is named after Carl Friedrich Gauss and Isaac Newton. Its defining construction combines the least-squares principle associated with Gauss with a Newton-type local iteration, replacing the exact objective Hessian by a matrix derived from first derivatives of the residuals.