Back to the on-screen lesson ·
Minimising the squared residual: the orthogonality that characterises the answer, the normal equations that compute it, and why the basis they are written in decides how many digits survive.
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 derive the normal equations, prove that the best approximation is the one with an orthogonal residual, count coefficients against data points, and say why forming the normal equations costs half the available digits.
You can build an interpolating polynomial, which matches data exactly at every node, and you know that inner products and orthogonality are how a vector is projected onto a subspace. Least squares is that projection, applied to functions, when matching exactly is either impossible or a bad idea.
The residual is $f - p$, the part the approximation missed. An inner product is $\langle f, g\rangle = \int w f g$ or $\sum w_i f_i g_i$, and two functions are orthogonal when it vanishes. The normal equations are the linear system for the coefficients, and their matrix is the Gram matrix of the basis — whose entries are the inner products of the basis functions with each other.
Given $f$ and a space $V$ of approximations, the least-squares approximation minimises $\|f - p\|^{2}$, a sum or integral of the squared residual. Two facts do all the work. The first is a characterisation: $p$ is best exactly when the residual $f - p$ is orthogonal to every element of $V$ — nothing is left in the residual that $V$ could have taken out. That is basis-free, and it is why least squares always has an answer and why the answer is unique. The second is a computation: writing $p$ in a basis and setting each partial derivative of the squared error to zero gives one linear equation per coefficient, the normal equations $A^{\mathsf{T}}Ac = A^{\mathsf{T}}b$, whose matrix is the Gram matrix of the basis. And there the trouble starts. In the monomial basis on $[0, 1]$ the Gram matrix has entries $\dfrac{1}{i + j + 1}$ — the Hilbert matrix — whose condition number grows like $10^{n}$. Worse, forming $A^{\mathsf{T}}A$ squares the singular values and so squares the condition number, throwing away half the available digits before any solving begins. The characterisation is mathematics and the misbehaviour is arithmetic: change the basis to an orthogonal one and the Gram matrix becomes diagonal, or factorise $A$ directly and never form the square at all.
Another way: steps
Another way: picture
The function $f$ is a point off a plane, and $V$ is the plane. The least-squares approximation is the foot of the perpendicular, and the residual is the perpendicular itself — which is the whole characterisation in one sentence, and the reason the answer exists and is unique. The basis is only a choice of axes drawn in the plane; a skewed pair of axes describes the same foot of the same perpendicular with coordinates that are hard to compute accurately.
A least-squares fit with a zero residual is read as a triumph. It means the space had as much freedom as the data had points, so the fit reproduced the noise exactly along with everything else, and the next observation will lie far off it. The second half of the mistake is computational: the normal equations are how the method is derived and a poor way to compute it, because forming $A^{\mathsf{T}}A$ squares the condition number and costs half the digits for nothing.
Fit a constant $c$ to data $y_1, \ldots, y_m$: the space is the constants, the basis is $\{1\}$.
One coefficient.
Orthogonality says $\sum (y_i - c) = 0$, so $c$ is the mean.
The normal equation, in one line.
Monomials on $[0, 1]$: $\langle x^{i}, x^{j}\rangle = \dfrac{1}{i + j + 1}$.
The Hilbert matrix.
For degree $9$ its condition number is about $10^{12}$, so four digits survive in double precision.
From a perfectly innocent fit.
In the Legendre basis the same problem has a diagonal Gram matrix and every coefficient is one integral.
The problem was never the trouble.
The space is the multiples of $x$, so $p(x) = cx$ and the residual is $y_i - cx_i$.
Orthogonality to $x$ gives $\sum x_i(y_i - cx_i) = 0$, so $c = \dfrac{\sum x_iy_i}{\sum x_i^{2}}$.
$= \dfrac{0 + 1 + 6}{0 + 1 + 4} = \dfrac75$ — one inner product over another, which is what a one-dimensional projection always is.
A polynomial of degree $3$ is fitted to data by least squares. How many normal equations are there?
Answer:
A polynomial is fitted by least squares to $13$ data points with distinct $x$ values. For degrees $4$, $5$ and $6$, give the number of data points left over once the coefficients are counted.
| Coefficients | Data points left over | |
|---|---|---|
| Degree $4$ | 5 | |
| Degree $5$ | 6 | |
| Degree $6$ | 7 |
Match each part of the least-squares construction to what it is.
| The sum or integral of the squared residual | Its residual is orthogonal to the whole approximating space | The normal equations $A^{\mathsf{T}}Ac = A^{\mathsf{T}}b$ | The Gram matrix is the Hilbert matrix, and hopelessly conditioned | |
|---|---|---|---|---|
| What the method minimises | ||||
| What characterises the best approximation | ||||
| The system that computes the coefficients | ||||
| What goes wrong in the monomial basis |
Put the five steps of deriving the normal equations into the order they depend on each other.
Number the steps in order (write the number in the box):
A least-squares problem has a matrix $A$ with $\kappa_2(A) = 10^{2}$, and is solved in double precision by forming and solving $A^{\mathsf{T}}Ac = A^{\mathsf{T}}b$. About how many correct digits should the coefficients have?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Build the argument that the least-squares approximation is exactly the one whose residual is orthogonal to the approximating space.
This task has no paper form; do it on a device.
You can derive and characterise a least-squares approximation and say what the normal equations cost. Say in your own words why a zero residual is a warning rather than a success.
8. Your turn: the least-squares line through $(0, 0)$, $(1, 1)$, $(2, 3)$ with no constant term, step 3