1

Can anyone give some guidance with the following question:-

Prove that the Gauss-Newton Method applied to a linear system $Ax=b$ converges in one step to the solution of the normal equations

user76020
  • 123
  • What are the normal equations? – Daniel Donnelly Nov 10 '13 at 17:45
  • There are no normal equations, rather it's just a proof – user76020 Nov 10 '13 at 18:06
  • Wt... I don't understand you. – Daniel Donnelly Nov 10 '13 at 18:21
  • This is the whole question, we are asked to prove that if we use the Gauss-Newton Method (which is used for non-linear systems) with a linear system it converges in one step to the solution of the normal equations. – user76020 Nov 10 '13 at 18:26
  • Normal equations are the linear regression estimating equations: $X^T(Y-XB)$. – AdamO Oct 28 '14 at 03:41
  • With Gauss-Newton, the sum of sum os sqaured errors: $$ \Vert (b-Ax)\Vert^2 = (b-Ax)^T(b-Ax) $$ is minimized. The Jacobian, $J$, of the error ($b-Ax$) w.r.t. the parameters ($x$) is $J = -A$, so the normal equations are: $$A^\top A \Delta x = A^\top(b-Ax) $$ with solution: $$\Delta x = (A^\top A)^{-1}A^\top(b-Ax)=A^{-1}(b-Ax)$$ Plugin this into the original equation: $$ A (x + \Delta x) = A (x + A^{-1}(b-Ax))=Ax + b - Ax = b$$ Therefore solving the problem in one step. – Javier TG Aug 19 '22 at 18:35

2 Answers2

1

Let $f$ be a function, in this case $f(x) = A x - b$. Then, with $p_n$ as the $n$-th iterand, this is Newton's method:

$y - f(p_n) = f'(p_n).(x - p_n)\;$ where $\;y = 0\;$ and $\;x = p_{n+1}\;$.

It's easy to see that $f'(x) = A$, so: $$A (p_{n+1} - p_n) = - (A p_n - b) $$ Start with $n=0$. Can you proceed from here?

Han de Bruijn
  • 17,070
  • Isn't this using Newtons Method and not Gauss-Newton? – user76020 Nov 10 '13 at 19:09
  • I've consulted Wikipedia http://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm which says the following: "if $m = n$ the iteration simplifies to [ .. ] a direct generalization of Newton's method in one dimension". But I'm not quite sure about $(m,n)$ of your matrix $A$. – Han de Bruijn Nov 15 '13 at 21:31
  • Here's the answer from our professor:- let $r=b-Ax$, we have $Dr=-A$, The Newton-Gauss formula - $A^TAv^0 = A^T(b-Ax^0)$ and $x^1 = x^0 + v^0$, we have $A^TA(x^0+v^0)=A^Tb$ and the solution is $x^1$ – user76020 Nov 17 '13 at 12:45
  • Yes, that was my second thought too. If $A$ has an inverse, I said: if , then you can multiply on the left with $A^{-T}$ and have $A x^1 = b$ , but in general your professor is quite right. – Han de Bruijn Nov 18 '13 at 15:23
0

The normal equations are:

$$ \mathbb{G}(\beta) = X^T(Y-X\beta)$$

The Gauss Newton method has that the root of $\mathbb{G}$ is iteratively found by:

$$\beta^{(1)} = \beta^{(0)} + \left( \frac{\partial \mathbb{G}}{\partial \beta} \right)^{-1} \mathbb{G}(\beta^{(0)})$$

Choose $\beta=0$. This gives you the usual OLS estimate and you can verify by plugging it into $\mathbb{G}$ that it is indeed the root.

AdamO
  • 105