Recently in my lectures we did Householder reflectors and normal equations to solve $Ax = b$, with $A$ being a rectangular $m\times n$ matrix and $x$ being a $m\times 1$ vector, where $m>n$. Or maybe more accurately to minimize the norm of the residual $r = Ax -b$.

Now I know how to do this, but I lack intution on why this works and why simple projecting doesn't work, i.e. let's say $A$ has columns $a_1, a_2, ... a_n$, then to find the least squares problem why isn't it enough to let $x_i = \langle\,a_i,b\rangle \frac{1}{\left\|a_i\right\|^2}$ for $i = 1, 2,... m$?

I see I am doing something similar through normal equations i.e. multiplying both sides by $A^t.$
I am again dot producting columns of $A$ with $b,$ and then $(A^tA)^{-1}$ seems to be the normalization, but it doesn't work out to be the same.

  • $\begingroup$ Note that m \times n gives you $m \times n$ as opposed to $mxn$ $\endgroup$ – Omnomnomnom May 7 at 21:52
  • $\begingroup$ Try a small example. Take $m=3,n = 2$. See what happens when $a_1,a_2$ are not perpendicular to each other. $\endgroup$ – Omnomnomnom May 7 at 22:42
  • $\begingroup$ Thanks for the reply! I really can't see to figure this out. We had a theorem that the residual is minimized when $A^t r = 0$. Now let's say $b = \alpha*a_1 + \beta*a_2 + \gamma*a_3$, where $a_1, a_2$ are linearly independent columns of A and $a_3$ is perpendicular to $a_1, a_2$ found using the cross product for example. Now you have $r = b - \alpha*a_1 - \beta*a_2 = \gamma*a_3$ and this times $A^t$ will clearly be 0. Now don't we find $\alpha, \beta, \gamma$ using exactly the dot product? $\endgroup$ – analysis1 May 8 at 8:58
  • $\begingroup$ We do not. To clarify my earlier comment, my recommendation was that you consider a numerical example where $a_1,a_2$ are not perpendicular so that you can verify that the dot-product formula fails to produce the correct result. For instance, take $a_1 = (1,0,0)^T$ and $a_2 = (1,1,0)^T$. $\endgroup$ – Omnomnomnom May 8 at 13:46
  • $\begingroup$ Yup, I have now verified it, thanks a lot $\endgroup$ – analysis1 May 8 at 19:41

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.