Least-Squares Models and Normal Equations, linear algebra I lesson

A table lists three measurements, output $1$ at input $0$ , output $2$ at input $1$ and output $2$ at input $2$ . To fit a line or a parabola to it by least squares, the table has to become a matrix, and someone has to decide what each column of that matrix means. This lesson builds the design matrix from the data, solves the normal equations by elimination, and checks the answer against the original observations. It also shows what changes when two columns of the model carry the same information.

Key terms

Model linear in its coefficients

Definition A model of the form

\begin{aligned} f(t) &= c_1\varphi_1(t) + c_2\varphi_2(t) \\[0.4em] &\quad + \cdots + c_n\varphi_n(t), \end{aligned}

where $\varphi_1, \dots, \varphi_n$ are known functions of the input and $c_1, \dots, c_n$ are unknown real coefficients, is linear in its coefficients. The functions $\varphi_j$ may be nonlinear in $t$ . What matters is that each prediction is a linear combination of the unknowns with known weights, so fitting the model to data by least squares is a linear algebra problem. A model with an unknown inside a nonlinear function, such as $c_1 e^{c_2 t}$ , is usually not linear in that unknown.

In plain words The word linear refers to the unknown coefficients, not to the shape of the graph. A parabola, or a combination of sines with fixed frequencies, still leads to a linear system for its coefficients.

Example The quadratic model $c_1 + c_2 t + c_3 t^2$ uses $\varphi_1(t) = 1$ , $\varphi_2(t) = t$ and $\varphi_3(t) = t^2$ , so it is linear in $c_1, c_2, c_3$ although its graph bends whenever $c_3 \ne 0$ . The model $c_1 + c_2 \sin t$ is also linear in its coefficients. The model $c_1 e^{c_2 t}$ is not linear in $c_2$ , because that coefficient sits inside the exponential.

Design matrix

Definition Fit a model $c_1\varphi_1(t) + \cdots + c_n\varphi_n(t)$ to the observations $(t_1, y_1), \dots, (t_m, y_m)$ . The design matrix is the $m \times n$ matrix $X$ with entries

X_{ij} = \varphi_j(t_i).

Row $i$ belongs to observation $i$ , and column $j$ belongs to the coefficient $c_j$ , in the order chosen for the coefficient vector $\mathbf{c} = (c_1, \dots, c_n)$ . The measured outputs form the separate observation vector $\mathbf{y} = (y_1, \dots, y_m)$ , and the predictions of the model at the observed inputs are the entries of $X\mathbf{c}$ . On this page a tuple written for a vector stands for a column.

In plain words Each column records what one coefficient does to every prediction at once. The known inputs go into $X$ , and the measured outputs stay on the right side in $\mathbf{y}$ . Swapping those roles would pose a different problem.

Example For the line $a + bt$ with $\mathbf{c} = (a, b)$ and the points $(0, 1)$ , $(1, 2)$ , $(2, 2)$ ,

X = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}, \qquad \mathbf{y} = \begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}.

For the quadratic model $c_1 + c_2 t + c_3 t^2$ at the inputs $-1$ , $0$ , $1$ and $2$ , the row for input $t$ is $\begin{bmatrix} 1 & t & t^2 \end{bmatrix}$ , so

X = \begin{bmatrix} 1 & -1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 2 & 4 \end{bmatrix}.

The powers are computed from the known inputs before any coefficient is found.

Fitted values

Definition Let $\hat{\mathbf{c}}$ be a least-squares solution, that is, a solution of the normal equations

X^{\top}X\mathbf{c} = X^{\top}\mathbf{y}.

The fitted values are the entries of $\mathbf{p} = X\hat{\mathbf{c}}$ , the predictions of the fitted model at the observed inputs, and the residuals are the entries of $\mathbf{r} = \mathbf{y} - \mathbf{p}$ . The vector $\mathbf{p}$ is the orthogonal projection of $\mathbf{y}$ onto $\operatorname{Col} X$ , so it is the same for every least-squares solution, and the smallest sum of squared errors is $\lVert \mathbf{r} \rVert^2$ .

In plain words Fitted values are what the chosen model says at the inputs where you measured. The residuals tell you by how much, and in which direction, the model misses each measurement. A residual has the unit of the output, and its square has the squared unit.

Example For the line fitted to the three points above, each entry of $X^{\top}X$ and $X^{\top}\mathbf{y}$ is a dot product of columns,

X^{\top}X = \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}, \qquad X^{\top}\mathbf{y} = \begin{bmatrix} 5 \\ 6 \end{bmatrix}.

The normal equations are $3a + 3b = 5$ and $3a + 5b = 6$ . Subtracting the first from the second gives $2b = 1$ , so $b = \tfrac12$ . Then $3a = 5 - \tfrac32 = \tfrac72$ , so $a = \tfrac76$ . No inverse is needed. The fitted values are

\begin{gathered} \tfrac76 + \tfrac12 \cdot 0 = \tfrac76, \qquad \tfrac76 + \tfrac12 \cdot 1 = \tfrac53, \\[0.4em] \tfrac76 + \tfrac12 \cdot 2 = \tfrac{13}{6}, \end{gathered}

and subtracting them from $1$ , $2$ , $2$ gives the residuals $-\tfrac16$ , $\tfrac13$ and $-\tfrac16$ . The first and third points lie a little below the line and the middle one lies above it. The sum of squared errors is $\tfrac{1}{36} + \tfrac19 + \tfrac{1}{36} = \tfrac16$ .

Residual orthogonality check

Definition For a coefficient vector $\mathbf{c}$ with residual $\mathbf{r} = \mathbf{y} - X\mathbf{c}$ , compute $X^{\top}\mathbf{r}$ , whose entries are the dot products of the residual with the columns of $X$ . The condition $X^{\top}\mathbf{r} = \mathbf{0}$ holds exactly when $\mathbf{c}$ is a least-squares solution. A zero result therefore certifies that $\mathbf{c}$ minimizes the sum of squared errors for this model and this criterion, and a nonzero entry shows that it does not. The check says nothing about whether the model suits the data, whether the measurements are accurate, or whether the fit holds outside the observed inputs.

In plain words A small but nonzero squared error proves nothing on its own, since another choice might be smaller still. Zero dot products with every design column prove the minimum. Keep the signs of the residuals until the check is done, because squaring them first hides mistakes.

Example For the residual $(-\tfrac16, \tfrac13, -\tfrac16)$ above, the all-ones column gives $-\tfrac16 + \tfrac13 - \tfrac16 = 0$ , and the input column $(0, 1, 2)$ gives $0 + \tfrac13 - \tfrac13 = 0$ . Both vanish, so $y = \tfrac76 + \tfrac12 t$ is the least-squares line. The same check can also find a fit. For the constant model $a$ with the same data, orthogonality to the all-ones column says

(1 - a) + (2 - a) + (2 - a) = 0,

so $a = \tfrac53$ , the mean of the observations. The residuals are $-\tfrac23$ , $\tfrac13$ , $\tfrac13$ , and the sum of squared errors is $\tfrac49 + \tfrac19 + \tfrac19 = \tfrac23$ . That is larger than $\tfrac16$ , and it could not be smaller, since every constant is a line with slope $0$ . In general the least-squares constant for equally weighted observations is their arithmetic mean.

Dependent design columns

Definition The columns of an $m \times n$ design matrix $X$ are dependent when $X\mathbf{h} = \mathbf{0}$ for some nonzero $\mathbf{h}$ in $\mathbb{R}^n$ , that is, when $\operatorname{rank} X < n$ . Because

\mathbf{h}^{\top}X^{\top}X\mathbf{h} = \lVert X\mathbf{h} \rVert^2,

the matrices $X^{\top}X$ and $X$ have the same null space. So the $n \times n$ matrix $X^{\top}X$ is invertible exactly when the columns of $X$ are independent, and then the least-squares coefficients are unique. When the columns are dependent, the normal equations still have solutions, but if $\hat{\mathbf{c}}$ is one of them, the full solution set is $\hat{\mathbf{c}} + \operatorname{Null} X$ , which contains infinitely many vectors. These are nonunique coefficients, and all of them give the same fitted values. Having more observations than coefficients does not by itself make the columns independent.

In plain words Dependent columns mean that different coefficient choices make exactly the same predictions, so the data cannot tell them apart. The best prediction is still unique. Picking one coefficient vector needs an extra rule or a redesigned model.

Example Give the three points a design matrix with two all-ones columns, so every prediction is $a + b$ . Then

X^{\top}X = \begin{bmatrix} 3 & 3 \\ 3 & 3 \end{bmatrix}, \qquad X^{\top}\mathbf{y} = \begin{bmatrix} 5 \\ 5 \end{bmatrix},

and both normal equations read $3a + 3b = 5$ . Every pair with $a + b = \tfrac53$ is a least-squares solution, for example $(\tfrac53, 0)$ , $(0, \tfrac53)$ and $(1, \tfrac23)$ , and all of them give the fitted values $(\tfrac53, \tfrac53, \tfrac53)$ . The singular matrix $X^{\top}X$ signals coefficients that cannot be told apart, not the absence of a best fit.

Check yourself

Write the design matrix for the model $y = c_1 + c_2 t^2$ at the inputs $-1$ , $0$ and $2$ . Is the model $y = c_1 e^{c_2 t}$ linear in its coefficients?

Show the answer

The row for input $t$ is $\begin{bmatrix} 1 & t^2 \end{bmatrix}$ , so

X = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ 1 & 4 \end{bmatrix}.

The first model is linear in $c_1$ and $c_2$ even though $t^2$ is not linear in $t$ . The second is not linear in $c_2$ , since that coefficient appears inside the exponential, so its predictions are not a fixed matrix times $(c_1, c_2)$ .

Find the least-squares line $y = a + bt$ for the points $(0, 1)$ , $(1, 2)$ , $(2, 2)$ and $(3, 4)$ , and check the residual.

Show the answer

The columns are $(1, 1, 1, 1)$ and $(0, 1, 2, 3)$ , and $\mathbf{y} = (1, 2, 2, 4)$ , so

X^{\top}X = \begin{bmatrix} 4 & 6 \\ 6 & 14 \end{bmatrix}, \qquad X^{\top}\mathbf{y} = \begin{bmatrix} 9 \\ 18 \end{bmatrix}.

Multiply $4a + 6b = 9$ by $3$ and $6a + 14b = 18$ by $2$ , then subtract to get $10b = 9$ . So $b = \tfrac{9}{10}$ , and $4a = 9 - \tfrac{27}{5} = \tfrac{18}{5}$ gives $a = \tfrac{9}{10}$ . The fitted values are $\tfrac{9}{10}$ , $\tfrac95$ , $\tfrac{27}{10}$ , $\tfrac{18}{5}$ and the residuals are $\tfrac{1}{10}$ , $\tfrac15$ , $-\tfrac{7}{10}$ , $\tfrac25$ . They sum to $0$ , and weighting by the inputs gives $0 + \tfrac15 - \tfrac75 + \tfrac65 = 0$ , so the residual is orthogonal to both columns. The sum of squared errors is $\tfrac{7}{10}$ .

Three measurements are all taken at the input $t = 1$ , with outputs $2$ , $3$ and $7$ . Fit the line $y = a + bt$ . Are the coefficients unique?

Show the answer

Both columns of $X$ equal $(1, 1, 1)$ , so the columns are dependent even though there are more observations than coefficients. Both normal equations read $3a + 3b = 12$ , so every pair with $a + b = 4$ is a least-squares solution, namely $(4 - s, s)$ for every real $s$ . The coefficients are not unique, but the fitted values are, namely $(4, 4, 4)$ , with residual $(-2, -1, 3)$ and sum of squared errors $14$ . Measurements at a single input cannot reveal a slope.

Least-Squares Models and Normal Equations

Key terms

Model linear in its coefficients

Design matrix

Fitted values

Residual orthogonality check

Dependent design columns

Check yourself

How this lesson connects

Builds on

Used later in