The information presented here is based off the Wikipedia pages on Gauss-Newton.
The Gauss-Newton algorithm is a simple method for solving non-linear least square problems, typically expressed mathematically as:
where S is the sum of the residuals. The residual, r, is the difference between the actual observed value and the value predicted by the model:
- y is the observed value
- x is the input value
- f is the function that we are trying to fit the data to
- is the parameters of the model that we are trying to find, to minimise S
Starting with an intial guess , the Gauss-Newton algorithm will iteratively find the best values for as follows:
can be thought as the “correction” applied to to get it closer to the solution. in terms of the Jacobian matrix of f is:
is the transpose of the matrix and is the inverse of the matrix.
I don’t know about most people, but whenever I see a bunch of matrix symbols clumped together it more than often leaves me in a state of confusion, particularly the matrix dimensions. For a better understanding of the matrices I’ll illustrate with an example. Suppose we want to do a quadratic fit to a set of data containing 100 points. A quadratic function has 3 parameters (A, B, C):
thus the Jacbobian is 100×3 and the residual matrix, r, is 100×1, ends up a 3×3 matrix.
One important note about the algorithm is that there is no guarantee it will converge. Each iteration will not necessarily improve the sum of residual. You can see this behaviour in my demo code. A plot of the mean square error vs iterations for my demo code is illustrated in the graph below. The code tries to fit the function , which is sensitive to the initial estimate.
It is important to initialise the algorithm close to the true parameter value as possible, this will improve your chances of finding the correct solution.
You’ll need OpenCV 2.x installed. In Linux just type make to compile and run. Replace the function Func() with your own one to play around with.
The program is very minimal and should be more or less self explanatory from the code, hopefully.