1
$\begingroup$

I'm trying to understand least squares through linear algebra and projection. Specifically the normal equations and $A^{T}Ax = A^{T}b$. I can work through several lines of reasoning including the calculus derivation and simply solving the equations $Ax + e = b$ where $A^{T}(b - Ax) = 0$. The logic behind both these are clear. I am trying to understand why simply multiplying both sides of the equation $Ax = b$ by $A^{T}$ gives the right answer. I came across this question/answer which really helped, but still left me somewhat confused. My understanding so far amounts to this:

  1. The vector $b$ can be broken down into two components, one that is in the column space of $A$ and another that is in the left null space of A, $N(A^{T})$. We are interested in solving $A\hat{x} = b^{C(A)}$, where $b^{C(A)}$ is the projection of $b$ onto the column space of $A$. In fact, if we construct a matrix $[N \space A]$ where $N$ is a basis for $N(A^{T})$ and solve $[N \space A]x = b$ the components of $x$ that multiply the $A$ block of the matrix are the least squares estimates.

  2. When we multiply $b$ by $A^{T}$, the component of $b$ in the left null-space is projected to zero, under the linear transformation of $A^{T}$ both $b$ and $b^{C(A)}$ are mapped to the same vector (I am assuming here that $m > n$ for $A$).

  3. Because linear transformations preserve $L(ab + cd) = aL(b) + cL(d)$ when we solve for $\hat{x}$ after applying $A^{T}$ the same vector $\hat{x}$ should also solve the system $A\hat{x} = b^{C(A)}$.

Number 3 above is where my understanding is a little shaky. I don't necessarily understand how these transformations that aren't one to one work. My best guess is that if we were to somehow undo the $A^{T}$ transformation we would map the zero vector back to the zero vector and the vector $b$ would be mapped back to $b^{C(A)}$. This would reason that solving $A^{T}A\hat{x} = A^{T}b$ is equivalent to solving $A\hat{x} = b^{C(A)}$, which turns out to be the correct method. This is really the crux of my question, there are infinitely many vectors the application of $A^{T}$ maps to the same vector, I don't understand why solving $A^{T}A\hat{x} = A^{T}b$ finds the right $\hat{x}$ for the vector we're looking for in the higher dimensional space before we apply the transformation.

Thanks

$\endgroup$
  • $\begingroup$ I'm not sure if this answers your question, but if you expand out the terms in the expression $\|Ax-b\|^2$ you will see how the $A^T$ appears. $\endgroup$ – copper.hat Apr 26 '17 at 15:06
  • $\begingroup$ Yes, I can follow the algebra to see where the $A^{T}$ appears from the usual line of reasoning where we find $\hat{x}$ s.t. $(Ax - b)$ is orthogonal to $A$. I really like the linear transformation way of thinking about matrix multiplication and was hoping that there was some intuitive link between that process and multiplying $A\hat{x} = b$ by $A^{T}$ to solve for $\hat{x}$ that would easily explain what was going on. $\endgroup$ – jwilson Apr 26 '17 at 18:23
  • $\begingroup$ Well, this probably won't help, but you can view it as a consequence of the chain rule. If $f$ is differentiable, then the derivative of $x \mapsto {1 \over 2} \|f(x)\|^2$ is $f(x)^T {\partial f(x) \over \partial x}$. In the above case, $f(x) = Ax-b$, ${\partial f(x) \over \partial x} = A$, so you can see how the transpose gets introduced. $\endgroup$ – copper.hat Apr 26 '17 at 19:20

Your Answer

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

Browse other questions tagged or ask your own question.