In Chapter 7.1, we asked how close Ax can get to b when there is no exact solution. All possible outputs lie in colsp(A), so we want the closest vector in that subspace. Orthogonal projection will turn this geometric question into a system of equations.
from least_squares_visuals import show_png, show_projection, show_squared_error_explorer
Recall from Chapter 2.3 that the closest point on a line is found by dropping a perpendicular. The same idea works for any subspace.
show_projection()
Loading...
This is a schematic picture of the projection. Our four-observation example has output vectors in R4.
Why is the projection closest? For any other vāV, the difference pāāv lies in V, while bāpā is perpendicular to V. These form the two legs of a right triangle. By the Pythagorean theorem,
ā„bāvā„2=ā„bāpāā„2+ā„pāāvā„2.
Moving away from pā within the subspace adds the nonnegative second term to the squared distance. Equality holds only when v=pā.
For least squares, V=colsp(A) and pā=Axā. The following error vector must therefore be perpendicular to the column space:
We only need to check that the error vector is perpendicular to each column of A. Any linear combination of those columns will then be perpendicular to it too.
Write the columns as a1ā,ā¦,adā. The conditions are
a1āā r=0,ā¦,adāā r=0.
Multiplication by AT calculates exactly these dot products:
ATr=ā£ā”āa1āā rā®adāā rāā¦ā¤ā.
Thus, the single matrix equation
ATr=0ā
says that the error vector is perpendicular to the entire column space.
If A has shape nĆd, this is a system of d equations in d unknowns. The normal equations always have a solution. The closest output Axā is unique; the coefficients xā are unique exactly when the columns of A are independent.
Each choice of intercept c and slope m gives a line on the left. The dashed segments show the vertical errors. On the right, the pink dot records the same choice of c and m, with height ā„rā„2, the sum of squared errors.
Try c=0 and m=1, then c=2 and m=1. Both choices give squared error 8. What happens if you set c=1 and keep m=1? Use the sliders to see how changing either coefficient moves the dot on the surface.
The mean squared error is the sum of squared errors divided by the number of observations, here 4. This rescales the height of the surface, so both objectives reach their minimum at the same line. The normal equation tells us where that minimum is without having to search with the sliders.