When a line cannot pass through all of our data points at once, the matrix equation Ax=b has no solution, and we need a way to find the closest line we can get.
1
Projecting Onto the Column Space
Suppose we want to fit a straight line y=mx+c through the three data points (1,1),(2,2), and (3,2), writing c for the intercept because b is already the right-hand side of Ax=b.
The first two points lock the line into place, and by x=3 that line is at height 3 instead of 2, so no choice of slope m and intercept c satisfies all three equations at once. Looking at the system by columns shows what happens in 3D space and why projecting perpendicularly onto the column space of A gives the closest line.
Why Least Squares Projects Onto the Column Space
Plugging the three points into mx+c=y and grouping the numbers by column turns the search for a line into a 3D vector equation:
1m+1c2m+1c3m+1c=1=2=2⟹m123+c111=122
Because b=122 sits off the plane spanned by the columns of A, we drop a perpendicular from b to the closest point on the plane, written with a hat to show it is the closest fit rather than an exact solution:
For any line we try, the three vertical misses e1,e2,e3 on the 2D graph are the components of the 3D error vector e=b−Ax. Their squared lengths add up to ∥e∥2, which is smallest right at b^, where e meets the plane at 90∘.
Each point on the 3D plane gives a candidate line on the 2D graph, and the spot where the 3D error vector meets the plane at a right angle makes the total area of the 2D error squares as small as possible.
2
Solving the Normal Equations for the Best Fit Line
Now we want to find the actual slope m^ and intercept c^ in x^=[m^c^] that give the projection b^ for the points (1,1),(2,2), and (3,2). Because the error vector e=b−Ax^ meets the plane at 90∘, its dot product with each column of A must be zero.
Solving the Normal Equations for the Best Fit Line
em^c^=b−Ax^=?=?
Text solution
Dot the column equation with the first column of ADotting every vector in m^123+c^111≈122 with 123 gives the first row of the normal equations:
Dot the column equation with the second column of A to form ATAx^=ATbDotting every vector with 111 simply adds the entries of each column to give the second row:
Eliminate c^ to solve for m^ and c^Doubling the second equation and subtracting it from the first cancels c^ right away:
(14m^+6c^)−2(6m^+3c^)=11−2(5)2m^=1m^=21
6(21)+3c^3+3c^3c^c^=5=5=2=32
So the best fit line that minimizes the sum of the squared vertical misses for (1,1),(2,2), and (3,2) is y=21x+32.
3
Finding the Projection, Error Vector, and Least Squares Error
Even our best fit line y=21x+32 does not pass through the three points, so we now want to find the projected vector b^=Ax^ on the plane, the error vector e=b−Ax^ of vertical misses, and the single number ∥e∥ that measures the total error of the line.
Finding the Projection, Error Vector, and Least Squares Error
1
2
3
1
2
3
x
y
(1,1)
(2,2)
(3,2)
y=21x+32
b^e∥e∥=?=?=?
Text solution
Evaluate the best fit line at x=1,2,3 to get the projection b^=Ax^The three heights from y=21x+32 give the closest vector b^ on the column space:
Subtract the line's heights b^ from the data heights b to find the error vector eSubtracting component by component gives the vertical miss at each data point:
Add the squared misses and take the square root to find the least squares error ∥e∥Using the 3D Pythagorean theorem on the components of e gives the length of the error vector:
So the shortest 3D distance from b to the column space is 61, and any other line drawn on the graph will have a least squares error larger than 61.
4
When the Least Squares Solution Is Unique
Every target vector b has a single closest point b^ on the column space, so a least squares solution always exists. Now we want to see when there is only one weight vector x^ that produces b^, and what happens when three data points are stacked vertically at (2,1),(2,2), and (2,5).
When the Least Squares Solution Is Unique
1
2
3
1
2
3
4
5
x
y
(2,1)
(2,2)
(2,5)
yx^=mx+c=[m^c^]=?
When the columns of A are linearly independent, there is only one combination x^ that gives b^, and ATA is invertible:
x^=(ATA)−1ATb
When the columns of A are linearly dependent, ATA is no longer invertible, and infinitely many combinations x^ give the exact same projection b^.
Text solution
Write Ax=b in column form for (2,1),(2,2), and (2,5)Because all three points have x=2, the first column of A is just 2 times the second column, so both columns lie on the same line in 3D space:
m222+c111=125,222=2111
Dot with 111 to find the equation relating m^ and c^ and the unique projection b^Projecting b=125 onto the line spanned by the columns gives a single equation relating m^ and c^:
So the projection b^=383838 is still unique, while any slope m^ and intercept c^ with 2m^+c^=38 gives a best fit line passing through (2,38) with the exact same vertical misses.
Every line through (2,38) has 2m^+c^=38, so the two vectors m^222 and c^111 always add up to the exact same projection b^=383838, leaving the vertical misses and the least squares error unchanged.
Every line through the average point trades slope for intercept to land on the same 3D projection, keeping the vertical misses and least squares error the same.
Key concepts
1
2
3
1
2
x
y
e1
e2
e3
y=mx+c
column space of A
b
b^=Ax^
e=b−Ax^
When you set up Ax=b to fit a line y=mx+c to data, first check whether b is already in the column space of A: if the points (1,1),(2,2), and (3,3) already lie on the line y=x, then b=123 is already 1123+0111, so Ax=b solves directly with error ∥e∥=0 and you do not need the normal equations.
When the points do not line up, b sits outside the column space of A and Ax=b has no solution. To find the closest fit, dot the column equation with each column of A to form the normal equations:
ATAx^=ATb
For (1,1),(2,2), and (3,2) with A=123111 and b=122, dotting with 123 and 111 gives [14663][m^c^]=[115], so m^=21 and c^=32.
Evaluating the line at the data points gives the projectionb^=Ax^ on the column space, subtracting gives the error vectore=b−b^ of vertical misses on the graph, and taking its length gives the least squares error∥e∥=e12+e22+e32. If you already have a vector b^ on the column space, you can skip solving ATAx^=ATb and test e=b−b^ directly: b^ is the least squares projection exactly when e has a zero dot product with every column of A.
Finally, look at the columns of A to tell whether x^ is unique. Linearly independent columns make ATA invertible, giving one best-fit solution x^=(ATA)−1ATb. Linearly dependent columns, like 222 and 111 when all points are stacked at x=2, lie on the same line and make ATA non-invertible, so infinitely many weight vectors x^ (every pair with 2m^+c^=38) give the exact same projection b^=383838 and least squares error ∥e∥.
5
Practice
1
Set up the matrix equation Ax=b and solve the normal equations ATAx^=ATb to find the best fit line y=m^x+c^ for the data points (0,1),(1,3), and (2,4).
Plug each (x,y) pair into mx+c=y to get the two columns of A and the vector b, then dot the entire equation with each column of A.
Plugging (0,1),(1,3), and (2,4) into mx+c=y gives Ax=b:
A=012111,x=[mc],b=134
Dotting the column equation m^012+c^111≈134 with 012 and then with 111 gives the normal equations ATAx^=ATb:
Subtracting the second equation from the first eliminates c^:
(5m^+3c^)−(3m^+3c^)2m^m^=11−8=3=23
Substitute m^=23 into the second equation 3m^+3c^=8 (watch out for stopping at 3c^=27 and forgetting to divide by 3, which gives the wrong line y=23x+27):
3(23)+3c^3c^c^=8=216−29=27=67
The best fit line is y=23x+67.
2
For the data points (−1,0),(0,1), and (1,4), the best fit line is y=2x+35. Find the projection vector b^=Ax^ on the column space, the error vector e=b−Ax^ of vertical misses, and the least squares error ∥e∥.
The entries of b^=Ax^ are the heights on the line y=2x+35 at x=−1,0,1. How do you get the vertical miss at each point from there?
Evaluating y=2x+35 at x=−1,0,1 gives the projection vector b^:
For A=123111 and b=435, someone claims that the vector b^=345 on the column space of A (from the line y=x+2) is the least squares projection of b. Without solving the normal equations, use the error vector e=b−b^ to check whether this claim is true.
Dotting e with the second column 111 gives 1(1)+(−1)(1)+0(1)=0, but do not stop after checking only one column (checking only 111 leads to the wrong conclusion that the claim is true).
If b^ is the perpendicular projection onto the column space, what must the dot product of e=b−b^ with each column of A equal?
First find the error vector e=b−b^:
e=435−345=1−10
Now dot e with the columns of A. Dotting e with the second column 111 gives 1(1)+(−1)(1)+0(1)=0, but do not stop after checking only one column (checking only 111 leads to the wrong conclusion that the claim is true). Dotting e with the first column 123 gives:
e⋅123=1(1)+(−1)(2)+0(3)=1−2+0=−1=0
Because e is not perpendicular to every column of A,b^=345 is not the least squares projection.
4
For the system Ax=b with A=122366 and b=036, explain why ATA is not invertible, find all least squares solutions x^=[x^1x^2], and find the unique projection b^ and least squares error ∥e∥.
Compare the second column of A to the first column to see the line they span, then dot Ax=b with 122 to find x^1+3x^2.
The second column 366 is 3 times the first column 122, so the columns of A are linearly dependent and ATA=[9272781] is not invertible.
Dotting x^1122+x^2366≈036 with 122 turns both rows of ATAx^=ATb into a single equation:
So every vector x^=[x^1x^2] with x^1+3x^2=2 is a least squares solution.
Factoring b^=x^1122+x^2366 gives the unique projection (be careful to multiply x^1+3x^2=2 by the first column 122, not the second column 366, which would give 61212 and ∥e∥=153):
b^=(x^1+3x^2)122=2122=244
Subtracting b^ from b gives the error vector and least squares error:
Three data points are at (1,2),(2,3), and (3,k). (a) For what value of k does b=23k lie in the column space of A so that the least squares error is 0? (b) For what value of k does the best fit line have slope m^=2, and what is its intercept c^?
For (a), find the height at x=3 of the line through (1,2) and (2,3). For (b), dot the column equation with 123 and 111, keeping k in ATb.
(a)The line through (1,2) and (2,3) is y=x+1, which has height y=4 at x=3, so b lies in the column space of A when k=4.
(b)With A=123111 and b=23k, dot the column equation with 123 and 111 (watch out for forgetting to multiply k by 3 when dotting 123⋅23k, which gives 8+k instead of 8+3k and leads to k=−6,c^=−313):