Least squares in matrix form demonstration

Question

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.

Answer 1

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$.