Least-squares problems

A least-squares problem is an optimisation problem with no constraints and an objective, which is as follows:

minimise

$$f_0(x)={\Vert Ax-b\Vert }_2^2=\sum _{i=1}^k(a_i^{T}x-b_i{)}^2$$

The objective function is a sum of squares of terms of the form

$$a_i^{T}x-b_i$$

 

The solution can be reduced to solving a set of linear equations,

$$f(x)={\Vert Ax-b\Vert }_2^2=(A_x-b{)}^T(Ax-b)$$

$$=((Ax{)}^T-b^T)(Ax-b)$$
$$=x^T{A}^{T}Ax-b^{T}Ax-x^T{A}^{T}b+b^{T}b$$

 

If x is a global minimum of the objective function, then its gradient is the zero vector.

$$▽f(x)=(\frac{\partial f}{\partial x_1},...,\frac{\partial f}{\partial x_n})$$

The gradients are:

$$▽(x^T{A}^{T}Ax)=2A^{T}Ax,▽(b^{T}Ax)=A^{T}b,▽(x^T{A}^{T}b)=A^{T}b$$

Calculate these gradients with respect to

$$x_1,...,x_n$$

Thus, the gradient of the objective function is

$$▽f(x)=2A^{T}Ax-A^{T}b-A^{T}b=2A^{T}Ax-2A^{T}b$$

To find the least squares solution, we can solve

$$▽f(x)=0$$

Or equivalently

$$A^{T}Ax=A^{T}b$$

So we have the analytical solution:

$$x=(A^{T}A{)}^{-1}{A}^{T}b$$

 

To recognise an optimisation problem as a least-squares problem, we only need to verify that the objective is a quadratic function.