# How to understand least squares solution?

Given a linear system $Ax = b$ in $R^{2}$ where there are more equations than the unknowns, we can find the best fit line by solving $x = (A^{T}A)^{-1}A^{T}b$.

I understand how I can project a vector $v$ onto a subspace $W$ and how $x - proj_{w}x$ is the shortest distance, but I can't connect this to the best fit line. How does projecting $b$ onto the $col(A)$ give us the best fit line?

• Least squares is useful not only for line fitting, but any time you have an overdetermined linear system $Ax = b$ that you want to "solve". If your goal is to fit a line to some data, do you know how to write $A$ explicitly in terms of your data points? – littleO Apr 6 '16 at 8:37

Let $n$ the number of equations and $p$ the number of unknowns. So $A$ is a $n\times p$ matrix, $x$ is a $p\times 1$ vector and $b$ is a $n\times p$ vector, with $p<n$.
Finding the best fit in a least square sense if finding $x$ that minimizes $\|Ax-b\|_2^2$. But we have $$\min_{x\in\mathbb{R}^p}\|Ax-b\|_2^2=\min_{y\in col(A)}\|y-b\|^2_2$$ because $col(A)=\{Ax,x\in\mathbb{R}^p\}$. And as you know, the solution of this minimization problem is given by the orthogonal projection of $b$ on $col(A)$.
So $y=Hb$ where $H$ is the matrix of the orthogonal projection over $col(A)$. Now you can check that this matrix is given by $H=A(A^TA)^{-1}A^T$. So we want $x$ such that $Ax=A(A^TA)^{-1}A^Tb$. Then if $A$ is full rank, the unique solution is given by $x=(A^TA)^{-1}A^Tb$.
• Thanks a lot for the answer. I couldn't think of a way to understand how it works. But after you mention the goal is to minimize $b- Ax$, everything makes sense now. – GalaxyVintage Apr 7 '16 at 1:37
If you want to understand why $x=(A^T A)^{-1}A^T b$, there is a simple derivation that shows that $x=(A^T A)^{-1}A^T b$ minimizes the square error, i.e. that it gives the best-fit solution: $$x = \text{argmin} |b-A x|^2 \leftrightarrow x=(A^T A)^{-1}A^T b$$