# Linear vs non-linear Least Squares

I am trying to understand the difference between linear and non-linear Least Squares. In the book I have it says:

If the parameters enter the model linearly then one obtains a linear LSP."

If the parameters enter the model in a non-linear manner, then one obtains a nonlinear LSP."

What does that mean?

The book gives the following definitions:

Linear LSP:

$$min \space \frac{1}{2} (Ax-b)^T(Ax-b)$$

nonlinear LSP:

$$min \space \frac{1}{2} \sum (h_i(x))^2$$

Both of those formulations seem non linear to me. Can someone explain the difference?

A least squares problem is a problem where you look for the solution to

$$\text{minimize}_{x\in \mathbb{R}^n} \sum_{i} f_i(x)^2$$

where the $$f_i$$ are real-valued functions of the vector of parameters $$x$$. If all the $$f_i$$ are affine functions (that is, linear plus a constant term) of $$x$$, then this is called linear least squares problem. If any of the $$f_i$$ is not affine then this is a nonlinear least squares problem.

In your example, in fact, the inner product between the residual and itself gives the sum of the squares of the single residuals, each one being an affine function of the vector variable: $$f_i(x) = a_i^T x - b_i,$$ where $$a_i^T$$ is the i-th row of matrix $$A$$, and $$b_i$$ is the i-th coefficient of vector $$b$$. Therefore this is a linear least squares problem.

Your second example instead is a nonlinear least squares problem in general, without further assumptions on the $$h_i$$.

Bottom line Linearity is not in the function to be minimized, but in the function giving the residuals. Linear least squares problems, in fact, consist of the minimization of a quadratic function.

• Note that it is possible to solve a linear least squares problem by solving a linear system of equations (the normal equations) or by using an orthogonal factorization of $A$ (QR or SVD.) Nonlinear least squares problems are solved by iterative methods. Jan 4, 2016 at 16:03
• I think you should add a word about the existence of Minimizer (Unique / Global) and Local Minimum Points.
– Royi
Aug 5, 2016 at 13:28
• I could, but it's outside the scope of the question which looks pretty much answered like this Aug 6, 2016 at 18:58
• @LorenzoStella What do you mean by "Your second example instead is a nonlinear least squares problem I general"?
– user168764
Apr 12, 2017 at 16:13
• I mean that it is linear least squares if all the h_i are linear, and nonlinear least squares otherwise. Apr 13, 2017 at 17:58
1. For both cases, we solve a quadratic loss function - (actual - predicted(beta, x))^2 and therefore, it is called least square.

2. Note that in the above specification the quest is to find the beta that would produce predicted values as close as possible to actual

3. How the predicted(beta, x) look like: a. predicted(beta, x) = beta(1)*x(1) + beta(2)*x(2) + ... i.e. LHS is linear combination of betas' it is called a linear least square problem - they are popular because an analytic solution can be derived using matrix algebra. b. the above expression, by someone or for some problems, is considered a strong one. That is to say, how can you ensure that the functional form is a linear combination? the answer to this question is to use some alternative functional form that does not look like the one in a. Anytime you see the word 'non-linear', it means that it is not analytically solvable and requires some numerical routine. Also note that, you can make this piece or accurately speaking transform it to an approximate linear function via taylor series expansion. but its an approximation!