Least squares in matrix form demonstration I want to know why $$\min ||AX-B||^2 <=> A^tAX = A^tB$$ and I'm having a hard time finding a demonstration that I can understand. I'm pretty sure I have to start by doing $Y=AX$ and $B = B_1 + B_2$ but any attempt to go beyond that has got me stuck. 
 A: Here is one approach:
Let $S = {\cal R} A$, the range space of $A$. This is a (closed) subspace, so
we can write the problem as $\min_{s \in S} \|s-b\|^2$, that is, finding the closest point to $b$ in the subspace $S$.
Remember, for every point in $s \in S$, there is some (possible many) $x$ such that $s = Ax$.
It is straightforward to show (using a compactness argument, for example)
that the derived problem has a solution (in fact it is unique). It is also
straightforward to show that the solution $s$ satisfies
$s-b \bot S$ (draw a picture to see the geometry). That is $s$ is the orthogonal
projection of $b$ onto $S$.
To see this analytically, choose $x \in S$, then we have $\|s-b\|^2 \le \|s+tx-b\|^2$ for all $t$. If we expand this we get
$\|s-b\|^2 \le t^2 \|x\|^2 + \|s-b\|^2 + 2 t \langle s-b, x \rangle$, which gives $t \|x\|^2 + 2 \langle s-b, x \rangle$ if we divide by $t \neq 0$. Letting $t \to 0$ gives $\langle s-b, x \rangle \ge 0$. Since $-x \in S$ as well, we get $\langle s-b, x \rangle =0$ for all $x \in S$, which is
$s-b \bot S$.
In particular, we have $\langle u, s-b \rangle = 0$ for all $u \in S$.
Since $s$ has the form $s = Ax$ for some $x$ and similarly $u=Ay$, this gives$\langle Ay, Ax-b \rangle = \langle y, A^T(Ax-b) \rangle =0$. Since
this is true for all $y$, we have $A^T(Ax-b) = 0$.
