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?

  • 2
    $\begingroup$ 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. $\endgroup$ Nov 8 '18 at 3:09
  • $\begingroup$ $x=(A^{\rm T}A)^{-1} Ab$ is such that the distance $||b-Ax||_2$ is minimal. $\endgroup$
    – Rócherz
    Nov 8 '18 at 3:12
  • $\begingroup$ 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? $\endgroup$ Nov 8 '18 at 4:05
  • $\begingroup$ What do you mean by "absolute error"? $\endgroup$
    – littleO
    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.

  • $\begingroup$ @ccorn too right - fixed. I've been using $E = \frac{1}{2}\Delta^2$ too much lately... $\endgroup$ Nov 8 '18 at 3:32

You can think it through a geometric way. b is certainly not in the column space, but since the left-null space is the orthogonal component of the column space. We can divide b into two parts: b= b(column part) +b(left-null part). since the multiplication of the transpose of A and b(left-null part) is 0 , we can get Ax=b(column part). And b(column part) is the projection from b to the column space, which is closest to b


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.