Back to the on-screen lesson ·
What it means to solve a system that has no solution, the projection that answers it, the normal equations $A^{T}A\hat{x} = A^{T}b$ and where they come from, the line of best fit as an instance of them, residuals and what they must satisfy, and the QR route that avoids forming $A^{T}A$ at all.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to say what a least-squares solution of an inconsistent system is and why the projection of $b$ onto the column space is the right answer, derive the normal equations from the residual being orthogonal to every column, form $A^{T}A$ and $A^{T}b$ for a line fit, compute and check residuals and know why they sum to zero when the model has an intercept, say exactly when $A^{T}A$ is invertible, and solve the same problem by back-substitution through $R$ instead.
A system with more equations than unknowns is nearly always inconsistent, and so far the honest answer has been that it has no solution. That answer is useless in every application that produces such a system — ten measurements of a quantity with two parameters, a curve asked to pass through a hundred points — and the useful question is not which $x$ solves it but which $x$ comes closest. Projection answers that, and the previous two lessons built everything the answer needs.
A system is overdetermined when it has more equations than unknowns. The residual of a candidate $x$ is $e = b - Ax$, and $|e|^2$ is the sum of squared errors. A least-squares solution $\hat{x}$ is one minimising $|b - Ax|$. The normal equations are $A^{T}A\hat{x} = A^{T}b$, and $A^{T}A$ is the normal matrix. The line of best fit is the least-squares solution of the system asking a line to pass through every data point.
$Ax$ is a combination of the columns of $A$, so as $x$ ranges over everything, $Ax$ sweeps out the column space $C(A)$ and nothing more. The system $Ax = b$ has a solution exactly when $b \in C(A)$. When $b$ is not there — the usual case with more rows than columns — the question changes: find $\hat{x}$ making $A\hat{x}$ as close to $b$ as possible.
The previous lesson answered that for any subspace: the closest point is the projection, and it is characterised by the leftover being perpendicular. So the condition on $\hat{x}$ is
$$b - A\hat{x} \ \perp\ \text{every column of } A \quad \Longleftrightarrow \quad A^{T}(b - A\hat{x}) = 0 \quad \Longleftrightarrow \quad A^{T}A\hat{x} = A^{T}b.$$
Those are the normal equations. The middle step is where the transpose earns its place: stacking "orthogonal to each column" into one matrix equation is multiplying by $A^{T}$.
Three things are worth noticing about them.
They are always consistent, whatever $b$ is. $A^{T}b$ lies in the column space of $A^{T}$, which is the row space of $A$, which is where $A^{T}A$'s column space is too. So there is always at least one least-squares solution, even when the original system had none.
$A^{T}A$ is square and symmetric, of size the number of unknowns — so a fit of two parameters to a million data points solves a $2 \times 2$ system.
$A^{T}A$ is invertible exactly when the columns of $A$ are independent. If $A^{T}Ax = 0$ then $|Ax|^2 = x^{T}A^{T}Ax = 0$, so $Ax = 0$; the converse is immediate. With independent columns $\hat{x} = (A^{T}A)^{-1}A^{T}b$ is unique, and $A\hat{x} = A(A^{T}A)^{-1}A^{T}b$ is the projection matrix of the previous lesson with a general $A$ in place of a single column.
Another way: picture
The column space is a plane and $b$ is a point off it. Every $Ax$ is somewhere on the plane; $b$ is not. Drop a perpendicular from $b$: the foot is $A\hat{x}$ and the dropped segment is the residual. Every other point of the plane is further away, by Pythagoras on the right-angled triangle the perpendicular makes. The picture also says what a large residual means — not that the arithmetic went wrong, but that $b$ sits a long way off the plane, so no choice of parameters could have fitted it.
Another way: steps
Fit $y = c + mx$ to points $(x_1, y_1), \dots, (x_n, y_n)$. Asking the line to pass through all of them is the system
$$\begin{pmatrix} 1 & x_1 \\ 1 & x_2 \\ \vdots & \vdots \\ 1 & x_n\end{pmatrix}\begin{pmatrix} c \\ m \end{pmatrix} = \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n\end{pmatrix},$$
which for $n > 2$ has no solution unless the points happen to be collinear. The least-squares solution minimises $\sum (y_i - c - mx_i)^2$: the sum of the squared vertical distances, because the residual is measured in the $y$ direction.
$A^{T}A = \begin{pmatrix} n & \sum x_i \\ \sum x_i & \sum x_i^2\end{pmatrix}$ and $A^{T}b = \begin{pmatrix} \sum y_i \\ \sum x_iy_i \end{pmatrix}$, and the two normal equations are the formulas every statistics course states without derivation. They are not a recipe; they are the condition that the residual be perpendicular to the two columns.
That perpendicularity has a reading anyone can check. Orthogonality to the column of ones says $\sum e_i = 0$: the residuals of a fit with an intercept always sum to zero. Orthogonality to the $x$ column says $\sum x_ie_i = 0$: the residuals are uncorrelated with $x$. A fitted line whose residuals fail either of those was computed wrongly.
Nothing restricts the method to lines. Fitting $y = a + bx + cx^2$ adds a column of $x_i^2$ and changes nothing else: the model must be linear in the parameters, not in $x$.
Via the normal equations. Form $A^{T}A$, form $A^{T}b$, solve. It is the shortest thing to write and the standard derivation, and for hand computation on small problems it is fine.
Via QR. Write $A = QR$ with orthonormal $Q$ and upper triangular $R$. Then $A^{T}A = R^{T}Q^{T}QR = R^{T}R$, and the normal equations become $R^{T}R\hat{x} = R^{T}Q^{T}b$. Cancel the invertible $R^{T}$:
$$R\hat{x} = Q^{T}b.$$
A triangular system, solved by back-substitution from the last row upwards, and $A^{T}A$ is never formed.
The two are identical in exact arithmetic. They are not equivalent in practice. Forming $A^{T}A$ squares the matrix's condition number — roughly, it doubles the number of significant digits lost — and for a fit with several nearly-parallel columns that is the difference between an answer and noise. The classic case is fitting a high-degree polynomial: the columns $1, x, x^2, \dots$ are nearly parallel over a short interval, and the normal equations for degree ten are hopeless in double precision while the QR route is not.
This is worth carrying out of the course. The route a derivation takes and the route a computation should take are different questions, and the second one is decided by what the arithmetic does to errors.
It does not solve the system. $A\hat{x} \ne b$, and the gap is the residual. Reporting $\hat{x}$ as though the system had been solved hides exactly the information that matters.
A small residual is not the goal, and a large one is not a mistake. The residual measures how far $b$ was from the column space, which is a fact about the data. A large residual says the model does not fit — which is a finding, not an error.
Minimising $|b - Ax|$ is not minimising $|x|$. Two different problems with two different answers, and the second one only becomes interesting when the first has many solutions.
Squared error is a choice. Squares are minimised because it makes the problem linear and the answer a projection; absolute errors would be more resistant to outliers and give a problem with no formula. Nothing in the mathematics says squares are the right loss — only that they are the tractable one.
$A^{T}A$ invertible is about the columns of $A$, not about $b$. No right-hand side can make dependent columns independent, and no amount of extra data helps if two of the columns are proportional.
The residuals summing to zero is not a check on the data. It is a check on your arithmetic, and it only holds when the model has an intercept — a fit forced through the origin has no column of ones and no such guarantee.
Fit $y = c + mx$ to $(0,1), (1,3), (2,4)$. $A = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2\end{pmatrix}$, $b = (1,3,4)$.
One row per point.
$A^{T}A = \begin{pmatrix} 3 & 3 \\ 3 & 5 \end{pmatrix}$ and $A^{T}b = (8, 11)$.
Counts, sums, sums of squares.
Solving: $c = \tfrac{7}{6}$, $m = \tfrac{3}{2}$. Fitted values $\tfrac{7}{6}, \tfrac{8}{3}, \tfrac{25}{6}$, residuals $-\tfrac{1}{6}, \tfrac{1}{3}, -\tfrac{1}{6}$, which sum to zero.
The check the theory promises.
Measure one quantity $n$ times. The system is $\mathbf{1}x = b$, with $\mathbf{1}$ the column of ones — inconsistent unless every reading agrees.
One unknown, $n$ equations.
$A^{T}A = n$ and $A^{T}b = \sum b_i$, so $\hat{x} = \dfrac{1}{n}\sum b_i$.
The normal equations, in one line.
The arithmetic mean. Averaging repeated measurements is the least-squares fit of the simplest model there is, and this is the reason it is the right thing to do.
A convention with a derivation.
$A = \begin{pmatrix} 1 \\ 2 \end{pmatrix}$ and $b = (1, 3)$, one unknown.
No column of ones this time.
$A^{T}A = 1 + 4 = 5$ and $A^{T}b = 1 + 6 = 7$, so $m = \tfrac{7}{5}$.
Two dot products.
Residuals $1 - \tfrac{7}{5} = -\tfrac{2}{5}$ and $3 - \tfrac{14}{5} = \tfrac{1}{5}$, which do not sum to zero — and need not, because there is no intercept column for them to be orthogonal to.
A line $y = c + mx$ is fitted at $x = 1, 7, 6$, so $A = \begin{pmatrix} 1 & 1 \\ 1 & 7 \\ 1 & 6 \end{pmatrix}$. Write $A^{T}A$.
This task has no paper form; do it on a device.
Three readings of one quantity are $5$, $8$ and $9$, so $\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}x = \begin{pmatrix} 5 \\ 8 \\ 9 \end{pmatrix}$. Find the least-squares $\hat{x}$.
Answer:
The least-squares line for the three points below is $y = 1 + 15x$, and its fitted values are given. Fill in the residuals.
| Observed | Fitted | Residual | |
|---|---|---|---|
| $x = 0$ | 5 | 1 | |
| $x = 1$ | 8 | 16 | |
| $x = 2$ | 35 | 31 |
$A$ is $6 \times 2$ with independent columns and $Ax = b$ has no solution. What does the least-squares $\hat{x}$ achieve?
$A$ has columns $(1, 1, 1)$ and $(5, 5, k)$. For which real $k$ is $A^{T}A$ invertible?
This task has no paper form; do it on a device.
$A = QR$ with $R = \begin{pmatrix} 5 & 1 \\ 0 & 3 \end{pmatrix}$, and $Q^{T}b = (27, 6)$. Solve $R\hat{x} = Q^{T}b$ and write $\hat{x}$ as a column.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A line $y = c + mx$ is fitted at $x = 3, 2, 5$, so $A = \begin{pmatrix} 1 & 3 \\ 1 & 2 \\ 1 & 5 \end{pmatrix}$. Write $A^{T}A$.
This task has no paper form; do it on a device.
You can set up and solve a least-squares problem, check the residual against the columns, and say when the solution is unique. Say in your own words why the normal equations are always consistent even when the original system is not. Next: the symmetric matrices that $A^{T}A$ is an example of, and what their eigenvectors do.
10. Your turn: the least-squares fit of $y = mx$ (no intercept) to $(1,1)$ and $(2,3)$, step 3
The check applies only when it applies.