Math 2.0

Numerical analysis Least squares and ill-posed problems Theorem

Gauss–Newton algorithm

Builds on Jacobian matrixLeast squaresNewton's methodLipschitz continuityRate of convergence

Statement

Let D⊆ℝnD \subseteq \R^n be open, let m≥nm \ge n, and let r ⁣:D→ℝmr \colon D \to \R^m be continuously differentiable with Jacobian matrix J(x)J(x). The aim is to minimize S(x)=12∥r(x)∥22S(x) = \tfrac12 \norm{r(x)}_2^2. The Gauss–Newton algorithm starts from x0∈Dx_0 \in D and sets xk+1=xk−(J(xk)TJ(xk))−1J(xk)Tr(xk),x_{k+1} = x_k - \bigl( J(x_k)^T J(x_k) \bigr)^{-1} J(x_k)^T r(x_k), as long as J(xk)J(x_k) has full column rank. Suppose that x∗∈Dx^* \in D satisfies r(x∗)=0r(x^*) = 0, that J(x∗)J(x^*) has full column rank, and that JJ is Lipschitz continuous near x∗x^*. Then there are δ>0\delta > 0 and C>0C > 0 such that, for every x0x_0 with ∥x0−x∗∥<δ\norm{x_0 - x^*} < \delta, the iterates are defined, converge to x∗x^*, and satisfy ∥xk+1−x∗∥≤C∥xk−x∗∥2.\norm{x_{k+1} - x^*} \le C \norm{x_k - x^*}^2.

Remarks

The step pk=xk+1−xkp_k = x_{k+1} - x_k is the least squares solution of the linearized problem min⁡p∥r(xk)+J(xk)p∥2\min_p \norm{r(x_k) + J(x_k) p}_2. In practice one computes it by a QR factorization of J(xk)J(x_k) rather than by forming JTJJ^T J. The Hessian of SS is JTJ+∑iri∇2riJ^T J + \sum_i r_i \nabla^2 r_i. Gauss–Newton drops the second term, so near a zero-residual solution it behaves like Newton's method, which gives the quadratic rate.

If r(x∗)≠0r(x^*) \ne 0, the dropped term need not vanish, and the convergence is then in general only linear. For large residuals or strongly nonlinear rir_i, the iteration may diverge even from good starting points. A line search or the Levenberg–Marquardt algorithm makes the method robust. Example: fitting y=ecty = e^{c t} to the data (0,1)(0, 1), (1,e)(1, e) has zero residual at c=1c = 1, so Gauss–Newton converges quadratically from any c0c_0 near 11.

Going deeper

For a student

The method needs only first derivatives of the residuals, unlike Newton's method for SS, which needs second derivatives. It is the basic method of nonlinear regression and of many calibration and inverse problems. The rank condition on J(x∗)J(x^*) is needed: without it the linearized problems have no unique solution, and the convergence theory fails.

Reading path

To understand this page from the ground up, read these 33 pages in order. The foundations come first.

Show the path as a graph
Euclidean space, object, no evidence levelEuclidean spaceobjectFunction, concept, no evidence levelFunctionconceptLimit point of a set, definition, no evidence levelLimit point of a setdefinitionLipschitz continuity, definition, no evidence levelLipschitz continuitydefinitionMatrix, definition, no evidence levelMatrixdefinitionRate of convergence, concept, no evidence levelRate of convergenceconceptVector space, definition, no evidence levelVector spacedefinitionTotal derivative, concept, no evidence levelTotal derivativeconceptFunction of several variables, concept, no evidence levelFunction of several v…conceptLimit of a function, definition, no evidence levelLimit of a functiondefinitionTranspose, definition, no evidence levelTransposedefinitionInner product, definition, no evidence levelInner productdefinitionLinear map, definition, no evidence levelLinear mapdefinitionLinear subspace, definition, no evidence levelLinear subspacedefinitionNorm, definition, no evidence levelNormdefinitionPartial derivative, concept, no evidence levelPartial derivativeconceptDerivative, definition, no evidence levelDerivativedefinitionInner product space, definition, no evidence levelInner product spacedefinitionOrthogonal vectors, definition, no evidence levelOrthogonal vectorsdefinitionEndomorphism, definition, no evidence levelEndomorphismdefinitionSum of subspaces, definition, no evidence levelSum of subspacesdefinitionJacobian matrix, concept, no evidence levelJacobian matrixconceptTangent line, concept, no evidence levelTangent lineconceptNorm induced by an inner product, definition, no evidence levelNorm induced by an in…definitionOrthogonal complement, definition, no evidence levelOrthogonal complementdefinitionDirect sum of subspaces, definition, no evidence levelDirect sum of subspac…definitionNewton's method, concept, no evidence levelNewton's methodconceptA space is the direct sum of a subspace and its orthogonal complement, statement, no evidence levelA space is the direct…statementProjection, definition, no evidence levelProjectiondefinitionOrthogonal projection, definition, no evidence levelOrthogonal projectiondefinitionOrthogonal projection is the closest point, statement, no evidence levelOrthogonal projection…statementLeast squares, concept, no evidence levelLeast squaresconceptGauss–Newton algorithm, statement, no evidence levelGauss–Newton algorithmstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Euclidean space object
  2. Function concept
  3. Limit point of a set definition
  4. Lipschitz continuity definition
  5. Matrix definition
  6. Rate of convergence concept
  7. Vector space definition
  8. Total derivative concept
  9. Function of several variables concept
  10. Limit of a function definition
  11. Transpose definition
  12. Inner product definition
  13. Linear map definition
  14. Linear subspace definition
  15. Norm definition
  16. Partial derivative concept
  17. Derivative definition
  18. Inner product space definition
  19. Orthogonal vectors definition
  20. Endomorphism definition
  21. Sum of subspaces definition
  22. Jacobian matrix concept
  23. Tangent line concept
  24. Norm induced by an inner product definition
  25. Orthogonal complement definition
  26. Direct sum of subspaces definition
  27. Newton's method concept
  28. A space is the direct sum of a subspace and its orthogonal complement statement
  29. Projection definition
  30. Orthogonal projection definition
  31. Orthogonal projection is the closest point statement
  32. Least squares concept
  33. Gauss–Newton algorithm statement

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm
About this page
TagCYV4T43FQJ
URIm2://CYV4T43FQJ
Kindstatement, theorem
WritingW0 stub
MSC65K10, 90C30, 62J02
StatusThis copy of the site has no build data. Run m2 status CYV4T43FQJ.
AboutNonlinear regression
UsesJacobian matrix, Least squares, Newton's method, Lipschitz continuity, Rate of convergence
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by