Non-Linear Least Squares

Gauss-Newton Method

This is a second-order method. Compared with Newton’s method, Gauss-Newton uses $J{J}^T$ as the approximation of the Hessian Matrix.

As a reminder from Non-Linear Least Squares, our goal is to minimize $\frac{1}{2}\Vert f(x){\Vert }^2$ in the least squares formulation, which we will proceed by finding a $\Delta x$ such that $\frac{1}{2}\Vert f(x+\Delta x){\Vert }^2$ is minimized.

$f(x+\Delta x)\approx f(x)+J(x{)}^T\Delta x$

We take the derivative of the above formula with respect to $\Delta x$ and set it to zero (this is essentially linearizing the problem): $J(x)f(x)+J(x)J^T(x)\Delta x=0$

Rearranging the terms, we get $J(x)J^T(x)\Delta x=-J(x)f(x)$ So we have

• $H=J{J}^T$
• $g=-Jf$

Wait… but $f$ isn’t linear, how is $g$ computed? Oh this is fine, it’s just a multiplication that you expand, right? - $J$ is $n\times n$, $f$ is $n\times 1$, so $g$ is $n\times 1$

Gauss-Newton Method

1. Give an initial value $x_0$.
2. For $k$-th iteration, calculate $J(x_k)$ and residual $f(x_k)$.
3. Solve the normal equation $H\Delta x_k=g$ (solve through Gaussian Elimination).
4. If $\Delta x_k$ is small enough, stop the algorithm. Otherwise, let $x_{k+1}=x_k+\Delta x_k$ and return to step 2.

Related

• Newton’s Method
• Levernberg-Marquatdt Method