Least-squares problems

Solve $x^{\ast }={\text{argmin}}_x\Vert Ax-b{\Vert }_2$ where $A$ has size $m\times n$.

Because we use the 2-norm, the solution is found when $Ax-b\perp \text{span}(A)$ (Pythagorean theorem).

This is equivalent to the equation

$$\begin{array}{c}{A}^T(Ax-b)=0\\ (A^{T}A)x=A^{T}b\end{array}$$

See dot product and orthogonality.

This equation is a linear equation in $x$ with a square matrix $A^{T}A$.