Linear algebra least squares - explanation

Question

Suppose we have a system of equations $Ax=b$ which has no solutions. Then, we need to find a certain $\bar{x}$ such that $A\bar{x} - b$ is minimal. Apparently this $\bar{x}$ we're looking for is a solution to the equation $A^TAx = A^Tb.$ This has something to do with projections and orthogonality but I don't understand how and why. I have tried looking online but I can't find intuitive explanations (i.e. geometric) or simple derivations as to why $\bar{x}$ must satisfy $A^TAx = A^Tb.$ (where the transpose comes from, etc.) One explanations I'm looking at states it as follows:

$Ax-b$ is the orthogonal projection of the zero vector $0$ on the set of vectors of the form $Ax-b, x \in \mathbb{R^n}$. It is characterized by the condition that $A\bar{x} -b$ is orthogonal to all vectors $Av, v \in \mathbb{R^n}$.

But I really don't understand what is meant by this. Can anyone clear this passage (or the equation itself) up for me?

Answer 1

You want to find the $x$ that minimizes the distance between $Ax$ and $b$, that is, you want to find x such that

$$ f(x) = || Ax - b|| = (Ax - b)^T(Ax -b) $$

is minimum. A possible solution to this problem is to find $x$ such that $\nabla f(x) = 0$:

$$ \nabla f(x) = 2(A^TA x - A^T b) $$

The solution to the problem is then reduced to solving

$$ A^TA x = A^Tb $$

Answer 2

Consider the projection $b'$ of $b$ on the range of $A$ (call it $R$). Splitting $b$ in $b'$ and $b_p$ gives $b = b' + b_p$, where $b_p$ is orthogonal to $R$ and is a measure for the error. This error is as small as possible if the length of $b_p$ is as small as possible and that is the case if $b_p$ is perpendicular to $R$.

Because $b'$ lies in $R$, $Ax = b'$ is solvable.

We have to solve $Ax = b'= b - b_p$. Since $b_p$ is orthogonal to $R$, the inner product of the column vectors of $A$ and $b_p$ equals zero (i.e. $b_p$ is in the null space of $A^T$). In matrix notation $A^T b_p = 0$.

Multiplying both sides of $Ax = b'= b - b_p$ with $A^T$: $A^T Ax = A^T (b - b_p) = A^T b - A^T b_p = A^T b$.