Gauss–Newton Algorithm¶

An iterative nonlinear least-squares algorithm that linearizes the residual vector and solves the resulting Jacobian least-squares subproblem for each parameter update.

Version: v3 · 2026-09-06 · History
Domain-specific #: 1914
Origin domain: numerical optimization
Subdomain: nonlinear least squares
Aliases: Gauss–Newton Method

Core Idea¶

The Gauss–Newton algorithm solves a smooth nonlinear least-squares problem by repeatedly replacing its nonlinear residual map with a first-order linear model. Given residuals \(r:\mathbb R^n\to\mathbb R^m\) and

\[ S(\beta)=\frac12\lVert r(\beta)\rVert_2^2, \]

let \(J_k\) be the \(m\times n\) Jacobian of \(r\) at the current iterate \(\beta_k\). The method chooses a step \(\Delta_k\) that solves

\[ \min_{\Delta}\ \lVert r_k+J_k\Delta\rVert_2^2, \qquad r_k=r(\beta_k), \]

and updates \(\beta_{k+1}=\beta_k+\Delta_k\). If \(J_k\) has full column rank, the idealized step satisfies

\[ J_k^{\mathsf T}J_k\Delta_k=-J_k^{\mathsf T}r_k. \]

The defining identity is the cycle evaluate residuals → form Jacobian → solve a linear least-squares subproblem → update → repeat. The normal equations describe the step, but robust implementations normally use QR, SVD, or another least-squares solver rather than forming an inverse of \(J_k^{\mathsf T}J_k\). Gauss–Newton exploits the sum-of-squares structure to avoid explicit second derivatives.^[1]

Structural Signature¶

The parameter vector: current unknowns \(\beta_k\) in a declared admissible region.
The residual map: differentiable component functions whose squared Euclidean norm defines the objective.
The Jacobian: first derivatives of all residuals with respect to all parameters.
The local residual model: \(r(\beta_k+\Delta)\approx r_k+J_k\Delta\).
The linear least-squares step: a minimizer of the modeled residual norm, found by a stable solver.
The update: \(\beta_{k+1}=\beta_k+\Delta_k\), possibly after a separately declared globalization rule.
The rank and scaling checks: conditioning of \(J_k\) determines whether the step is identifiable and numerically reliable.
The stopping test: small gradient, step, objective change, or residual, interpreted as numerical termination rather than global proof.

Recognition test. Ask whether the objective is explicitly a sum of squared residuals and whether each step comes from linearizing those residuals. A method using only the scalar objective gradient, a full general-purpose Hessian, or a different loss is not bare Gauss–Newton.

What It Is Not¶

It is not the nonlinear least-squares problem itself. The accepted Nonlinear Least Squares node defines the estimation objective and permits Gauss–Newton, Levenberg–Marquardt, trust-region, variable-projection, and other solvers. Gauss–Newton is one solver with a particular step construction.

It is not Newton's method applied unchanged to an arbitrary scalar objective. For

\[ \nabla^2 S(\beta)=J^{\mathsf T}J+\sum_{i=1}^{m}r_i(\beta)\nabla^2r_i(\beta), \]

Gauss–Newton drops the residual-weighted second-derivative term and uses \(J^{\mathsf T}J\) as the Hessian model.^[2] This is accurate near a small-residual solution or when that omitted term is controlled, but not universally.

It is not gradient descent, which chooses a direction proportional to \(-J^{\mathsf T}r\) and requires a step size. It is not automatically Levenberg–Marquardt, which adds damping, nor a trust-region method, which constrains the step. It is not linear least squares, whose Jacobian is constant and needs no repeated relinearization.

Scope of Application¶

Gauss–Newton is used for nonlinear regression, parameter estimation, curve fitting, inverse problems, bundle adjustment, system identification, geodesy, and overdetermined systems of nonlinear equations. It is especially attractive when first derivatives are accessible but residual Hessians are expensive or inconvenient.

Weighted least squares can be reduced to the same structure after applying a weighting or whitening operator to the residuals and Jacobian. Constraints, robust losses, bounds, and sparse structure require explicit extensions; their solvers may retain a Gauss–Newton model while no longer being the bare algorithm.

Convergence is local. With adequate smoothness, a full-rank Jacobian, a suitable initial point, and a sufficiently good local model, the iterates can converge rapidly. A large residual at the solution, poor scaling, rank deficiency, or a remote starting point can produce slow convergence, oversized steps, stagnation, or divergence.

Clarity¶

Sign conventions must be stable. This dossier defines \(J=\partial r/\partial\beta\), giving \(r+J\Delta\) and \(J^{\mathsf T}J\Delta=-J^{\mathsf T}r\). If residuals are defined as observations minus predictions while \(J\) differentiates predictions, the local expression becomes \(r-J\Delta\) and the right-hand sign reverses.

Writing \((J^{\mathsf T}J)^{-1}J^{\mathsf T}r\) is mathematically compact but computationally hazardous. Squaring the condition number through normal equations can lose accuracy. Rank-deficient or nearly rank-deficient problems require pivoted QR, SVD, regularization, constraints, or a different parameterization.^[3]

Stopping is not validation. A small step can result from bad scaling, and a small gradient can occur at a saddle or poor local minimum. Residual plots, parameter sensitivity, rank, and model adequacy remain separate obligations.

Manages Complexity¶

Direct Newton optimization of \(S\) requires all second derivatives of all residuals. Gauss–Newton compresses that curvature calculation into the Gram matrix \(J^{\mathsf T}J\), which is assembled from first derivatives already needed to understand local sensitivity.

Each nonlinear iteration becomes a familiar linear least-squares problem. This permits mature dense, sparse, and structured linear algebra, and exposes parameter identifiability through singular values of the Jacobian. The approximation is reusable across different scientific models because only the residual evaluation and Jacobian change.

The method retains local sensitivity while discarding residual curvature. That trade is the source of both its efficiency and its characteristic failure modes.

Abstract Reasoning¶

Taylor expansion gives

\[ r(\beta_k+\Delta)=r_k+J_k\Delta+O(\lVert\Delta\rVert^2). \]

Substituting the linear part into \(S\) yields the quadratic model

\[ m_k(\Delta)=\frac12\lVert r_k+J_k\Delta\rVert^2. \]

Differentiating gives \(\nabla m_k(\Delta)=J_k^{\mathsf T}(r_k+J_k\Delta)\), so stationarity produces the normal equations. When \(J_k\) has full column rank, \(J_k^{\mathsf T}J_k\) is positive definite and the modeled step is unique.

The same derivation explains the approximate Hessian. The exact gradient is \(J^{\mathsf T}r\); differentiating it produces \(J^{\mathsf T}J\) plus residual-weighted second derivatives. If residuals vanish at the solution, the omitted term vanishes there, helping explain Newton-like local behavior.

Knowledge Transfer¶

The mechanism transfers literally across models because a residual map supplies a common interface. An exponential decay fit, camera reprojection problem, chemical kinetic fit, and nonlinear calibration all form \(r\), compute \(J\), solve the local least-squares problem, and update parameters.

Automatic differentiation changes how \(J\) is obtained, not the algorithm's identity. Sparse QR changes the step implementation, not the local model. Damping and trust regions modify the identity enough to require variant labels, though they preserve a Gauss–Newton model internally.

Outside numerical estimation, “linearize and correct” is only a broad analogy. The accepted Algorithm and Optimization primes carry the portable procedure/search patterns. Gauss–Newton requires squared residuals and Jacobian least squares.

Examples¶

One residual. Let \(r(\beta)=\beta^2-2\). At \(\beta_0=1\), \(r=-1\) and \(J=2\), so \(\Delta=1/2\) and \(\beta_1=1.5\). The next step is \(-0.25/3\), giving approximately \(1.4167\). With one scalar residual, this coincides with Newton iteration for the root \(r=0\).

Exponential decay. For predictions \(f(t;a,b)=ae^{-bt}\), residuals \(r_i=f(t_i;a,b)-y_i\) have Jacobian columns \(e^{-bt_i}\) and \(-at_i e^{-bt_i}\). Each iteration fits a linear correction in \(a,b\), then reevaluates the nonlinear model.

Bundle adjustment. Reprojection residuals across many cameras and points yield a large sparse Jacobian. Sparse elimination or iterative linear algebra can solve the Gauss–Newton subproblem without changing its defining residual-linearization step.

Rank failure. If a model depends only on \(a+b\), the Jacobian columns for \(a\) and \(b\) coincide. The normal matrix is singular, revealing that the parameters are not separately identifiable.

Structural Tensions¶

First-derivative economy versus curvature omission: avoiding residual Hessians saves work but can spoil the model. Diagnostic: compare residual magnitude and the omitted second-order term near the iterate.
Fast local convergence versus initialization sensitivity: a strong local step may be unsafe far from a solution. Diagnostic: monitor predicted versus actual reduction and globalize when they disagree.
Normal-equation clarity versus numerical stability: the compact equation squares conditioning. Diagnostic: inspect singular values and prefer QR or SVD for the solve.
Parameter fit versus identifiability: low residual can coexist with a rank-deficient Jacobian. Diagnostic: check numerical rank and parameter sensitivities.
Bare method versus damped variant: damping can rescue steps but changes the update. Diagnostic: record whether a \(\lambda I\) term or trust-region radius is active.
Numerical termination versus scientific adequacy: convergence does not validate the model. Diagnostic: separate solver criteria from residual and domain diagnostics.

Structural–Framed Character¶

Gauss–Newton is strongly structural: the residual vector, Jacobian, linear least-squares solve, and update persist across implementations and scientific models. Coordinate scaling changes numerical behavior but not the defining cycle.

Its numerical-optimization framing is indispensable. Without differentiable residuals and a squared norm, the Hessian approximation and normal-equation step have no literal meaning. It remains domain-specific.

Structural Core vs. Domain Accent¶

The portable core is an iterative algorithm that replaces a difficult problem with a locally tractable model and corrects its state. The domain accent is nonlinear least squares, residual Jacobians, and a linear least-squares correction.

Algorithm supplies the genus, while Optimization supplies the problem-solving context. Nonlinear Least Squares supplies the problem class. None alone entails the specific \(J^{\mathsf T}J\) curvature model and update cycle.

prime:algorithm is the proposed minimal parent by strict specialization. Gauss–Newton is a repeatable stepwise procedure with defined inputs, transformations, stopping criteria, and output.

prime:optimization is a broader problem context. domain_specific:nonlinear_least_squares is the problem class solved rather than a taxonomic parent of a method. Regularization is optional in damped or ill-conditioned variants.

Relationships to Other Abstractions¶

Current abstraction Gauss–Newton Algorithm Domain-specific

Parents (1) — more general patterns this builds on

Gauss–Newton Algorithm is a kind of Algorithm Prime

prime:algorithm is the proposed minimal parent by strict specialization.

Hierarchy paths (2) — routes to 2 parentless roots

Gauss–Newton Algorithm → Algorithm → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space¶

Gauss–Newton Algorithm sits in a sparse region of the domain-specific corpus (85^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Numerical Discretization & Element Methods (6 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Nonlinear least squares: the objective class, independent of solver.
Newton's method: uses a full scalar-objective Hessian or solves root equations directly.
Gradient descent: follows the negative gradient with a selected step length.
Levenberg–Marquardt algorithm: adds a damping term to the Gauss–Newton model.
Trust-region reflective method: constrains steps and often supports bounds.
Linear least squares: one fixed linear problem rather than repeated linearizations.
Fisher scoring: replaces a likelihood Hessian by expected information in statistical estimation.
Gauss–Seidel method: a stationary iteration for linear systems, unrelated despite the shared name.

References¶

[1] NIST/SEMATECH, e-Handbook of Statistical Methods, “Nonlinear Least Squares Regression,” https://www.itl.nist.gov/div898/handbook/pmd/section1/pmd142.htm. registry ↩

[2] Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2^nd ed., Springer, 2006, chapter 10, “Least-Squares Problems,” https://doi.org/10.1007/978-0-387-40065-5. registry ↩

[3] Åke Björck, Numerical Methods for Least Squares Problems, SIAM, 1996, chapters 1 and 9, https://doi.org/10.1137/1.9781611971484. registry ↩