How to minimize $f(x) = \|Ax-b\|$ Solve the problem of minimizing $f(x) = ||Ax-b||$. Consider all the cases and interpret geometrically.
If we write
$$\|Ax-b\| = (a_{11}x_1 + \cdots + a_{1n}x_n - b_1)^2 + \cdots +  (a_{n1}x_1 + \cdots + a_{nn}x_n - b_1)^2$$
then
$$\frac{\partial \|Ax-b\|}{\partial x_j} = 2(a_{11}x_1 + \cdots + a_{1n}x_n - b_1)a_{1j} + \cdots +  (a_{n1}x_1 + \cdots + a_{nn}x_n - b_1)a_{nj}$$
If I try to do $\frac{\partial \|Ax-b\|}{\partial x_j} = 0$ I get nothing useful. For $x$ to be a minimizer, I have to have gradient $0$ and hessian positive definite. If we do the hessian just to see:
$$\frac{\partial^2 \|Ax-b\|}{\partial x_k\partial x_j} = 2a_{1k}a_{1j} + \cdots + 2a_{nk}a_{nj}$$
I see nothing useful here. 
I think the geometric interpretation comes from the conditions for the gradient to be $0$ and the hessian to be $>0$, but I don't find these conditions useful. 
Any ideas?

\begin{eqnarray*}
\left \lVert Ax-y\right\rVert^{2} &=& x^{T} A^{T} A x -2 y^{T} A x + y^{T} y
\end{eqnarray*}
Gradient w.r.t $x$ to $0$ translates to 
\begin{eqnarray*}
\nabla_{x} \left \lVert Ax-y\right\rVert^{2} &=& 2 A^{T} A x - 2A^{T} y =0
\end{eqnarray*}
yields, the normal equations. The solution is (the well known Least Square).
\begin{equation*}
\hat{x}_{LS} = \left(A^{T} A \right)^{-1} A^{T} y
\end{equation*}
Geometrically, the least square solution can be viewed as an (orthogonal) projection of the observation $y$ onto the image of $A$.
