Linear AlgebraOrthogonality and Projections5 of 9
Orthogonality and Projections · 5

Least Squares: The Best Fit When Ax = b Fails

When a line cannot pass through all of our data points at once, the matrix equation Ax=bAx = \target{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+cy = \firstcol{m}x + \secondcol{c} through the three data points (1,1)\data{(1, 1)}, (2,2)\data{(2, 2)}, and (3,2)\data{(3, 2)}, writing c\secondcol{c} for the intercept because b\target{b} is already the right-hand side of Ax=bAx = \target{b}.

11
22
33
11
22
33
xx
yy
(1,1)\htmlClass{lc-blue}{(1, 1)}
(2,2)\htmlClass{lc-blue}{(2, 2)}
(3,3)\htmlClass{lc-violet}{(3, 3)}
(3,2)\htmlClass{lc-blue}{(3, 2)}
1\htmlClass{lc-orange}{1}

The first two points lock the line into place, and by x=3x = 3 that line is at height 3\proj{3} instead of 2\target{2}, so no choice of slope m\firstcol{m} and intercept c\secondcol{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 AA gives the closest line.

Why Least Squares Projects Onto the Column Space
11
22
33
11
22
33
xx
yy
(1,1)\htmlClass{lc-blue}{(1, 1)}
(2,2)\htmlClass{lc-blue}{(2, 2)}
(3,2)\htmlClass{lc-blue}{(3, 2)}
y=mx+cm=  ?c=  ?\begin{aligned} y &= \htmlClass{lc-green}{m}x + \htmlClass{lc-pink}{c} \\[3pt] \htmlClass{lc-green}{m} &= \;? \\[3pt] \htmlClass{lc-pink}{c} &= \;? \end{aligned}

Plugging the three points into mx+c=y\firstcol{m}x + \secondcol{c} = y and grouping the numbers by column turns the search for a line into a 3D vector equation:

1m+1c=12m+1c=23m+1c=2⟹m[123]+c[111]=[122]\displaystyle \begin{aligned} \firstcol{1}\firstcol{m} + \secondcol{1}\secondcol{c} &= \target{1} \\ \firstcol{2}\firstcol{m} + \secondcol{1}\secondcol{c} &= \target{2} \\ \firstcol{3}\firstcol{m} + \secondcol{1}\secondcol{c} &= \target{2} \end{aligned} \quad\Longrightarrow\quad \firstcol{m}\firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} + \secondcol{c}\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} = \target{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}}

Because b=[122]\target{b} = \target{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} sits off the plane spanned by the columns of AA, we drop a perpendicular from b\target{b} to the closest point on the plane, written with a hat to show it is the closest fit rather than an exact solution:

e⏟error vector\displaystyle \underbrace{\err{e}}_{\text{error vector}} =b−Ax^⏟projection b^,∥e∥2\displaystyle = \target{b} - \underbrace{\proj{A\hat{x}}}_{\text{projection } \proj{\hat{b}}}, \qquad \err{\|e\|^2} =e12+e22+e32\displaystyle = \err{e_1^2} + \err{e_2^2} + \err{e_3^2}

For any line we try, the three vertical misses e1,e2,e3\err{e_1}, \err{e_2}, \err{e_3} on the 2D graph are the components of the 3D error vector e=b−Ax\err{e} = \target{b} - \proj{Ax}. Their squared lengths add up to ∥e∥2\err{\|e\|^2}, which is smallest right at b^\proj{\hat{b}}, where e\err{e} meets the plane at 90∘90^\circ.

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^\firstcol{\hat{m}} and intercept c^\secondcol{\hat{c}} in x^=[m^c^]\hat{x} = \begin{bmatrix} \firstcol{\hat{m}} \\ \secondcol{\hat{c}} \end{bmatrix} that give the projection b^\proj{\hat{b}} for the points (1,1)\data{(1, 1)}, (2,2)\data{(2, 2)}, and (3,2)\data{(3, 2)}. Because the error vector e=b−Ax^\err{e} = \target{b} - \proj{A\hat{x}} meets the plane at 90∘90^\circ, its dot product with each column of AA must be zero.

Solving the Normal Equations for the Best Fit Line
e=b−Ax^m^=  ?c^=  ?\begin{aligned} \htmlClass{lc-orange}{e} &= \htmlClass{lc-blue}{b} - \htmlClass{lc-violet}{A\hat{x}} \\[3pt] \htmlClass{lc-green}{\hat{m}} &= \;? \\[3pt] \htmlClass{lc-pink}{\hat{c}} &= \;? \end{aligned}
Text solution
Dot the column equation with the first column of AADotting every vector in m^[123]+c^[111]≈[122]\firstcol{\hat{m}}\firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} + \secondcol{\hat{c}}\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} \approx \target{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} with [123]\firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} gives the first row of the normal equations:
([123]⋅[123])m^+([123]⋅[111])c^=[123]⋅[122](1+4+9)m^+(1+2+3)c^=1+4+614m^+6c^=11\displaystyle \begin{aligned} & \left(\firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} \cdot \firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}}\right)\firstcol{\hat{m}} \\ &\quad + \left(\firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} \cdot \secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}}\right)\secondcol{\hat{c}} \\ &\quad = \firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} \cdot \target{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} \\ & (1 + 4 + 9)\firstcol{\hat{m}} + (1 + 2 + 3)\secondcol{\hat{c}} \\ &\quad = 1 + 4+ 6 \\ & 14\firstcol{\hat{m}} + 6\secondcol{\hat{c}} = 11 \end{aligned}
Dot the column equation with the second column of AA to form ATAx^=ATbA^T A\hat{x} = A^T \target{b}Dotting every vector with [111]\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} simply adds the entries of each column to give the second row:
(1+2+3)m^+(1+1+1)c^=1+2+26m^+3c^=5⟹[14663][m^c^]=[115]⏟normal equations ATAx^=ATb\displaystyle \begin{gathered} \begin{aligned} & (1 + 2 + 3)\firstcol{\hat{m}} + (1 + 1 + 1)\secondcol{\hat{c}} \\ &\quad = 1 + 2 + 2 \\ & 6\firstcol{\hat{m}} + 3\secondcol{\hat{c}} = 5 \end{aligned} \\[4pt] \Longrightarrow\quad \underbrace{\begin{bmatrix} 14 & 6 \\ 6 & 3 \end{bmatrix}\begin{bmatrix} \firstcol{\hat{m}} \\ \secondcol{\hat{c}} \end{bmatrix} = \begin{bmatrix} 11 \\ 5 \end{bmatrix}}_{\text{normal equations } A^T A\hat{x} = A^T \target{b}} \end{gathered}
Eliminate c^\secondcol{\hat{c}} to solve for m^\firstcol{\hat{m}} and c^\secondcol{\hat{c}}Doubling the second equation and subtracting it from the first cancels c^\secondcol{\hat{c}} right away:
(14m^+6c^)−2(6m^+3c^)=11−2(5)2m^=1m^=12\displaystyle \begin{aligned} & (14\firstcol{\hat{m}} + 6\secondcol{\hat{c}}) - 2(6\firstcol{\hat{m}} + 3\secondcol{\hat{c}}) \\ &\quad = 11 - 2(5) \\ & 2\firstcol{\hat{m}} = 1 \\ & \firstcol{\hat{m}} = \frac{1}{2} \end{aligned}
6(12)+3c^=53+3c^=53c^=2c^=23\displaystyle \begin{aligned} 6\left(\frac{1}{2}\right) + 3\secondcol{\hat{c}} &= 5 \\ 3 + 3\secondcol{\hat{c}} &= 5 \\ 3\secondcol{\hat{c}} &= 2 \\ \secondcol{\hat{c}} &= \frac{2}{3} \end{aligned}

So the best fit line that minimizes the sum of the squared vertical misses for (1,1)\data{(1, 1)}, (2,2)\data{(2, 2)}, and (3,2)\data{(3, 2)} is y=12x+23y = \frac{1}{2}x + \frac{2}{3}.

3

Finding the Projection, Error Vector, and Least Squares Error

Even our best fit line y=12x+23y = \frac{1}{2}x + \frac{2}{3} does not pass through the three points, so we now want to find the projected vector b^=Ax^\proj{\hat{b}} = \proj{A\hat{x}} on the plane, the error vector e=b−Ax^\err{e} = \target{b} - \proj{A\hat{x}} of vertical misses, and the single number ∥e∥\err{\|e\|} that measures the total error of the line.

Finding the Projection, Error Vector, and Least Squares Error
11
22
33
11
22
33
xx
yy
(1,1)\htmlClass{lc-blue}{(1, 1)}
(2,2)\htmlClass{lc-blue}{(2, 2)}
(3,2)\htmlClass{lc-blue}{(3, 2)}
y=12x+23y = \tfrac{1}{2}x + \tfrac{2}{3}
b^=  ?e=  ?∥e∥=  ?\begin{aligned} \htmlClass{lc-violet}{\hat{b}} &= \;? \\[3pt] \htmlClass{lc-orange}{e} &= \;? \\[3pt] \htmlClass{lc-orange}{\|e\|} &= \;? \end{aligned}
Text solution
Evaluate the best fit line at x=1,2,3x = 1, 2, 3 to get the projection b^=Ax^\proj{\hat{b}} = \proj{A\hat{x}}The three heights from y=12x+23y = \frac{1}{2}x + \frac{2}{3} give the closest vector b^\proj{\hat{b}} on the column space:
b^=Ax^=[12(1)+2312(2)+2312(3)+23]=[36+4666+4696+46]=[76106136]\displaystyle \proj{\hat{b}} = \proj{A\hat{x}} = \begin{bmatrix} \frac{1}{2}(1) + \frac{2}{3} \\[4pt] \frac{1}{2}(2) + \frac{2}{3} \\[4pt] \frac{1}{2}(3) + \frac{2}{3} \end{bmatrix} = \begin{bmatrix} \frac{3}{6} + \frac{4}{6} \\[4pt] \frac{6}{6} + \frac{4}{6} \\[4pt] \frac{9}{6} + \frac{4}{6} \end{bmatrix} = \proj{\begin{bmatrix} \tfrac{7}{6} \\[4pt] \tfrac{10}{6} \\[4pt] \tfrac{13}{6} \end{bmatrix}}
Subtract the line's heights b^\proj{\hat{b}} from the data heights b\target{b} to find the error vector e\err{e}Subtracting component by component gives the vertical miss at each data point:
e=b−Ax^=[122]−[76106136]=[66−76126−106126−136]=[−1626−16]\displaystyle \err{e} = \target{b} - \proj{A\hat{x}} = \target{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} - \proj{\begin{bmatrix} \tfrac{7}{6} \\[4pt] \tfrac{10}{6} \\[4pt] \tfrac{13}{6} \end{bmatrix}} = \begin{bmatrix} \target{\tfrac{6}{6}} - \proj{\tfrac{7}{6}} \\[4pt] \target{\tfrac{12}{6}} - \proj{\tfrac{10}{6}} \\[4pt] \target{\tfrac{12}{6}} - \proj{\tfrac{13}{6}} \end{bmatrix} = \err{\begin{bmatrix} -\tfrac{1}{6} \\[4pt] \tfrac{2}{6} \\[4pt] -\tfrac{1}{6} \end{bmatrix}}
Add the squared misses and take the square root to find the least squares error ∥e∥\err{\|e\|}Using the 3D Pythagorean theorem on the components of e\err{e} gives the length of the error vector:
∥e∥2=(−16)2+(26)2+(−16)2=136+436+136=636=16∥e∥⏟least squares error=16\displaystyle \begin{aligned} & \err{\|e\|^2} = \left(\err{-\frac{1}{6}}\right)^2 + \left(\err{\frac{2}{6}}\right)^2 \\ &\quad + \left(\err{-\frac{1}{6}}\right)^2 \\ &\quad = \frac{1}{36} + \frac{4}{36} + \frac{1}{36} = \frac{6}{36} \\ &\quad = \frac{1}{6} \\ & \underbrace{\err{\|e\|}}_{\text{least squares error}} = \sqrt{\frac{1}{6}} \end{aligned}

So the shortest 3D distance from b\target{b} to the column space is 16\sqrt{\tfrac{1}{6}}, and any other line drawn on the graph will have a least squares error larger than 16\sqrt{\tfrac{1}{6}}.

4

When the Least Squares Solution Is Unique

Every target vector b\target{b} has a single closest point b^\proj{\hat{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^\hat{x} that produces b^\proj{\hat{b}}, and what happens when three data points are stacked vertically at (2,1)\data{(2, 1)}, (2,2)\data{(2, 2)}, and (2,5)\data{(2, 5)}.

When the Least Squares Solution Is Unique
11
22
33
11
22
33
44
55
xx
yy
(2,1)\htmlClass{lc-blue}{(2, 1)}
(2,2)\htmlClass{lc-blue}{(2, 2)}
(2,5)\htmlClass{lc-blue}{(2, 5)}
y=mx+cx^=[m^c^]=  ?\begin{aligned} y &= \htmlClass{lc-green}{m}x + \htmlClass{lc-pink}{c} \\[3pt] \hat{x} &= \begin{bmatrix} \htmlClass{lc-green}{\hat{m}} \\ \htmlClass{lc-pink}{\hat{c}} \end{bmatrix} = \;? \end{aligned}

When the columns of AA are linearly independent, there is only one combination x^\hat{x} that gives b^\proj{\hat{b}}, and ATAA^T A is invertible:

x^\displaystyle \hat{x} =(ATA)−1ATb\displaystyle = (A^T A)^{-1} A^T \target{b}

When the columns of AA are linearly dependent, ATAA^T A is no longer invertible, and infinitely many combinations x^\hat{x} give the exact same projection b^\proj{\hat{b}}.

Text solution
Write Ax=bAx = \target{b} in column form for (2,1)\data{(2, 1)}, (2,2)\data{(2, 2)}, and (2,5)\data{(2, 5)}Because all three points have x=2x = 2, the first column of AA is just 22 times the second column, so both columns lie on the same line in 3D space:
m[222]+c[111]=[125],[222]=2[111]\displaystyle \firstcol{m}\firstcol{\begin{bmatrix} 2 \\ 2 \\ 2 \end{bmatrix}} + \secondcol{c}\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} = \target{\begin{bmatrix} 1 \\ 2 \\ 5 \end{bmatrix}}, \qquad \firstcol{\begin{bmatrix} 2 \\ 2 \\ 2 \end{bmatrix}} = 2\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}}
Dot with [111]\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} to find the equation relating m^\firstcol{\hat{m}} and c^\secondcol{\hat{c}} and the unique projection b^\proj{\hat{b}}Projecting b=[125]\target{b} = \target{\begin{bmatrix} 1 \\ 2 \\ 5 \end{bmatrix}} onto the line spanned by the columns gives a single equation relating m^\firstcol{\hat{m}} and c^\secondcol{\hat{c}}:
([111]⋅[222])m^+([111]⋅[111])c^=[111]⋅[125]6m^+3c^=1+2+56m^+3c^=82m^+c^=83\displaystyle \begin{aligned} & \left(\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} \cdot \firstcol{\begin{bmatrix} 2 \\ 2 \\ 2 \end{bmatrix}}\right)\firstcol{\hat{m}} \\ &\quad + \left(\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} \cdot \secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}}\right)\secondcol{\hat{c}} \\ &\quad = \secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} \cdot \target{\begin{bmatrix} 1 \\ 2 \\ 5 \end{bmatrix}} \\ & 6\firstcol{\hat{m}} + 3\secondcol{\hat{c}} = 1 + 2 + 5 \\ & 6\firstcol{\hat{m}} + 3\secondcol{\hat{c}} = 8 \\ & 2\firstcol{\hat{m}} + \secondcol{\hat{c}} = \frac{8}{3} \end{aligned}
b^=m^[222]+c^[111]=(2m^+c^)[111]=[838383]\displaystyle \proj{\hat{b}} = \firstcol{\hat{m}}\firstcol{\begin{bmatrix} 2 \\ 2 \\ 2 \end{bmatrix}} + \secondcol{\hat{c}}\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} = (2\firstcol{\hat{m}} + \secondcol{\hat{c}})\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} = \proj{\begin{bmatrix} \tfrac{8}{3} \\[4pt] \tfrac{8}{3} \\[4pt] \tfrac{8}{3} \end{bmatrix}}

So the projection b^=[838383]\proj{\hat{b}} = \proj{\begin{bmatrix} \tfrac{8}{3} \\[4pt] \tfrac{8}{3} \\[4pt] \tfrac{8}{3} \end{bmatrix}} is still unique, while any slope m^\firstcol{\hat{m}} and intercept c^\secondcol{\hat{c}} with 2m^+c^=832\firstcol{\hat{m}} + \secondcol{\hat{c}} = \frac{8}{3} gives a best fit line passing through (2,83)\proj{(2, \tfrac{8}{3})} with the exact same vertical misses.

Every line through (2,83)\proj{(2, \tfrac{8}{3})} has 2m^+c^=832\firstcol{\hat{m}} + \secondcol{\hat{c}} = \tfrac{8}{3}, so the two vectors m^[222]\firstcol{\hat{m}}\firstcol{\begin{bmatrix} 2 \\ 2 \\ 2 \end{bmatrix}} and c^[111]\secondcol{\hat{c}}\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} always add up to the exact same projection b^=[838383]\proj{\hat{b}} = \proj{\begin{bmatrix} \tfrac{8}{3} \\[4pt] \tfrac{8}{3} \\[4pt] \tfrac{8}{3} \end{bmatrix}}, 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

11
22
33
11
22
xx
yy
e1\htmlClass{lc-orange}{e_1}
e2\htmlClass{lc-orange}{e_2}
e3\htmlClass{lc-orange}{e_3}
y=mx+cy = \htmlClass{lc-green}{m}x + \htmlClass{lc-pink}{c}

When you set up Ax=bAx = \target{b} to fit a line y=mx+cy = \firstcol{m}x + \secondcol{c} to data, first check whether b\target{b} is already in the column space of AA: if the points (1,1)\data{(1, 1)}, (2,2)\data{(2, 2)}, and (3,3)\data{(3, 3)} already lie on the line y=xy = x, then b=[123]\target{b} = \target{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} is already 1[123]+0[111]1\firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} + 0\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}}, so Ax=bAx = \target{b} solves directly with error ∥e∥=0\err{\|e\|} = 0 and you do not need the normal equations.

When the points do not line up, b\target{b} sits outside the column space of AA and Ax=bAx = \target{b} has no solution. To find the closest fit, dot the column equation with each column of AA to form the normal equations:

ATAx^\displaystyle A^T A\hat{x} =ATb\displaystyle = A^T \target{b}

For (1,1)\data{(1, 1)}, (2,2)\data{(2, 2)}, and (3,2)\data{(3, 2)} with A=[112131]A = \begin{bmatrix} \firstcol{1} & \secondcol{1} \\ \firstcol{2} & \secondcol{1} \\ \firstcol{3} & \secondcol{1} \end{bmatrix} and b=[122]\target{b} = \target{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}}, dotting with [123]\firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} and [111]\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} gives [14663][m^c^]=[115]\begin{bmatrix} 14 & 6 \\ 6 & 3 \end{bmatrix}\begin{bmatrix} \firstcol{\hat{m}} \\ \secondcol{\hat{c}} \end{bmatrix} = \begin{bmatrix} 11 \\ 5 \end{bmatrix}, so m^=12\firstcol{\hat{m}} = \frac{1}{2} and c^=23\secondcol{\hat{c}} = \frac{2}{3}.

Evaluating the line at the data points gives the projection b^=Ax^\proj{\hat{b}} = \proj{A\hat{x}} on the column space, subtracting gives the error vector e=b−b^\err{e} = \target{b} - \proj{\hat{b}} of vertical misses on the graph, and taking its length gives the least squares error ∥e∥=e12+e22+e32\err{\|e\|} = \sqrt{\err{e_1^2} + \err{e_2^2} + \err{e_3^2}}. If you already have a vector b^\proj{\hat{b}} on the column space, you can skip solving ATAx^=ATbA^T A\hat{x} = A^T \target{b} and test e=b−b^\err{e} = \target{b} - \proj{\hat{b}} directly: b^\proj{\hat{b}} is the least squares projection exactly when e\err{e} has a zero dot product with every column of AA.

Finally, look at the columns of AA to tell whether x^\hat{x} is unique. Linearly independent columns make ATAA^T A invertible, giving one best-fit solution x^=(ATA)−1ATb\hat{x} = (A^T A)^{-1}A^T \target{b}. Linearly dependent columns, like [222]\firstcol{\begin{bmatrix} 2 \\ 2 \\ 2 \end{bmatrix}} and [111]\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} when all points are stacked at x=2x = 2, lie on the same line and make ATAA^T A non-invertible, so infinitely many weight vectors x^\hat{x} (every pair with 2m^+c^=832\firstcol{\hat{m}} + \secondcol{\hat{c}} = \frac{8}{3}) give the exact same projection b^=[838383]\proj{\hat{b}} = \proj{\begin{bmatrix} \tfrac{8}{3} \\[4pt] \tfrac{8}{3} \\[4pt] \tfrac{8}{3} \end{bmatrix}} and least squares error ∥e∥\err{\|e\|}.

5

Practice

1

Set up the matrix equation Ax=bAx = \target{b} and solve the normal equations ATAx^=ATbA^T A\hat{x} = A^T \target{b} to find the best fit line y=m^x+c^y = \firstcol{\hat{m}}x + \secondcol{\hat{c}} for the data points (0,1)\data{(0, 1)}, (1,3)\data{(1, 3)}, and (2,4)\data{(2, 4)}.

Plug each (x,y)(x, y) pair into mx+c=y\firstcol{m}x + \secondcol{c} = y to get the two columns of AA and the vector b\target{b}, then dot the entire equation with each column of AA.

Plugging (0,1)\data{(0, 1)}, (1,3)\data{(1, 3)}, and (2,4)\data{(2, 4)} into mx+c=y\firstcol{m}x + \secondcol{c} = y gives Ax=bAx = \target{b}:
A=[011121],x=[mc],b=[134]\displaystyle A = \begin{bmatrix} \firstcol{0} & \secondcol{1} \\ \firstcol{1} & \secondcol{1} \\ \firstcol{2} & \secondcol{1} \end{bmatrix}, \qquad x = \begin{bmatrix} \firstcol{m} \\ \secondcol{c} \end{bmatrix}, \qquad \target{b} = \target{\begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix}}
Dotting the column equation m^[012]+c^[111]≈[134]\firstcol{\hat{m}}\firstcol{\begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix}} + \secondcol{\hat{c}}\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} \approx \target{\begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix}} with [012]\firstcol{\begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix}} and then with [111]\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} gives the normal equations ATAx^=ATbA^T A\hat{x} = A^T \target{b}:
(0+1+4)m^+(0+1+2)c^=0+3+8(0+1+2)m^+(1+1+1)c^=1+3+4⟹[5333][m^c^]=[118]\displaystyle \begin{gathered} \begin{aligned} & (0 + 1 + 4)\firstcol{\hat{m}} + (0 + 1 + 2)\secondcol{\hat{c}} \\ &\quad = 0 + 3 + 8 \\ & (0 + 1 + 2)\firstcol{\hat{m}} + (1 + 1 + 1)\secondcol{\hat{c}} \\ &\quad = 1 + 3 + 4 \end{aligned} \\[4pt] \Longrightarrow\quad \begin{bmatrix} 5 & 3 \\ 3 & 3 \end{bmatrix}\begin{bmatrix} \firstcol{\hat{m}} \\ \secondcol{\hat{c}} \end{bmatrix} = \begin{bmatrix} 11 \\ 8 \end{bmatrix} \end{gathered}
Subtracting the second equation from the first eliminates c^\secondcol{\hat{c}}:
(5m^+3c^)−(3m^+3c^)=11−82m^=3m^=32\displaystyle \begin{aligned} (5\firstcol{\hat{m}} + 3\secondcol{\hat{c}}) - (3\firstcol{\hat{m}} + 3\secondcol{\hat{c}}) &= 11 - 8 \\ 2\firstcol{\hat{m}} &= 3 \\ \firstcol{\hat{m}} &= \frac{3}{2} \end{aligned}
Substitute m^=32\firstcol{\hat{m}} = \frac{3}{2} into the second equation 3m^+3c^=83\firstcol{\hat{m}} + 3\secondcol{\hat{c}} = 8 (watch out for stopping at 3c^=723\secondcol{\hat{c}} = \frac{7}{2} and forgetting to divide by 33, which gives the wrong line y=32x+72y = \frac{3}{2}x + \frac{7}{2}):
3(32)+3c^=83c^=162−92=72c^=76\displaystyle \begin{aligned} 3\left(\frac{3}{2}\right) + 3\secondcol{\hat{c}} &= 8 \\ 3\secondcol{\hat{c}} &= \frac{16}{2} - \frac{9}{2} = \frac{7}{2} \\ \secondcol{\hat{c}} &= \frac{7}{6} \end{aligned}
The best fit line is y=32x+76y = \frac{3}{2}x + \frac{7}{6}.
2

For the data points (−1,0)\data{(-1, 0)}, (0,1)\data{(0, 1)}, and (1,4)\data{(1, 4)}, the best fit line is y=2x+53y = 2x + \tfrac{5}{3}. Find the projection vector b^=Ax^\proj{\hat{b}} = \proj{A\hat{x}} on the column space, the error vector e=b−Ax^\err{e} = \target{b} - \proj{A\hat{x}} of vertical misses, and the least squares error ∥e∥\err{\|e\|}.

The entries of b^=Ax^\proj{\hat{b}} = \proj{A\hat{x}} are the heights on the line y=2x+53y = 2x + \tfrac{5}{3} at x=−1,0,1x = -1, 0, 1. How do you get the vertical miss at each point from there?

Evaluating y=2x+53y = 2x + \frac{5}{3} at x=−1,0,1x = -1, 0, 1 gives the projection vector b^\proj{\hat{b}}:
b^=Ax^=[2(−1)+532(0)+532(1)+53]=[−1353113]\displaystyle \proj{\hat{b}} = \proj{A\hat{x}} = \begin{bmatrix} 2(-1) + \tfrac{5}{3} \\[4pt] 2(0) + \tfrac{5}{3} \\[4pt] 2(1) + \tfrac{5}{3} \end{bmatrix} = \proj{\begin{bmatrix} -\tfrac{1}{3} \\[4pt] \tfrac{5}{3} \\[4pt] \tfrac{11}{3} \end{bmatrix}}
Subtracting b^\proj{\hat{b}} from the actual heights b=[014]\target{b} = \target{\begin{bmatrix} 0 \\ 1 \\ 4 \end{bmatrix}} gives the error vector e\err{e} (be careful with the double negative in 0−(−13)\target{0} - (\proj{-\tfrac{1}{3}}) on the first component):
e=b−Ax^=[014]−[−1353113]=[13−2313]\displaystyle \err{e} = \target{b} - \proj{A\hat{x}} = \target{\begin{bmatrix} 0 \\ 1 \\ 4 \end{bmatrix}} - \proj{\begin{bmatrix} -\tfrac{1}{3} \\[4pt] \tfrac{5}{3} \\[4pt] \tfrac{11}{3} \end{bmatrix}} = \err{\begin{bmatrix} \tfrac{1}{3} \\[4pt] -\tfrac{2}{3} \\[4pt] \tfrac{1}{3} \end{bmatrix}}
Sum the squares of the vertical misses and take the square root (watch out for stopping at ∥e∥2=23\err{\|e\|^2} = \frac{2}{3} without taking the square root):
∥e∥2=(13)2+(−23)2+(13)2=19+49+19=69=23∥e∥=23\displaystyle \begin{aligned} \err{\|e\|^2} &= \left(\err{\frac{1}{3}}\right)^2 + \left(\err{-\frac{2}{3}}\right)^2 + \left(\err{\frac{1}{3}}\right)^2 \\ &= \frac{1}{9} + \frac{4}{9} + \frac{1}{9} = \frac{6}{9} = \frac{2}{3} \\ \err{\|e\|} &= \sqrt{\frac{2}{3}} \end{aligned}
3

For A=[112131]A = \begin{bmatrix} \firstcol{1} & \secondcol{1} \\ \firstcol{2} & \secondcol{1} \\ \firstcol{3} & \secondcol{1} \end{bmatrix} and b=[435]\target{b} = \target{\begin{bmatrix} 4 \\ 3 \\ 5 \end{bmatrix}}, someone claims that the vector b^=[345]\proj{\hat{b}} = \proj{\begin{bmatrix} 3 \\ 4 \\ 5 \end{bmatrix}} on the column space of AA (from the line y=x+2y = x + 2) is the least squares projection of b\target{b}. Without solving the normal equations, use the error vector e=b−b^\err{e} = \target{b} - \proj{\hat{b}} to check whether this claim is true.

If b^\proj{\hat{b}} is the perpendicular projection onto the column space, what must the dot product of e=b−b^\err{e} = \target{b} - \proj{\hat{b}} with each column of AA equal?

First find the error vector e=b−b^\err{e} = \target{b} - \proj{\hat{b}}:
e=[435]−[345]=[1−10]\displaystyle \err{e} = \target{\begin{bmatrix} 4 \\ 3 \\ 5 \end{bmatrix}} - \proj{\begin{bmatrix} 3 \\ 4 \\ 5 \end{bmatrix}} = \err{\begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix}}
Now dot e\err{e} with the columns of AA. Dotting e\err{e} with the second column [111]\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} gives 1(1)+(−1)(1)+0(1)=0\err{1}(\secondcol{1}) + (\err{-1})(\secondcol{1}) + \err{0}(\secondcol{1}) = 0, but do not stop after checking only one column (checking only [111]\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} leads to the wrong conclusion that the claim is true). Dotting e\err{e} with the first column [123]\firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} gives:
e⋅[123]=1(1)+(−1)(2)+0(3)=1−2+0=−1≠0\displaystyle \err{e} \cdot \firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} = \err{1}(\firstcol{1}) + (\err{-1})(\firstcol{2}) + \err{0}(\firstcol{3}) = 1 - 2 + 0 = -1 \neq 0
Because e\err{e} is not perpendicular to every column of AA, b^=[345]\proj{\hat{b}} = \proj{\begin{bmatrix} 3 \\ 4 \\ 5 \end{bmatrix}} is not the least squares projection.
4

For the system Ax=bAx = \target{b} with A=[132626]A = \begin{bmatrix} \firstcol{1} & \secondcol{3} \\ \firstcol{2} & \secondcol{6} \\ \firstcol{2} & \secondcol{6} \end{bmatrix} and b=[036]\target{b} = \target{\begin{bmatrix} 0 \\ 3 \\ 6 \end{bmatrix}}, explain why ATAA^T A is not invertible, find all least squares solutions x^=[x^1x^2]\hat{x} = \begin{bmatrix} \firstcol{\hat{x}_1} \\ \secondcol{\hat{x}_2} \end{bmatrix}, and find the unique projection b^\proj{\hat{b}} and least squares error ∥e∥\err{\|e\|}.

Compare the second column of AA to the first column to see the line they span, then dot Ax=bAx = \target{b} with [122]\firstcol{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} to find x^1+3x^2\firstcol{\hat{x}_1} + 3\secondcol{\hat{x}_2}.

The second column [366]\secondcol{\begin{bmatrix} 3 \\ 6 \\ 6 \end{bmatrix}} is 33 times the first column [122]\firstcol{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}}, so the columns of AA are linearly dependent and ATA=[9272781]A^T A = \begin{bmatrix} 9 & 27 \\ 27 & 81 \end{bmatrix} is not invertible.
Dotting x^1[122]+x^2[366]≈[036]\firstcol{\hat{x}_1}\firstcol{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} + \secondcol{\hat{x}_2}\secondcol{\begin{bmatrix} 3 \\ 6 \\ 6 \end{bmatrix}} \approx \target{\begin{bmatrix} 0 \\ 3 \\ 6 \end{bmatrix}} with [122]\firstcol{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} turns both rows of ATAx^=ATbA^T A\hat{x} = A^T \target{b} into a single equation:
(1+4+4)x^1+(3+12+12)x^2=0+6+129x^1+27x^2=18x^1+3x^2=2\displaystyle \begin{aligned} & (1 + 4 + 4)\firstcol{\hat{x}_1} + (3 + 12 + 12)\secondcol{\hat{x}_2} \\ &\quad = 0 + 6+ 12 \\ & 9\firstcol{\hat{x}_1} + 27\secondcol{\hat{x}_2} = 18 \\ & \firstcol{\hat{x}_1} + 3\secondcol{\hat{x}_2} = 2 \end{aligned}
So every vector x^=[x^1x^2]\hat{x} = \begin{bmatrix} \firstcol{\hat{x}_1} \\ \secondcol{\hat{x}_2} \end{bmatrix} with x^1+3x^2=2\firstcol{\hat{x}_1} + 3\secondcol{\hat{x}_2} = 2 is a least squares solution.
Factoring b^=x^1[122]+x^2[366]\proj{\hat{b}} = \firstcol{\hat{x}_1}\firstcol{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} + \secondcol{\hat{x}_2}\secondcol{\begin{bmatrix} 3 \\ 6 \\ 6 \end{bmatrix}} gives the unique projection (be careful to multiply x^1+3x^2=2\firstcol{\hat{x}_1} + 3\secondcol{\hat{x}_2} = 2 by the first column [122]\firstcol{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}}, not the second column [366]\secondcol{\begin{bmatrix} 3 \\ 6 \\ 6 \end{bmatrix}}, which would give [61212]\begin{bmatrix} 6 \\ 12 \\ 12 \end{bmatrix} and ∥e∥=153\err{\|e\|} = \sqrt{153}):
b^=(x^1+3x^2)[122]=2[122]=[244]\displaystyle \proj{\hat{b}} = (\firstcol{\hat{x}_1} + 3\secondcol{\hat{x}_2})\firstcol{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} = 2\firstcol{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} = \proj{\begin{bmatrix} 2 \\ 4 \\ 4 \end{bmatrix}}
Subtracting b^\proj{\hat{b}} from b\target{b} gives the error vector and least squares error:
e=b−b^=[036]−[244]=[−2−12],∥e∥=(−2)2+(−1)2+22=4+1+4=3\displaystyle \err{e} = \target{b} - \proj{\hat{b}} = \target{\begin{bmatrix} 0 \\ 3 \\ 6 \end{bmatrix}} - \proj{\begin{bmatrix} 2 \\ 4 \\ 4 \end{bmatrix}} = \err{\begin{bmatrix} -2 \\ -1 \\ 2 \end{bmatrix}}, \qquad \err{\|e\|} = \sqrt{(\err{-2})^2 + (\err{-1})^2 + \err{2}^2} = \sqrt{4 + 1 + 4} = 3
5

Three data points are at (1,2)\data{(1, 2)}, (2,3)\data{(2, 3)}, and (3,k)\data{(3, k)}. (a) For what value of k\target{k} does b=[23k]\target{b} = \target{\begin{bmatrix} 2 \\ 3 \\ k \end{bmatrix}} lie in the column space of AA so that the least squares error is 00? (b) For what value of k\target{k} does the best fit line have slope m^=2\firstcol{\hat{m}} = 2, and what is its intercept c^\secondcol{\hat{c}}?

For (a), find the height at x=3x = 3 of the line through (1,2)\data{(1, 2)} and (2,3)\data{(2, 3)}. For (b), dot the column equation with [123]\firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} and [111]\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}}, keeping k\target{k} in ATbA^T \target{b}.

(a)The line through (1,2)\data{(1, 2)} and (2,3)\data{(2, 3)} is y=x+1y = x + 1, which has height y=4y = 4 at x=3x = 3, so b\target{b} lies in the column space of AA when k=4\target{k} = 4.
(b)With A=[112131]A = \begin{bmatrix} \firstcol{1} & \secondcol{1} \\ \firstcol{2} & \secondcol{1} \\ \firstcol{3} & \secondcol{1} \end{bmatrix} and b=[23k]\target{b} = \target{\begin{bmatrix} 2 \\ 3 \\ k \end{bmatrix}}, dot the column equation with [123]\firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} and [111]\secondcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} (watch out for forgetting to multiply k\target{k} by 33 when dotting [123]⋅[23k]\firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} \cdot \target{\begin{bmatrix} 2 \\ 3 \\ k \end{bmatrix}}, which gives 8+k8 + \target{k} instead of 8+3k8 + 3\target{k} and leads to k=−6\target{k} = -6, c^=−133\secondcol{\hat{c}} = -\frac{13}{3}):
14m^+6c^=1(2)+2(3)+3(k)=8+3k6m^+3c^=1(2)+1(3)+1(k)=5+k\displaystyle \begin{aligned} 14\firstcol{\hat{m}} + 6\secondcol{\hat{c}} &= \firstcol{1}(\target{2}) + \firstcol{2}(\target{3}) + \firstcol{3}(\target{k}) \\ &= 8 + 3\target{k} \\ 6\firstcol{\hat{m}} + 3\secondcol{\hat{c}} &= \secondcol{1}(\target{2}) + \secondcol{1}(\target{3}) + \secondcol{1}(\target{k}) \\ &= 5 + \target{k} \end{aligned}
Doubling the second equation and subtracting it from the first isolates m^\firstcol{\hat{m}}:
(14m^+6c^)−2(6m^+3c^)=(8+3k)−2(5+k)2m^=k−2\displaystyle \begin{aligned} & (14\firstcol{\hat{m}} + 6\secondcol{\hat{c}}) - 2(6\firstcol{\hat{m}} + 3\secondcol{\hat{c}}) \\ &\quad = (8 + 3\target{k}) - 2(5 + \target{k}) \\ & 2\firstcol{\hat{m}} = \target{k} - 2 \end{aligned}
Setting m^=2\firstcol{\hat{m}} = 2 gives 4=k−24 = \target{k} - 2, so k=6\target{k} = 6. Substituting m^=2\firstcol{\hat{m}} = 2 and k=6\target{k} = 6 back into 6m^+3c^=5+k6\firstcol{\hat{m}} + 3\secondcol{\hat{c}} = 5 + \target{k} gives:
6(2)+3c^=5+612+3c^=11c^=−13\displaystyle \begin{aligned} 6(2) + 3\secondcol{\hat{c}} &= 5 + 6 \\ 12 + 3\secondcol{\hat{c}} &= 11 \\ \secondcol{\hat{c}} &= -\frac{1}{3} \end{aligned}