Least squares: the best answer when Ax = b has no solution
Slide 3 found the closest point inside a column space. Now we use it when Ax = b has no solution, which happens all the time with real measurements. Three friends time the same runner and get three slightly different times. No single time fits all three, so everyone agrees on the best compromise: the average. Least squares does the same for any system with too many equations. It picks the x̂ that makes the total squared error ‖b − Ax‖² as small as possible. The answer is the shadow from slide 3: Ax̂ is the projection of b onto the column space, and x̂ solves the normal equations AᵀAx̂ = Aᵀb.
Lesson 5 · slide 4Least squares- Ax = b is solvable only when b lies in the column space C(A). Noisy data almost never does.
- Least squares minimizes E = ‖b − Ax‖², the sum of the squared errors.
- The best Ax̂ is the projection of b onto C(A). The error is perpendicular to every column: Aᵀe = 0.
- That condition is the normal equations AᵀAx̂ = Aᵀb.
- AᵀA is square and invertible when the columns of A are independent.
Three stopwatches, one runner
Three friends time one sprint: 10.2, 10.5 and 10.0 seconds. So x = 10.2, x = 10.5, x = 10.0. No x fits all three, but everyone would take the average, about 10.23.
That is least squares. A has one column, a = 111, and b = 10.210.510.0. Project b onto a, as on slide 2:
The average is the projection onto 111. With only two stopwatches, reading 1 and 3, we can draw it in the plane:
The general recipe
Now A has n columns and m rows, with more rows than columns (m > n). Every Ax lies in the column space, a flat subspace inside ℝᵐ (all vectors with m numbers). The data b sticks out of it. So we go to the closest point we can reach: the projection p = Ax̂.
The error e = b − Ax̂ is perpendicular to every column. Stack those dot products and you get Aᵀe = 0:
We can't solve Ax = b, but when the columns of A are independent, AᵀAx̂ = Aᵀb has exactly one solution (shown below). It is only n by n, however many measurements there are.
A worked example
Fit a line to three readings: at t = 0, 1, 2 we read b = 1, 1, 4. Each reading gives one equation C + Dt = b, where C is the height of the line at t = 0 and D is its slope:
Why AᵀA has an inverse
Suppose AᵀAx = 0. Multiply by xᵀ: xᵀAᵀAx = (Ax)ᵀ(Ax) = ‖Ax‖² = 0, so Ax = 0. (Transposing a product reverses it: (Ax)ᵀ = xᵀAᵀ.) Independent columns force x = 0. So AᵀA has an inverse.
With dependent columns it fails. Take all three readings at the same time t = 1. Then both columns are 111:
Three readings at one moment say nothing about a slope. For a line fit, use at least two different times.
Keep reading with the full course
Finish lesson 5 and you will be able to: fit the best line to noisy sensor data.
Still locked here:
- The rest of this explanation
- 4 more examples with step-by-step solutions
- Five extra members-only problems with worked solutions
$20 once, lifetime access. Lessons 1 to 3 stay free.
Examples
Example 1 · The average is least squares
One unknown, three readings: x = 3, x = 5, x = 10.
Questions and comments
Stuck on something, or found a mistake? Ask here and I'll answer. You sign in with GitHub.