# Why does solving $A^{\rm T}Ax = A^{\rm T}b$ yield a least squares approximation?

I was following a linear algebra course, and I came upon an example where a linear regression was done by solving $$A^{\rm T}Ax = A^{\rm T}b$$, where $$Ax = b$$ could not be solved because $$b$$ is not in the column space of $$A$$. So the formula $$A^{\rm T}Ax = A^{\rm T}b$$ is derived as the projection of $$b$$ onto the column space of $$A$$, and solved for as an approximation.

What I am confused about is where during this derivation this became a least squared approximation. How would I formulate the problem in a similar way (as a linear algebra problem), but minimize linear distance instead? (edited, from Euclidean distance which was improper use of terminology)

What I mean to ask is when fitting a line to a set of points, if I wanted to minimize the absolute error, not the squared error, how would I formulate the problem?

• It is minimizing Euclidean distance. The points to remember is that $Ax=0$ means $x$ is orthogonal to every row of $A$, hence to the whole row space. Changing to $A^T$ gives similar statement about column space. So the Nullspace of $A^T$ and the column space of $A$ are two subspaces that are orthogonal to each other. Now you can work out the connection. Nov 8 '18 at 3:09
• $x=(A^{\rm T}A)^{-1} Ab$ is such that the distance $||b-Ax||_2$ is minimal. Nov 8 '18 at 3:12
• Nov 8 '18 at 3:19
• Question edited. I meant to ask, how could I minimize the absolute error, not the squared error when fitting a line to a set of points for example? Nov 8 '18 at 4:05
• What do you mean by "absolute error"? Nov 8 '18 at 6:19

Given an approximate solution $$x$$ we can define the squared error in the approximation as $$E(x) = \| A x - b \|^2 = (Ax-b)^T(Ax-b)$$.
Finding the $$x$$ that minimises this "error" us the least squares solution.
$$E$$ has gradient $$\nabla E(x) = 2 A^T(Ax-b)$$. Also $$E$$ has a minimum when $$\nabla E = 0$$. i.e. when $$A^TAx-A^Tb = 0$$ - which is exactly the condition you want.
• @ccorn too right - fixed. I've been using $E = \frac{1}{2}\Delta^2$ too much lately... Nov 8 '18 at 3:32