Non-Linear Least Squares (NLS)

While linear least squares provides a closed-form solution for fitting linear models, many real-world problems involve non-linear models. A common example is fitting a Gaussian function to a set of observations.

Given a set of $m$ observations $(x_i,y_i)$, we want to find the parameters $\beta =[a,\mu ,\sigma {]}^T$ that best fit the non-linear model:

Since this function is non-linear in its parameters, we cannot solve it directly. Instead, we must use an iterative optimization algorithm like the Gauss-Newton method.

The Gauss-Newton Algorithm

The core idea is to start with an initial guess for the parameters and iteratively refine it by solving a sequence of linear least-squares problems.

1. Start with an initial estimate for the parameters, ${\beta }_0=[a_0,{\mu }_0,{\sigma }_0{]}^T$.

2. At each iteration, we linearize the non-linear function $f(x,\beta )$ around the current estimate ${\beta }_t$ using a first-order Taylor series expansion:

where $\delta \beta =\beta -{\beta }_t$ is the update step we want to find, and $J$ is the Jacobian matrix of $f$ with respect to the parameters $\beta$:

3. We can now write the error (or residual) for each observation $i$ as:

This is a linear system of the form ${\mathbf{y}}_{new}=J\delta \beta$, where ${\mathbf{y}}_{new}$ is the vector of residuals. We can stack the equations for all $m$ observations:

4. We solve this linear least-squares problem for $\delta \beta$ using the normal equations:

5. Update the parameter estimate for the next iteration:

6. Repeat steps 2-5, linearizing around the new estimate ${\beta }_{t+1}$, until the change in parameters $||\delta \beta ||$ is below a small threshold $ϵ$, or a maximum number of iterations is reached.

Levenberg-Marquardt (LM) Algorithm

The Gauss-Newton algorithm can be unstable if the Jacobian $J$ is ill-conditioned. The Levenberg-Marquardt (LM) algorithm is a more robust alternative that adds a damping factor $\lambda$ to the normal equations. This helps to control the step size and direction, making convergence more reliable.