Gauss-Newton Method: Brief Overview

Regression Analysis >

What is the Gauss-Newton Method?

The Gauss-Newton method is an iterative algorithm to solve nonlinear least squares problems. “Iterative” means it uses a series of calculations (based on guesses for x-values) to find the solution. It is a modification of Newton’s method, which finds x-intercepts (minimums) in calculus. The Gauss-Newton is usually used to find the best fit theoretical model although it could also be used to locate a single point.

This algorithm is probably the most popular method for non-linear least squares. It does however, have a few pitfalls:

  • If you don’t make a good initial guess, it will be very slow to find a solution and may not find one at all.
  • The procedure is not-suited for design matrices that are ill-conditioned or deficient in rank.
  • If relative residuals are very big, the procedure will lose a large amount of information.

Software Options for the Gauss-Newton Method

Any non-linear least squares procedure is going to be “considerably more difficult” (Hartley) to find by hand than its linear counterpart (which is challenging enough). The Gauss-Newton method is no exception: It requires finding Jacobian matrices and many partial derivatives. It may, in some cases, take hundreds of iterations to find a solution (assuming one exists). Therefore, it is almost exclusively performed with software. The basic steps that the software will perform (note that the following steps are for a single iteration):

  1. Make an initial guess x0 for x,
  2. Make a guess for k = 1,
  3. Create a vector fk with elements fi(xk),
  4. Create a Jacobian matrix for Jk
  5. Solve (JTkJkpk = -JTkfk). This gives you the probabilities p for all k.
  6. Find s. F(xk + spk) should satisfy the Wolfe conditions (these prove that step-lengths exist).
  7. Set xk+1 = xk + spk.
  8. Repeat Steps 1 to 7 until convergence.

At the time of writing (August, 2017), SPSS does not have the procedure. Other options include:

  • MATLAB: Woodrow Herman at the Stanford Center For Computer Research In Music and Acoustics provides some nice code for the calculation steps (click here for the pdf), along with some (relatively) simple to follow instructions. Note that you’ll really need to know some calculus and matrix algebra basics to follow along.
  • Minitab: The Gauss-Newton algorithm is the default for least squares estimation.
  • R: The default non-linear least squares algorithm is the Gauss-Newton. Other options are plinear for the Golub-Pereyra algorithm (for partial LLS), or port for the nl2sol algorithm from the Port Library.

Variations

Many variations of Gauss-Newton exist, most of which use different ways to calculate an appropriate step size or improve the accuracy of the approximated Hessian Matrix.

  • The damped Gauss-Newton (sometimes called Hartley’s method or the modified GM) improves the basic method with a line search.
  • >The Levenberg-Marquadt (LM) searches for a “trust region” and gives both the direction and distance for the next step. It performs particularly well for ill-conditioned problems (Jelali & Kroll, 2012).

More examples of some different variations can be found in Gill & Murray (1978).

References:
ETH Zurich. Nonlinear Least Squares. Retrieved 8/20/2017 from: https://stat.ethz.ch/R-manual/R-devel/library/stats/html/nls.html
Gill, P. & Murray, W. Algorithms for the solution of the non-linear least squares problem. SIAM J. Numer. Anal. 15, no.5 (1978), 977-992.
Hartley, H. The Modified G-N method for the fitting of non-linear regression functions by least squares. Technometrics 3, no. 2 (1960). 269-280.
Herman, W. Applications of the Gauss-Newton Method. Retrieved 8/20/2107 from: https://ccrma.stanford.edu/~wherman/tulane/gauss_newton.pdf
Encyclopedia of Optimization. Springer Science & Business Media, 2001.
Jelali, M. & Kroll, A. (2012). Hydraulic Servo-systems: Modelling, Identification and Control. Springer Science.


Comments? Need to post a correction? Please Contact Us.