Advantage of the matrix form of the least squares problem My professor mentioned in the lecture that minimizing $\|Ax−b\|$ is equivalent to solving the linear system $$\begin{bmatrix}
-I & A\\
A^T & 0
\end{bmatrix}
\begin{bmatrix}
r\\
x
\end{bmatrix} =
\begin{bmatrix}
b\\
0
\end{bmatrix}, $$
where $r = b-Ax.$ 
Can somebody elaborate on why this is true and what are the advantages of writing the least square problem in this way? What is the relationship between the optimization problem and the solution of the linear system?
 A: The matrix equation given in the question tells us that $-r + Ax = b$ (in other words, $r = Ax - b$) and that $A^T r = 0$. Combining these two equations, we obtain $A^T (Ax - b) = 0$, which is the well known "normal equations" for solving a least squares problem.
One potential advantage of the equation given in the question is that if $A$ is sparse, then the coefficient matrix
$$
\begin{bmatrix} -I & A \\ A^T & 0 \end{bmatrix}
$$
is still sparse, whereas the matrix $A^T A$ appearing in the normal equations might be dense. Also, if $A$ has many more columns than rows, then $A^T A$ is a large dense matrix, which potentially takes up much more memory than $A$ itself.
A: In general, if $A x = b$ has an exact solution, then
\begin{align}
x = A^{-1} b
\end{align}
However, if $A x = b$ does not admit an exact solution, we can still find $x$ that minimizes the residual. Then,
\begin{align}
r &=  Ax -  b \\
A^T r &= A^T A x - A^T b \\
0 &= (A^T A)^{-1} A^T A x -  (A^T A)^{-1} A^T b
\end{align}
the last line above follows from the fact that the residual is orthogonal to $A^T$ when the residual is minimized, i.e., in that case
\begin{equation}
A^T r = 0
\end{equation}
  This is known as the orthogonality principle. See https://en.wikipedia.org/wiki/Orthogonality_principle 
Therefore,
\begin{align}
x = (A^T A)^{-1} A^T b
\end{align}
The latter is the pseudo-inverse of $A$ times $b$.
In the matrix form proposed in your post, you wrote in a compact way the two key equations above, which are:
\begin{align}
 r&=Ax - b \\
 A^T r&=0.
\end{align}
Due to the orthogonality principle, solving the two equations above is equivalent to solving
\begin{align}
  \min_x r = Ax - b
\end{align}
and the solution is given by the pseudo-inverse.  It is very convenient to rewrite the solution of an optimization problem as the solution of a set of linear equations, for which many known methods are available. 
