0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – littleO Apr 6 '16 at 8:37
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – GalaxyVintage Apr 7 '16 at 1:37
0
$\begingroup$

The equation you write gives you the best fit solution, which is not necessarily a line.

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$$

$\endgroup$

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.