The Geometry of Least Squares

Least squares as orthogonal projection. The projection theorem proved, the normal equations obtained from orthogonality without calculus, the hat matrix shown to be the symmetric idempotent matrix of rank p that depends only on the column space, leverages bounded, the split TSS = ESS + RSS and R squared as a squared cosine, nested models and extra sums of squares, the Frisch–Waugh–Lovell theorem with the general omitted-variable identity, rank-deficient designs and estimable functions, and the QR factorization with a measured comparison against the normal equations. Worked problems build a hat matrix by hand, solve a rank-deficient design, and check the extra sums of squares.

For the twelve adults of the unit's running sample, least squares fits systolic pressure as

$$\widehat{\text{pressure}} = 71.769 + 0.187\,\text{age} - 8.669\,\text{female} + 1.379\,\text{BMI},$$

where female is 1 for women and 0 for men and BMI is body mass index. Multiple Linear Regression finds such coefficients by setting the gradient of the residual sum of squares to zero. That derivation gives the answer but hides its structure. The twelve pressures form a single point in twelve-dimensional space, and every choice of coefficients gives a point in a four-dimensional flat subspace of it. Least squares picks the point of that subspace closest to the data. What does reading the fit as a closest point make evident that the calculus leaves hidden?

Orthogonal projection is the answer to that question. The closest point of a subspace to a given vector is the one whose difference from the vector is perpendicular to the subspace. That one fact yields the normal equations, the hat matrix and its properties, the decomposition of sums of squares, and the theorem that a coefficient in a multiple regression is a simple regression on residuals.

First we prove the projection theorem and read off the normal equations. Then we study the matrix that carries out the projection, and the split of the total sum of squares it produces. Next we compare nested models and prove the Frisch–Waugh–Lovell theorem. Then we treat designs whose columns are dependent, and finally how the projection is computed in practice. The article assumes the matrix form of regression from Multiple Linear Regression and the language of vectors and dot products used in Correlation: Pearson, Spearman and Kendall.

The setting

There are $n$ observations of a response $y_1, \ldots, y_n$, collected in the vector $\mathbf{y}$, and the design matrix $X$ has $n$ rows and $p$ columns. In this unit $p$ counts every column, including the column of ones $\mathbf{1}$ for the intercept; the Data Science articles write $p$ for the number of inputs and $p + 1$ for the columns. For the twelve adults, $n = 12$ and $p = 4$: ones, age, the indicator of female sex, and BMI. A coefficient vector $\mathbf{b}$ gives the fitted vector $X\mathbf{b} = b_1\mathbf{x}_1 + \cdots + b_p\mathbf{x}_p$, a linear combination of the columns $\mathbf{x}_j$. The set of all such combinations is the column space $\mathcal{C}(X)$, a subspace of $\mathbb{R}^n$. Least squares minimizes the residual sum of squares

$$\mathrm{RSS}(\mathbf{b}) = \lVert\mathbf{y} - X\mathbf{b}\rVert^2,$$

the squared distance from $\mathbf{y}$ to the point $X\mathbf{b}$ of $\mathcal{C}(X)$. So the least squares fitted vector is the point of $\mathcal{C}(X)$ closest to $\mathbf{y}$, if there is one and only one such point. The next section proves that there is.

Two vectors are orthogonal, $\mathbf{u} \perp \mathbf{v}$, when $\mathbf{u}^{\mathsf T}\mathbf{v} = 0$, and a vector is orthogonal to a subspace when it is orthogonal to every vector in it. For orthogonal vectors, $\lVert\mathbf{u} + \mathbf{v}\rVert^2 = \lVert\mathbf{u}\rVert^2 + 2\mathbf{u}^{\mathsf T}\mathbf{v} + \lVert\mathbf{v}\rVert^2 = \lVert\mathbf{u}\rVert^2 + \lVert\mathbf{v}\rVert^2$: Pythagoras's theorem in $n$ dimensions.

The closest point is the perpendicular foot

Here is the idea. Build an orthonormal basis of the subspace, project onto each basis vector separately, and add. The difference from $\mathbf{y}$ is then perpendicular to the subspace, and Pythagoras shows that any other point of the subspace is farther away.

Lemma 1 (Gram–Schmidt). Every subspace $V \ne \{\mathbf{0}\}$ of $\mathbb{R}^n$ has an orthonormal basis: vectors $\mathbf{q}_1, \ldots, \mathbf{q}_k$ of length 1, pairwise orthogonal, whose linear combinations are exactly $V$. More precisely, if $\mathbf{v}_1, \ldots, \mathbf{v}_m$ span $V$, the following process produces one: for $j = 1, \ldots, m$ in turn, form $\mathbf{w}_j = \mathbf{v}_j - \sum_{\mathbf{q}\ \text{so far}}(\mathbf{q}^{\mathsf T}\mathbf{v}_j)\,\mathbf{q}$, and if $\mathbf{w}_j \ne \mathbf{0}$ add $\mathbf{w}_j/\lVert\mathbf{w}_j\rVert$ to the list.

Proof. By induction on $j$, the vectors listed after step $j$ are orthonormal and span the same space as $\mathbf{v}_1, \ldots, \mathbf{v}_j$. It holds before step 1, with an empty list spanning $\{\mathbf{0}\}$. At step $j$, each listed $\mathbf{q}$ satisfies $\mathbf{q}^{\mathsf T}\mathbf{w}_j = \mathbf{q}^{\mathsf T}\mathbf{v}_j - \mathbf{q}^{\mathsf T}\mathbf{v}_j = 0$, using the orthonormality of the list, so a new unit vector $\mathbf{w}_j/\lVert\mathbf{w}_j\rVert$ is orthogonal to the old ones. The span is right: $\mathbf{v}_j$ is $\mathbf{w}_j$ plus a combination of the listed vectors, so it lies in the new span, and conversely $\mathbf{w}_j$ lies in the span of $\mathbf{v}_1, \ldots, \mathbf{v}_j$. If $\mathbf{w}_j = \mathbf{0}$, then $\mathbf{v}_j$ is already a combination of the list and nothing needs adding. Every subspace of $\mathbb{R}^n$ is spanned by finitely many vectors (any set of more than $n$ vectors is linearly dependent), so the process applies to $V$. $\square$

Theorem 1 (orthogonal projection). Let $V$ be a subspace of $\mathbb{R}^n$ and $\mathbf{y}$ any vector. There is exactly one $\hat{\mathbf{y}} \in V$ with $\mathbf{y} - \hat{\mathbf{y}}$ orthogonal to $V$. It is the unique point of $V$ closest to $\mathbf{y}$: for every $\mathbf{v} \in V$,

$$\lVert\mathbf{y} - \mathbf{v}\rVert^2 = \lVert\mathbf{y} - \hat{\mathbf{y}}\rVert^2 + \lVert\hat{\mathbf{y}} - \mathbf{v}\rVert^2.$$

Proof. If $V = \{\mathbf{0}\}$, take $\hat{\mathbf{y}} = \mathbf{0}$. Otherwise take an orthonormal basis $\mathbf{q}_1, \ldots, \mathbf{q}_k$ of $V$ (Lemma 1) and set $\hat{\mathbf{y}} = \sum_i(\mathbf{q}_i^{\mathsf T}\mathbf{y})\,\mathbf{q}_i$. Then $\mathbf{q}_j^{\mathsf T}(\mathbf{y} - \hat{\mathbf{y}}) = \mathbf{q}_j^{\mathsf T}\mathbf{y} - \mathbf{q}_j^{\mathsf T}\mathbf{y} = 0$ for every $j$, and a vector orthogonal to every basis vector is orthogonal to every combination of them. For $\mathbf{v} \in V$, write $\mathbf{y} - \mathbf{v} = (\mathbf{y} - \hat{\mathbf{y}}) + (\hat{\mathbf{y}} - \mathbf{v})$. The second term lies in $V$, so the two terms are orthogonal and Pythagoras gives the identity. Its last term is positive unless $\mathbf{v} = \hat{\mathbf{y}}$, so $\hat{\mathbf{y}}$ is the unique closest point. If another $\hat{\mathbf{y}}' \in V$ also had $\mathbf{y} - \hat{\mathbf{y}}' \perp V$, the identity with the roles exchanged would make each of the two points strictly closer than the other, which is impossible unless they are equal. $\square$

The vector $\hat{\mathbf{y}}$ is the orthogonal projection of $\mathbf{y}$ onto $V$, written $P_V\mathbf{y}$. The identity also says that $\mathbf{y} - P_V\mathbf{y}$ is the projection of $\mathbf{y}$ onto the orthogonal complement $V^\perp$, the set of vectors orthogonal to $V$: it lies in $V^\perp$, and its difference from $\mathbf{y}$, which is $P_V\mathbf{y}$, is orthogonal to $V^\perp$. So $\mathbb{R}^n$ splits every vector uniquely into a part in $V$ and a part in $V^\perp$.

The normal equations from orthogonality

Apply Theorem 1 with $V = \mathcal{C}(X)$. A coefficient vector $\mathbf{b}$ minimizes $\mathrm{RSS}$ exactly when $X\mathbf{b} = \hat{\mathbf{y}}$, that is, when $\mathbf{y} - X\mathbf{b}$ is orthogonal to every column of $X$:

$$X^{\mathsf T}(\mathbf{y} - X\mathbf{b}) = \mathbf{0}, \qquad\text{that is,}\qquad X^{\mathsf T}X\,\mathbf{b} = X^{\mathsf T}\mathbf{y}.$$

These are the normal equations, named for the perpendicular (normal) residual. Theorem 1 gives three facts that the calculus derivation has to argue separately.

  1. A solution always exists. $\hat{\mathbf{y}}$ lies in $\mathcal{C}(X)$, so it equals $X\mathbf{b}$ for some $\mathbf{b}$, and that $\mathbf{b}$ solves the normal equations, whatever the rank of $X$.
  2. Every solution is a minimizer, and every minimizer is a solution. No second-derivative test is needed; the closest-point identity is global.
  3. The fitted values are unique even when the coefficients are not. Any two solutions give the same $\hat{\mathbf{y}}$.

Lemma 2. $X^{\mathsf T}X$ is invertible exactly when the columns of $X$ are linearly independent, that is, when $X$ has rank $p$.

Proof. If $X^{\mathsf T}X\mathbf{a} = \mathbf{0}$, then $0 = \mathbf{a}^{\mathsf T}X^{\mathsf T}X\mathbf{a} = \lVert X\mathbf{a}\rVert^2$, so $X\mathbf{a} = \mathbf{0}$. Conversely $X\mathbf{a} = \mathbf{0}$ gives $X^{\mathsf T}X\mathbf{a} = \mathbf{0}$. So the two matrices have the same null space, and the square matrix $X^{\mathsf T}X$ is invertible exactly when that null space is $\{\mathbf{0}\}$, which is the independence of the columns. $\square$

With rank $p$, the unique solution is $\hat{\boldsymbol\beta} = (X^{\mathsf T}X)^{-1}X^{\mathsf T}\mathbf{y}$. For the twelve adults it is the vector $(71.769, 0.187, -8.669, 1.379)$ of the opening, computed by the script in exact rational arithmetic and checked against a floating-point solver. The residual vector $\mathbf{e} = \mathbf{y} - X\hat{\boldsymbol\beta}$ is orthogonal to the column of ones, so the residuals sum to zero, and orthogonal to each predictor, so they are uncorrelated with it.

The hat matrix

When $X$ has rank $p$, the fitted vector is a fixed matrix times $\mathbf{y}$:

$$\hat{\mathbf{y}} = X(X^{\mathsf T}X)^{-1}X^{\mathsf T}\mathbf{y} = H\mathbf{y}, \qquad H = X(X^{\mathsf T}X)^{-1}X^{\mathsf T}.$$

$H$ is called the hat matrix because it puts the hat on $\mathbf{y}$. It is the matrix of the projection $P_{\mathcal{C}(X)}$, and its properties are those of a projection.

Theorem 2 (the hat matrix). Let $X$ have rank $p$.

  1. $H^{\mathsf T} = H$ and $H^2 = H$; $HX = X$, and $H\mathbf{v} = \mathbf{0}$ for every $\mathbf{v} \perp \mathcal{C}(X)$.
  2. The rank of $H$ is $p$, and so is its trace.
  3. $I - H$ is the projection onto $\mathcal{C}(X)^\perp$; it is symmetric and idempotent with rank and trace $n - p$, and $\mathbf{e} = (I - H)\mathbf{y}$.
  4. $H$ depends on $X$ only through $\mathcal{C}(X)$. In particular, if $A$ is an invertible $p \times p$ matrix, then $XA$ has the same hat matrix as $X$.
  5. The diagonal entries, the leverages $h_{ii}$, satisfy $0 \le h_{ii} \le 1$ and $\sum_i h_{ii} = p$. If $\mathbf{1} \in \mathcal{C}(X)$, then $h_{ii} \ge 1/n$.

Proof. (1) Transposing, $H^{\mathsf T} = X[(X^{\mathsf T}X)^{-1}]^{\mathsf T}X^{\mathsf T} = H$, because $X^{\mathsf T}X$ is symmetric and so is its inverse. Multiplying, $H^2 = X(X^{\mathsf T}X)^{-1}(X^{\mathsf T}X)(X^{\mathsf T}X)^{-1}X^{\mathsf T} = H$, and $HX = X(X^{\mathsf T}X)^{-1}X^{\mathsf T}X = X$. If $\mathbf{v} \perp \mathcal{C}(X)$, then $X^{\mathsf T}\mathbf{v} = \mathbf{0}$ and $H\mathbf{v} = \mathbf{0}$.

(2) By (1), $H$ maps $\mathbb{R}^n$ onto $\mathcal{C}(X)$: every $H\mathbf{y}$ lies in $\mathcal{C}(X)$, and every $X\mathbf{a}$ equals $H(X\mathbf{a})$. So its rank is $\dim\mathcal{C}(X) = p$. For the trace use $\operatorname{tr}(AB) = \operatorname{tr}(BA)$: $\operatorname{tr}H = \operatorname{tr}\big((X^{\mathsf T}X)^{-1}X^{\mathsf T}X\big) = \operatorname{tr}I_p = p$.

(3) For any $\mathbf{y}$, $(I - H)\mathbf{y} = \mathbf{y} - \hat{\mathbf{y}}$, which by the remark after Theorem 1 is the projection onto $\mathcal{C}(X)^\perp$. Symmetry is clear, $(I - H)^2 = I - 2H + H^2 = I - H$, and the trace is $n - p$. For a symmetric idempotent matrix the rank equals the trace (Lemma 2 of Sampling Distributions from the Normal), so the rank is $n - p$.

(4) For every $\mathbf{y}$, $H\mathbf{y}$ is the unique vector of Theorem 1 for $V = \mathcal{C}(X)$, and the theorem mentions only $V$. Two matrices that agree on every vector are equal. If $A$ is invertible, $XA$ has the same column space as $X$: every $XA\mathbf{c}$ is $X(A\mathbf{c})$, and every $X\mathbf{b}$ is $XA(A^{-1}\mathbf{b})$.

(5) Let $\mathbf{u}_i$ be the $i$th coordinate vector. By (1), $h_{ii} = \mathbf{u}_i^{\mathsf T}H\mathbf{u}_i = \mathbf{u}_i^{\mathsf T}H^{\mathsf T}H\mathbf{u}_i = \lVert H\mathbf{u}_i\rVert^2 \ge 0$, and by Theorem 1 with $\mathbf{y} = \mathbf{u}_i$ and $\mathbf{v} = \mathbf{0}$, $\lVert H\mathbf{u}_i\rVert^2 \le \lVert\mathbf{u}_i\rVert^2 = 1$. The sum is the trace, $p$. If $\mathbf{1} \in \mathcal{C}(X)$, let $P_{\mathbf 1} = \tfrac1n J$ be the projection onto the line through $\mathbf{1}$ ($J$ is the matrix of ones). Since that line lies in $\mathcal{C}(X)$, Theorem 4 below (whose proof does not use this part) shows that $H - P_{\mathbf 1}$ is a projection matrix, so $h_{ii} = \mathbf{u}_i^{\mathsf T}P_{\mathbf 1}\mathbf{u}_i + \mathbf{u}_i^{\mathsf T}(H - P_{\mathbf 1})\mathbf{u}_i = \frac1n + \lVert(H - P_{\mathbf 1})\mathbf{u}_i\rVert^2 \ge \frac1n$. $\square$

Part 4 is the geometric content of reparametrization. Measuring age from 50 instead of 0, or coding sex by an indicator of male instead of female, multiplies $X$ on the right by an invertible matrix. The coefficients change, the hat matrix and the fitted values do not. For the twelve adults, with age measured from 50 and the male indicator in place of the female one, the intercept becomes 72.457 and the sex coefficient becomes $+8.669$ for men, the same difference with the sign reversed. The script confirms that the two hat matrices agree entry by entry.

For the twelve adults the trace of $H$ is 4.000, and the leverages run from 0.135 to 0.573. The largest belongs to adult 2, a woman of 39 with a BMI of 45.1, the highest in the sample. Leverage measures how far an observation's predictors lie from the others', and a leverage near 1 means the fit must pass close to that point, since $\hat{y}_i = \sum_j h_{ij}y_j$ gives $y_i$ the weight $h_{ii}$. The uses of leverage in diagnosing a fit, including the leave-one-out identities, are the subject of Leverage, Influence and Residual Diagnostics.

The split of the total sum of squares

When the model has an intercept, $\mathbf{1} \in \mathcal{C}(X)$, and the centered response splits into two orthogonal pieces:

$$\mathbf{y} - \bar{y}\mathbf{1} = (\hat{\mathbf{y}} - \bar{y}\mathbf{1}) + \mathbf{e}.$$

The first piece lies in $\mathcal{C}(X)$, because both $\hat{\mathbf{y}}$ and $\mathbf{1}$ do. The second is orthogonal to $\mathcal{C}(X)$. Pythagoras gives

$$\underbrace{\lVert\mathbf{y} - \bar{y}\mathbf{1}\rVert^2}_{\mathrm{TSS}} = \underbrace{\lVert\hat{\mathbf{y}} - \bar{y}\mathbf{1}\rVert^2}_{\mathrm{ESS}} + \underbrace{\lVert\mathbf{e}\rVert^2}_{\mathrm{RSS}},$$

the identity that Simple Linear Regression proves for one predictor by expanding a square. Here it holds for any number of predictors, with one proof. For the twelve adults, $\mathrm{TSS} = 2{,}310.63$, $\mathrm{ESS} = 1{,}263.09$ and $\mathrm{RSS} = 1{,}047.54$.

Theorem 3 ($R^2$ as a squared cosine). If $\mathbf{1} \in \mathcal{C}(X)$ and $\mathbf{y}$ is not constant, then $R^2 = \mathrm{ESS}/\mathrm{TSS}$ is the squared cosine of the angle between $\mathbf{y} - \bar{y}\mathbf{1}$ and $\hat{\mathbf{y}} - \bar{y}\mathbf{1}$, and equals the squared Pearson correlation of $\mathbf{y}$ and $\hat{\mathbf{y}}$.

Proof. The mean of the fitted values is $\bar{y}$, because $\mathbf{1}^{\mathsf T}\mathbf{e} = 0$ gives $\mathbf{1}^{\mathsf T}\hat{\mathbf{y}} = \mathbf{1}^{\mathsf T}\mathbf{y}$. So Pearson's coefficient of $\mathbf{y}$ and $\hat{\mathbf{y}}$ is the cosine between $\mathbf{a} = \mathbf{y} - \bar{y}\mathbf{1}$ and $\mathbf{c} = \hat{\mathbf{y}} - \bar{y}\mathbf{1}$ (Correlation: Pearson, Spearman and Kendall). Since $\mathbf{a} = \mathbf{c} + \mathbf{e}$ with $\mathbf{e} \perp \mathbf{c}$, $\mathbf{a}^{\mathsf T}\mathbf{c} = \lVert\mathbf{c}\rVert^2$, and the cosine is $\lVert\mathbf{c}\rVert^2/(\lVert\mathbf{a}\rVert\,\lVert\mathbf{c}\rVert) = \lVert\mathbf{c}\rVert/\lVert\mathbf{a}\rVert = \sqrt{\mathrm{ESS}/\mathrm{TSS}}$. (If $\mathbf{c} = \mathbf{0}$, then $R^2 = 0$ and the correlation is undefined.) $\square$

For the twelve adults $R^2 = 1{,}263.09/2{,}310.63 = 0.5466$, and the correlation of the pressures with their fitted values is 0.7394, whose square is 0.5466. With one predictor, $\hat{\mathbf{y}} - \bar{y}\mathbf{1}$ is a multiple of $\mathbf{x} - \bar{x}\mathbf{1}$, and the theorem becomes $R^2 = r^2$.

Example (R squared without an intercept). "$R^2$ is always the share of variation explained." Only when $\mathbf{1} \in \mathcal{C}(X)$. Without an intercept the residuals need not sum to zero, $\hat{\mathbf{y}} - \bar{y}\mathbf{1}$ need not be in the column space, and the cross term in the split of $\mathrm{TSS}$ need not vanish, so $1 - \mathrm{RSS}/\mathrm{TSS}$ and $\mathrm{ESS}/\mathrm{TSS}$ can disagree and the first can be negative. Some programs report instead, for a model without intercept, the uncentered ratio $\lVert\hat{\mathbf{y}}\rVert^2/\lVert\mathbf{y}\rVert^2$, which is a squared cosine of uncentered vectors, a different quantity.

Nested models and extra sums of squares

Adding a predictor enlarges the column space. How does the projection change?

Theorem 4 (nested projections). Let $V_0 \subseteq V$ be subspaces of $\mathbb{R}^n$ with projection matrices $P_0$ and $P$. Then $PP_0 = P_0P = P_0$, the difference $P - P_0$ is the projection onto $V \cap V_0^\perp$ (the part of $V$ orthogonal to $V_0$), and for every $\mathbf{y}$

$$\lVert\mathbf{y} - P_0\mathbf{y}\rVert^2 - \lVert\mathbf{y} - P\mathbf{y}\rVert^2 = \lVert(P - P_0)\mathbf{y}\rVert^2 \ge 0.$$

Proof. $P_0\mathbf{y}$ lies in $V_0 \subseteq V$, and $P$ leaves vectors of $V$ unchanged, so $PP_0 = P_0$. Transposing, with both symmetric (Theorem 2 applied to any matrix whose columns span the subspace, or directly from the orthonormal-basis formula of Theorem 1), $P_0P = P_0$. Then $(P - P_0)^2 = P - P_0 - P_0 + P_0 = P - P_0$, and $P - P_0$ is symmetric. For any $\mathbf{y}$, the vector $(P - P_0)\mathbf{y}$ lies in $V$, and it is orthogonal to $V_0$ because $P_0(P - P_0)\mathbf{y} = \mathbf{0}$ and a vector whose projection onto $V_0$ is zero is orthogonal to $V_0$ (Theorem 1). Its difference from $\mathbf{y}$, which is $(I - P)\mathbf{y} + P_0\mathbf{y}$, is orthogonal to every vector of $V \cap V_0^\perp$, being the sum of a vector orthogonal to $V$ and one in $V_0$. So by Theorem 1 it is the projection onto $V \cap V_0^\perp$. Finally $\mathbf{y} - P_0\mathbf{y} = (\mathbf{y} - P\mathbf{y}) + (P - P_0)\mathbf{y}$, the first term orthogonal to $V$ and the second in $V$, and Pythagoras gives the identity. $\square$

The left side is the drop in the residual sum of squares when the larger model replaces the smaller, the extra sum of squares of the added columns. It is never negative, which proves that $R^2$ can never fall when a column is added. The General Linear Hypothesis divides it by $\sigma^2$ and uses the theorem's orthogonality to build the $F$ test of the smaller model.

For the 5,176 adults, with $\mathrm{TSS} = 2{,}050{,}039$:

Model $R^2$ Extra sum of squares
Intercept only 0.0000
+ age 0.2362 484,125
+ female 0.2378 3,312
+ BMI 0.2580 41,497

The full fit for all 5,176 adults is

$$\widehat{\text{pressure}} = 90.05 + 0.517\,\text{age} - 1.92\,\text{female} + 0.385\,\text{BMI}.$$

The extra sums of squares depend on the order in which columns are added, because each is the squared length of a projection onto the part of the new space orthogonal to everything added before. Here age enters first and takes most of the explained variation. Unbalanced Designs and the Types of Sums of Squares treats the consequences of that order for analysis of variance.

A coefficient is a regression on residuals

What does the age coefficient 0.517 mean, with sex and BMI in the model? Theorem 4 has a corollary that answers exactly.

Theorem 5 (Frisch–Waugh–Lovell). Partition $X = [X_1\ X_2]$, with $X$ of rank $p$, and the least squares coefficients correspondingly as $\hat{\boldsymbol\beta}_1$ and $\hat{\boldsymbol\beta}_2$. Let $M_1 = I - P_1$, where $P_1$ is the projection onto $\mathcal{C}(X_1)$. Then

$$\hat{\boldsymbol\beta}_2 = \big(X_2^{\mathsf T}M_1X_2\big)^{-1}X_2^{\mathsf T}M_1\mathbf{y},$$

the least squares coefficients of the residualized response $M_1\mathbf{y}$ on the residualized columns $M_1X_2$, and the residuals of that regression equal the residuals $\mathbf{e}$ of the full regression.

The idea: remove from $\mathbf{y}$ and from $X_2$ everything that $X_1$ can explain. What remains of $X_2$ is the only part of it that can add to the fit, and the full regression's coefficient on $X_2$ measures exactly that part.

Proof. Write $\mathbf{y} = X_1\hat{\boldsymbol\beta}_1 + X_2\hat{\boldsymbol\beta}_2 + \mathbf{e}$, with $\mathbf{e}$ orthogonal to every column of $X$. Apply $M_1$, which kills $X_1\hat{\boldsymbol\beta}_1$ and leaves $\mathbf{e}$ unchanged (because $\mathbf{e} \perp \mathcal{C}(X_1)$, so $P_1\mathbf{e} = \mathbf{0}$):

$$M_1\mathbf{y} = M_1X_2\,\hat{\boldsymbol\beta}_2 + \mathbf{e}.$$

The vector $\mathbf{e}$ is orthogonal to the columns of $M_1X_2$: these columns are $X_2$ minus vectors in $\mathcal{C}(X_1)$, and $\mathbf{e}$ is orthogonal to both. So this is a decomposition of $M_1\mathbf{y}$ into a vector in $\mathcal{C}(M_1X_2)$ and one orthogonal to it, and by Theorem 1 the first is the projection of $M_1\mathbf{y}$ onto $\mathcal{C}(M_1X_2)$ and $\mathbf{e}$ is its residual. The columns of $M_1X_2$ are independent: if $M_1X_2\mathbf{a} = \mathbf{0}$, then $X_2\mathbf{a} = P_1X_2\mathbf{a} \in \mathcal{C}(X_1)$, so $X_2\mathbf{a} = X_1\mathbf{c}$ for some $\mathbf{c}$, and the independence of the columns of $X$ forces $\mathbf{a} = \mathbf{0}$. By Lemma 2 the coefficients are unique and equal $(X_2^{\mathsf T}M_1X_2)^{-1}(M_1X_2)^{\mathsf T}M_1\mathbf{y}$, which is the stated formula because $M_1$ is symmetric and idempotent. $\square$

The theorem carries the names of Frisch and Waugh (1933), whose paper compared partial time regressions with individual trends, and Lovell (1963), who related seasonal adjustment of economic series to multiple regression.

For the age coefficient, $X_2$ is the age column and $X_1$ holds the ones, female and BMI. Regressing pressure and age separately on $X_1$ and taking residuals, the slope of the pressure residuals on the age residuals is 0.5170, the multiple regression coefficient exactly. The correlation of the two residual vectors, the partial correlation of age and pressure given sex and BMI, is 0.487, against the plain correlation of 0.486. A plot of the two residual vectors against each other, the added-variable plot, shows the coefficient as a simple slope, with every point's contribution visible.

The added-variable plot for age: pressure and age, each with sex and body mass index regressed out, for the 5,176 adults. Notice that the least squares line through the residuals has slope 0.5170, exactly the age coefficient of the full model, as the Frisch–Waugh–Lovell theorem requires. The vertical band at the right is the adults recorded as 80, the survey's top code for age.
The added-variable plot for age: pressure and age, each with sex and body mass index regressed out, for the 5,176 adults. Notice that the least squares line through the residuals has slope 0.5170, exactly the age coefficient of the full model, as the Frisch–Waugh–Lovell theorem requires. The vertical band at the right is the adults recorded as 80, the survey's top code for age.

The omitted-variable identity

The same decomposition gives the exact relation between a coefficient with and without other predictors. Multiple Linear Regression proves it for one omitted predictor; here is the general form. Let $\tilde{\boldsymbol\beta}_1 = (X_1^{\mathsf T}X_1)^{-1}X_1^{\mathsf T}\mathbf{y}$ be the coefficients from $X_1$ alone, and $D = (X_1^{\mathsf T}X_1)^{-1}X_1^{\mathsf T}X_2$ the coefficients of each column of $X_2$ regressed on $X_1$. Then

$$\tilde{\boldsymbol\beta}_1 = \hat{\boldsymbol\beta}_1 + D\,\hat{\boldsymbol\beta}_2.$$

Proof. Multiply $\mathbf{y} = X_1\hat{\boldsymbol\beta}_1 + X_2\hat{\boldsymbol\beta}_2 + \mathbf{e}$ on the left by $(X_1^{\mathsf T}X_1)^{-1}X_1^{\mathsf T}$, and use $X_1^{\mathsf T}\mathbf{e} = \mathbf{0}$. $\square$

For the 5,176 adults, the simple slope of pressure on age is 0.5223. Regressing female and BMI on age (with intercept) gives slopes $\delta = -0.00055$ and $0.01098$: the women are slightly younger on average and BMI rises slightly with age. The identity reads $0.5223 = 0.5170 + (-1.92)(-0.00055) + 0.385 \times 0.01098$, with the two adjustment terms equal to 0.0011 and 0.0042. Here the adjustment is small because age is nearly uncorrelated with the other two predictors. In the diabetes study of Multiple Linear Regression the same identity moves the BMI coefficient from 10.23 to 8.52.

When the columns are dependent

Coding sex with both indicators, female and male, alongside the column of ones, makes the columns dependent: female plus male equals the ones column. Then $X$ has rank $p - 1$, $X^{\mathsf T}X$ is singular by Lemma 2, and the normal equations have infinitely many solutions. By the facts of the normal-equations section, they all give the same fitted values.

Every solution has the form $\mathbf{b} + \mathbf{t}$ with $\mathbf{b}$ one solution and $X\mathbf{t} = \mathbf{0}$, since the difference of two solutions satisfies $X^{\mathsf T}X\mathbf{t} = \mathbf{0}$, hence $X\mathbf{t} = \mathbf{0}$ by the proof of Lemma 2. For the twelve adults with columns (ones, age, female, male, BMI), the null space is spanned by $(1, 0, -1, -1, 0)$: adding $t$ to the intercept and subtracting $t$ from both sex coefficients changes nothing. A conventional choice is the solution of smallest length. By Theorem 1 applied in $\mathbb{R}^p$, it is unique: the solutions form the set $\mathbf{b} + N$, where $N$ is the null space, and the shortest is $\mathbf{b}$ minus its projection onto $N$, the one solution orthogonal to $N$. It is the solution given by the Moore–Penrose generalized inverse of $X$ (Penrose, 1955), which numerical libraries compute. For the twelve adults it is $(44.956, 0.187, 18.143, 26.813, 1.379)$. Its sex coefficients mean nothing alone, but their difference, $18.14339 - 26.81275 = -8.66936$, is the female coefficient $-8.669$ of the full-rank fit.

Which combinations of coefficients does the data determine? A linear function $\mathbf{c}^{\mathsf T}\boldsymbol\beta$ is called estimable when $\mathbf{c}$ is a combination of the rows of $X$, so that $\mathbf{c}^{\mathsf T}\boldsymbol\beta$ is a combination of the means of the observations.

Theorem 6 (estimable functions). $\mathbf{c}^{\mathsf T}\mathbf{b}$ takes the same value for every solution $\mathbf{b}$ of the normal equations exactly when $\mathbf{c}$ lies in the row space of $X$, the column space of $X^{\mathsf T}$.

Proof. The solutions are one solution plus the null space $N = \{\mathbf{t}: X\mathbf{t} = \mathbf{0}\}$, so $\mathbf{c}^{\mathsf T}\mathbf{b}$ is constant over them exactly when $\mathbf{c} \perp N$. The null space is the orthogonal complement of the row space: $X\mathbf{t} = \mathbf{0}$ says exactly that $\mathbf{t}$ is orthogonal to every row. A vector orthogonal to $\mathcal{C}(X^{\mathsf T})^\perp$ lies in $\mathcal{C}(X^{\mathsf T})$, by Theorem 1: its projection onto $\mathcal{C}(X^{\mathsf T})^\perp$ is orthogonal to itself, hence zero. $\square$

The female-minus-male difference has $\mathbf{c} = (0, 0, 1, -1, 0)$, which is orthogonal to $(1, 0, -1, -1, 0)$ and so, by Theorem 6, estimable. It is the difference between the rows that a woman and a man of the same age and BMI would have. The intercept alone, $\mathbf{c} = (1, 0, 0, 0, 0)$, is not orthogonal to $(1, 0, -1, -1, 0)$, so it is not. The Gauss–Markov Theorem shows that for an estimable function, the common value $\mathbf{c}^{\mathsf T}\mathbf{b}$ is the best linear unbiased estimate.

Computing the projection

If the columns of $X$ are orthonormal, $X^{\mathsf T}X = I$ and the coefficients are simply $\hat\beta_j = \mathbf{x}_j^{\mathsf T}\mathbf{y}$, one dot product each, with no interaction between columns. Lemma 1 turns any full-rank $X$ into that case. Applying Gram–Schmidt to the columns in order gives orthonormal $\mathbf{q}_1, \ldots, \mathbf{q}_p$ with each $\mathbf{x}_j$ a combination of $\mathbf{q}_1, \ldots, \mathbf{q}_j$. In matrix form,

$$X = QR,$$

where $Q$ is $n \times p$ with orthonormal columns and $R$ is $p \times p$ upper triangular, with $r_{jj} = \lVert\mathbf{w}_j\rVert > 0$. Then $H = QQ^{\mathsf T}$ (Theorem 2, part 4, with $A = R^{-1}$), and the normal equations $R^{\mathsf T}Q^{\mathsf T}QR\mathbf{b} = R^{\mathsf T}Q^{\mathsf T}\mathbf{y}$ reduce to the triangular system $R\mathbf{b} = Q^{\mathsf T}\mathbf{y}$, solved by back substitution.

Gram–Schmidt as written is not the only way to compute $Q$ and $R$, and in floating-point arithmetic it need not be the most accurate. On the quartic design of the check below, the columns it produced had inner products departing from those of an orthonormal set by up to $3.1 \times 10^{-11}$, against $6.8 \times 10^{-15}$ for the QR routine of NumPy; that is one computation, not a general rate. Householder (1958) triangularized a matrix by unitary transformations, and Golub (1965) gave numerical methods for linear least squares problems. Why not solve the normal equations directly? Their matrix squares the difficulty. The condition number of a full-rank matrix, the ratio of its largest to its smallest singular value, is a measure of how sensitive a solution computed from it can be to small changes in the data; the singular values of $X$ are the square roots of the eigenvalues of $X^{\mathsf T}X$, and Multivariate Statistics is the home of the singular value decomposition. So the condition number of $X^{\mathsf T}X$, the ratio of its largest to its smallest eigenvalue, is the square of that of $X$.

The check. Fit pressure to a quartic in age, with columns $1, \text{age}, \ldots, \text{age}^4$, for the 5,176 adults. The condition number of $X$ is 852,211,099, so that of $X^{\mathsf T}X$ is about $7.3 \times 10^{17}$. The script solves the problem exactly in rational arithmetic and compares two double-precision solutions with it. Solving the normal equations gives coefficients whose largest relative error is $3.6 \times 10^{-10}$; solving $R\mathbf{b} = Q^{\mathsf T}\mathbf{y}$ from a QR factorization gives $2.7 \times 10^{-13}$, more than a thousand times smaller. Both are far smaller than a condition number of $7.3 \times 10^{17}$ would suggest, since that number exceeds $1/u$, where $u = 1.1 \times 10^{-16}$ is the unit roundoff of double precision. Most of the condition number comes from the scales of the columns: $\text{age}^4$ reaches $80^4 = 40{,}960{,}000$ while the column of ones is 1. With each column scaled to unit length, the condition number of $X$ is 1,877 and that of $X^{\mathsf T}X$ about $3.5 \times 10^{6}$, and the product of the latter with $u$ is $4 \times 10^{-10}$, close to the error observed for the normal equations. That the computed solutions are insensitive to the scales of the columns, which this agreement suggests, is not proved here and was not tested beyond this design. The remedy that matters more is to change the columns: with age centered at its mean and divided by its standard deviation, the condition number of the quartic's $X$ falls to 15.8. By Theorem 2, part 4, the fitted values are the same, since the new columns span the same space.

A last generalization uses another inner product. Weighted least squares minimizes $\sum_i w_i(y_i - \mathbf{x}_i^{\mathsf T}\mathbf{b})^2 = (\mathbf{y} - X\mathbf{b})^{\mathsf T}W(\mathbf{y} - X\mathbf{b})$ with $W$ diagonal and positive. With the inner product $\langle\mathbf{u}, \mathbf{v}\rangle_W = \mathbf{u}^{\mathsf T}W\mathbf{v}$ every result above holds with orthogonality, lengths and symmetry taken in that inner product (the weighted hat matrix $X(X^{\mathsf T}WX)^{-1}X^{\mathsf T}W$ is not symmetric in the ordinary sense). Equivalently, apply the results to $W^{1/2}\mathbf{y}$ and $W^{1/2}X$, where $W^{1/2}$ has the square roots of the weights on its diagonal: their ordinary least squares fit is the weighted one. Results stated without reference to $\mathbf{1}$, $1/n$ or the plain mean carry over in that transformed form (the projection theorem, the normal equations, Lemma 2 with $X^{\mathsf T}WX$, the trace $p$, nested projections, Frisch–Waugh–Lovell, estimability); those that name $1/n$ or the plain mean, such as the lower bound on leverages and $R^2$, change form and are not restated here. The normal equations become $X^{\mathsf T}WX\mathbf{b} = X^{\mathsf T}W\mathbf{y}$. The same holds for any symmetric positive definite $W$, with a factor $L$ such that $W = L^{\mathsf T}L$ in place of $W^{1/2}$. The Gauss–Markov Theorem shows which $W$ to choose when the errors have unequal variances or are correlated.

What is proved here, what is cited, what is computed

Proved here. The Gram–Schmidt process (Lemma 1); the projection theorem (Theorem 1); the normal equations as the condition of orthogonality, with existence of a solution for every design and uniqueness of the fitted values; the invertibility of $X^{\mathsf T}X$ (Lemma 2); the properties of the hat matrix, including its rank and trace, its dependence only on the column space, and the bounds on leverages (Theorem 2); the split $\mathrm{TSS} = \mathrm{ESS} + \mathrm{RSS}$ and $R^2$ as a squared cosine and squared correlation (Theorem 3); nested projections and extra sums of squares (Theorem 4); the Frisch–Waugh–Lovell theorem (Theorem 5) and the omitted-variable identity; the characterization of estimable functions (Theorem 6); the QR form of the solution.

Cited. That a symmetric idempotent matrix has rank equal to its trace (Lemma 2 of Sampling Distributions from the Normal); the singular values and the condition number, from linear algebra; the name of the Moore–Penrose inverse (Penrose, 1955) and that library routines for it return the minimum-length solution, which the script checks; the numerical methods of Householder (1958) and Golub (1965).

Computed. The fits, hat matrices, sums of squares, residual regressions and minimum-length solution are computed by the script tools/experiments/statistics/least-squares-geometry.py, the coefficients in exact rational arithmetic. The comparison of the normal equations with QR, the condition numbers before and after scaling the columns, and the loss of orthogonality of Gram–Schmidt are computations on one design, observations and not general rates; the agreement of the scaled condition number with the observed error is untested beyond that design. The figure is drawn by tools/figures/least-squares-geometry.py from the same data.

Worked problems

The problems use the unit's twelve adults and the population, chosen to exercise the hat matrix, estimability and nested projections. Every number is recomputed by the article's script.

Problem 1 (a hat matrix by hand). Adults 7 to 10 of the twelve are aged 19, 21, 28 and 27, with pressures $320/3$, $334/3$, $358/3$ and $292/3$ mm Hg. For the straight-line regression of pressure on age, find the hat matrix, check its trace, and compute the fitted values from it.

Solution. With one predictor and an intercept, $h_{ij} = \frac1n + \frac{(x_i - \bar{x})(x_j - \bar{x})}{S_{xx}}$. To see it, take the orthonormal basis $\mathbf{1}/\sqrt{n}$ and $(\mathbf{x} - \bar{x}\mathbf{1})/\sqrt{S_{xx}}$ of $\mathcal{C}(X)$ (orthogonal because the deviations sum to zero) and apply the formula of Theorem 1, which gives $H = \frac1n J + (\mathbf{x} - \bar{x}\mathbf{1})(\mathbf{x} - \bar{x}\mathbf{1})^{\mathsf T}/S_{xx}$. Here $\bar{x} = 95/4 = 23.75$, the deviations are $-19/4$, $-11/4$, $17/4$ and $13/4$, and $S_{xx} = 940/16 = 58.75$. So $h_{ij} = \frac14 + \frac{d_id_j}{940}$ with $d = (-19, -11, 17, 13)$, which gives

$$H = \frac{1}{235}\begin{pmatrix} 149 & 111 & -22 & -3 \\ 111 & 89 & 12 & 23 \\ -22 & 12 & 131 & 114 \\ -3 & 23 & 114 & 101 \end{pmatrix}.$$

The leverages are $149/235 = 0.634$, $89/235 = 0.379$, $131/235 = 0.557$ and $101/235 = 0.430$; their sum is $470/235 = 2 = p$. The youngest adult, farthest from the mean age, has the largest leverage, and the adult aged 21, whose deviation $-11/4$ is the smallest in absolute value, has the smallest. Multiplying $H$ by the pressures gives fitted values 107.80, 108.17, 109.44 and 109.26. They lie on the line $104.355 + (128/705)\,\text{age}$, with slope $S_{xy}/S_{xx} = (32/3)/(235/4) = 128/705 = 0.1816$.

Problem 2 (a rank-deficient design). For the twelve adults with columns (ones, age, female, male, BMI), describe every least squares solution and show which of the following are estimable: the female-minus-male difference; the age coefficient; the intercept.

Solution. The solutions are $(44.956 + t,\ 0.187,\ 18.143 - t,\ 26.813 - t,\ 1.379)$ for all real $t$, and the first two functions are estimable, the third is not. The minimum-length solution $(44.956, 0.187, 18.143, 26.813, 1.379)$ is one solution, and the null space of $X$ is spanned by $(1, 0, -1, -1, 0)$, because the ones column equals female plus male and the columns are otherwise independent (rank 4). By Theorem 6, $\mathbf{c}^{\mathsf T}\boldsymbol\beta$ is estimable exactly when $\mathbf{c} \perp (1, 0, -1, -1, 0)$. For the difference, $\mathbf{c} = (0, 0, 1, -1, 0)$ gives $\mathbf{c}^{\mathsf T}(1, 0, -1, -1, 0) = -1 + 1 = 0$, so it is estimable, with value $-8.669$ for every $t$. For age, $\mathbf{c} = (0, 1, 0, 0, 0)$ is orthogonal, estimable, value 0.187. For the intercept, $\mathbf{c}^{\mathsf T}(1, 0, -1, -1, 0) = 1$, so it changes with $t$ and is not estimable. The intercept plus the female coefficient, the mean pressure of a woman with age and BMI zero, is estimable: $1 - 1 = 0$.

Problem 3 (extra sums of squares add up). Show that for nested models $V_0 \subset V_1 \subset V_2 \subset V_3$ the extra sums of squares add to $\mathrm{ESS}$ of the largest model when $V_0$ is the line through $\mathbf{1}$, and check it on the table for the 5,176 adults.

Solution. By Theorem 4, $\lVert(P_{k} - P_{k-1})\mathbf{y}\rVert^2 = \mathrm{RSS}_{k-1} - \mathrm{RSS}_k$, so the sum over $k = 1, 2, 3$ telescopes to $\mathrm{RSS}_0 - \mathrm{RSS}_3$. The model $V_0$ fits the mean, so $\mathrm{RSS}_0 = \mathrm{TSS}$, and $\mathrm{TSS} - \mathrm{RSS}_3 = \mathrm{ESS}_3$ by the split of the total sum of squares. In the table, $484{,}125 + 3{,}312 + 41{,}497 = 528{,}934$, and the script computes $\mathrm{ESS}_3 = \lVert\hat{\mathbf{y}} - \bar{y}\mathbf{1}\rVert^2 = 528{,}934$ directly from the full fit. Dividing by $\mathrm{TSS} = 2{,}050{,}039$ gives $R^2 = 0.2580$, the last row of the table.

Problem 4 (leverage at least 1/n). Prove that in a model with an intercept every leverage is at least $1/n$, and that $h_{ii} = 1/n$ exactly when the predictors of observation $i$ equal their means.

Solution. By Theorem 4 with $V_0$ the line through $\mathbf{1}$ and $V = \mathcal{C}(X)$, $H = P_{\mathbf 1} + (H - P_{\mathbf 1})$ with both terms projections, so $h_{ii} = \frac1n + \mathbf{u}_i^{\mathsf T}(H - P_{\mathbf 1})\mathbf{u}_i = \frac1n + \lVert(H - P_{\mathbf 1})\mathbf{u}_i\rVert^2 \ge \frac1n$. Equality holds exactly when $(H - P_{\mathbf 1})\mathbf{u}_i = \mathbf{0}$. The space $V \cap V_0^\perp$ is spanned by the centered columns $\mathbf{x}_j - \bar{x}_j\mathbf{1}$, and $(H - P_{\mathbf 1})\mathbf{u}_i = \mathbf{0}$ means $\mathbf{u}_i$ is orthogonal to that space, that is, $x_{ij} - \bar{x}_j = 0$ for every predictor $j$. In Problem 1 no adult is at the mean age, and every leverage exceeds $\frac14$.

Summary

Result Statement
Projection theorem the closest point of $V$ is the unique $\hat{\mathbf{y}} \in V$ with $\mathbf{y} - \hat{\mathbf{y}} \perp V$
Normal equations $X^{\mathsf T}X\mathbf{b} = X^{\mathsf T}\mathbf{y}$; always solvable; fitted values unique
Hat matrix $H = X(X^{\mathsf T}X)^{-1}X^{\mathsf T}$: symmetric, idempotent, trace $p$, depends only on $\mathcal{C}(X)$; $0 \le h_{ii} \le 1$
Sums of squares $\mathrm{TSS} = \mathrm{ESS} + \mathrm{RSS}$ with an intercept; $R^2 = \operatorname{corr}(\mathbf{y}, \hat{\mathbf{y}})^2$
Nested models $\mathrm{RSS}_0 - \mathrm{RSS} = \lVert(P - P_0)\mathbf{y}\rVert^2$
Frisch–Waugh–Lovell $\hat{\boldsymbol\beta}_2$ is the regression of $M_1\mathbf{y}$ on $M_1X_2$
Omitted variables $\tilde{\boldsymbol\beta}_1 = \hat{\boldsymbol\beta}_1 + D\hat{\boldsymbol\beta}_2$
Estimability $\mathbf{c}^{\mathsf T}\boldsymbol\beta$ is determined exactly when $\mathbf{c} \in \mathcal{C}(X^{\mathsf T})$
QR $X = QR$: $H = QQ^{\mathsf T}$, $R\hat{\boldsymbol\beta} = Q^{\mathsf T}\mathbf{y}$

What we have learned

Least squares is orthogonal projection onto the column space of the design. The projection theorem gives the normal equations as a statement of perpendicularity, guarantees a solution for every design, and makes the fitted values unique even when the coefficients are not. The hat matrix is the projection's matrix: symmetric, idempotent, of trace $p$, and fixed by the column space alone, so reparametrizing changes coefficients and never fits. Pythagoras splits the total sum of squares, $R^2$ is a squared cosine, nested models differ by the squared length of a projection, and a multiple regression coefficient is a simple regression on residuals.

All of this is geometry of the data and needs no probability. The question of how good the coefficients are as estimates of the true ones needs a model for the errors. The Gauss–Markov Theorem adds the weakest useful one, uncorrelated errors with a common variance, and proves that under it the projection gives the best linear unbiased estimates.

References

  • Frisch, R., and Waugh, F. V. (1933). Partial time regressions as compared with individual trends. Econometrica, 1(4), 387–401. record
  • Golub, G. (1965). Numerical methods for solving linear least squares problems. Numerische Mathematik, 7(3), 206–216. record
  • Householder, A. S. (1958). Unitary triangularization of a nonsymmetric matrix. Journal of the ACM, 5(4), 339–342. record
  • Lovell, M. C. (1963). Seasonal adjustment of economic time series and multiple regression analysis. Journal of the American Statistical Association, 58(304), 993–1010. record
  • Penrose, R. (1955). A generalized inverse for matrices. Mathematical Proceedings of the Cambridge Philosophical Society, 51(3), 406–413. record