Least-Squares Problems

A least-squares solution is simply the best answer you can get when $A\vec x = \vec b$ has no exact answer: the $\hat x$ that makes $A\hat x$ land as close to $\vec b$ as possible. The name says what it does: it makes the sum of the squared errors as small as possible, the least. What it's good for: real data never lines up perfectly, and this is how you fit a line (or any model) through messy measurements. All we're really saying here is that in $A^TA\,\hat x = A^T\vec b$, you start from the impossible system $A\vec x = \vec b$ and multiply both sides by $A^T$. That turns it into a square system that always has a solution, and the solution is the best compromise. It looks like a trick pulled out of a hat, but there's a clean picture behind it; bear with it.

Geometry. Take a look at what $A\vec x$ can be. As $\vec x$ varies, $A\vec x$ runs over all combinations of the columns of $A$, which is the column space $\operatorname{Col}A$. If $\vec b$ isn't in there, the system has no solution. So what can we do now? The last two lessons tell you: the closest point to $\vec b$ in $\operatorname{Col}A$ is the projection $\hat b = A\hat x$.

What makes it the closest point is the right angle. The error $\vec b - A\hat x$ must be perpendicular to every column of $A$, and "dotted with every column gives $0$" is exactly $A^T(\vec b - A\hat x) = \vec 0$. Multiply it out and you get $A^TA\hat x = A^T\vec b$. That's the normal equation ("normal" is another word for perpendicular). Notice you never need an orthogonal basis of $\operatorname{Col}A$ here; the normal equations do the projecting for you.

Fitting a line $y = \beta_0 + \beta_1x$ to points $(x_i, y_i)$: each point gives a row $[1\;\;x_i]$ of the design matrix and an entry $y_i$ of $\vec b$. If the points were exactly on a line, $A\beta = \vec b$ would have a solution. They usually aren't, so the least-squares $\beta$ minimizes the sum of squared vertical errors instead.

A common mistake. It's tempting to think the best-fit line minimizes the perpendicular distances from the points to the line, because this whole unit is about perpendiculars. It doesn't. In the data picture, the errors are the vertical gaps $y_i - (\beta_0 + \beta_1x_i)$. The right angle lives in $\mathbb R^n$, between $\vec b$ and $\operatorname{Col}A$, not in the $xy$-plane where you plot the points.

There's an animation further down that shows the total squared error changing as a line swings through the data.

Every "line of best fit," from economics to lab data to the linear regression lab, is a least-squares problem; GPS receivers solve least squares to combine many satellite measurements.