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.