13
$\begingroup$

In the model ${y} = X \beta + \epsilon$, we could estimate $\beta$ using the normal equation:

$$\hat{\beta} = (X'X)^{-1}X'y,$$ and we could get $$\hat{y} = X \hat{\beta}.$$

The vector of residuals is estimated by

$$\hat{\epsilon} = y - X \hat{\beta} = (I - X (X'X)^{-1} X') y = Q y = Q (X \beta + \epsilon) = Q \epsilon,$$

where $$Q = I - X (X'X)^{-1} X'.$$

My question is how to get the conclusion of $$\textrm{tr}(Q) = n - p.$$

$\endgroup$
12
$\begingroup$

The conclusion merely counts dimensions of vector spaces. However, it is not generally true.

The most basic properties of matrix multiplication show that the linear transformation represented by the matrix $\mathbb{H}=X(X^\prime X)^{-}X^\prime$ satisfies

$$\mathbb{H}^2 = \left(X(X^\prime X)^{-}X^\prime\right)^2=X(X^\prime X)^{-}(X^\prime X)(X^\prime X)^{-}X^\prime=\mathbb{H},$$

exhibiting it as a projection operator. Therefore its complement

$$\mathbb{Q} = 1 - \mathbb{H}$$

(as given in the question) also is a projection operator. The trace of $\mathbb{H}$ is its rank $h$ (see below), whence the trace of $\mathbb{Q}$ equals $n-h$.

From its very formula it is apparent that $\mathbb{H}$ is the matrix associated with the composition of two linear transformations $$\mathbb{J}=(X^\prime X)^{-}X^\prime$$ and $X$ itself. The first ($\mathbb{J}$) transforms the $n$-vector $y$ into the $p$-vector $\hat\beta$. The second ($X$) is a transformation from $\mathbb{R}^p$ to $\mathbb{R}^n$ given by $\hat y = X\hat \beta$. Its rank cannot exceed the smaller of those two dimensions, which in a least squares setting is always $p$ (but could be less than $p$, whenever $\mathbb{J}$ is not of full rank). Consequently the rank of the composition $\mathbb{H}=X\mathbb{J}$ cannot exceed the rank of $X$. The correct conclusion, then, is

$\text{tr} (\mathbb{Q}) = n-p$ if and only if $\mathbb{J}$ is of full rank; and in general $n \ge \text{tr} (\mathbb{Q}) \ge n-p$. In the former case the model is said to be "identifiable" (for the coefficients of $\beta$).

$\mathbb{J}$ will be of full rank if and only if $X^\prime X$ is invertible.


Geometric interpretation

$\mathbb{H}$ represents the orthogonal projection from $n$-vectors $y$ (representing the "response" or "dependent variable") onto the space spanned by the columns of $X$ (representing the "independent variables" or "covariates"). The difference $\mathbb{Q}=1-\mathbb{H}$ shows how to decompose any $n$-vector $y$ into a sum of vectors $$y = \mathbb{H}(y) + \mathbb{Q}(y),$$ where the first can be "predicted" from $X$ and the second is perpendicular to it. When the $p$ columns of $X$ generate a $p$-dimensional space (that is, are not collinear), the rank of $\mathbb{H}$ is $p$ and the rank of $\mathbb{Q}$ is $n-p$, reflecting the $n-p$ additional dimensions of variation in the response that are not represented within the independent variables. The trace gives an algebraic formula for these dimensions.


Linear Algebra Background

A projection operator on a vector space $V$ (such as $\mathbb{R}^n$) is a linear transformation $\mathbb{P}:V\to V$ (that is, an endomorphism of $V$) such that $\mathbb{P}^2=\mathbb{P}$. This makes its complement $\mathbb{Q}=1-\mathbb{P}$ a projection operator, too, because

$$\mathbb{Q}^2 = \left(1 - \mathbb{P}\right)^2 = 1 - 2\mathbb{P} + \mathbb{P}^2 = 1-2\mathbb{P}+\mathbb{P} = \mathbb{Q}.$$

All projections fix every element of their images, for whenever $v\in \text{Im}(\mathbb{P})$ we may write $v = \mathbb{P}(w)$ for some $w\in V$, whence $$w = \mathbb{P}(v) = \mathbb{P}^2(v) = \mathbb{P}(\mathbb{P}(v)) = \mathbb{P}(w).$$

Associated with any endomorphism $\mathbb{P}$ of $V$ are two subspaces: its kernel $$\text{ker}(\mathbb{P}) = \{v\in v\,|\, \mathbb{P}(v)=0\}$$ and its image $$\text{Im}(\mathbb{P}) = \{v\in v\,|\, \exists_{w\in V} \mathbb{P}(w)=v\}.$$ Every vector $v\in V$ can be written in the form $$v = w+u$$ where $w\in \text{Im}(\mathbb{P})$ and $u\in \text{Ker}(\mathbb{P})$. We may therefore construct a basis $E \cup F$ for $V$ for which $E \subset \text{Ker}(\mathbb{P})$ and $F \subset \text{Im}(\mathbb{P})$. When $V$ is finite-dimensional, the matrix of $\mathbb{P}$ in this basis will therefore be in block-diagonal form, with one block (corresponding to the action of $\mathbb{P}$ on $E$) all zeros and the other (corresponding to the action of $\mathbb{P}$ on $F$) equal to the $f$ by $f$ identity matrix, where the dimension of $F$ is $f$. The trace of $\mathbb{P}$ is the sum of the values on the diagonal and therefore must equal $f\times 1 = f$. This number is the rank of $\mathbb{P}$: the dimension of its image.

The trace of $1-\mathbb{P}$ equals the trace of $1$ (equal to $n$, the dimension of $V$) minus the trace of $\mathbb{P}$.

These results may be summarized with the assertion that the trace of a projection equals its rank.

$\endgroup$
  • $\begingroup$ Thanks very much. I learned a lot extended knowledge from your answer. $\endgroup$ – zhushun0008 Mar 9 '15 at 11:34
19
$\begingroup$

@Dougal has already given an answer, but here is another one, a bit simpler.

First, let's use the fact that $\newcommand{\tr}{\mathrm{tr}}\tr(A - B) = \tr(A) - \tr(B)$. So, we get: $$\tr(Q) = \tr(I) - \tr(X(X'X)^{-1}X').$$ Now $I$ is an $n \times n$ identity matrix, so $\tr(I) = n$. Now let's use the fact that $\tr(AB) = \tr(BA)$, that is, the trace is invariant under cyclic permutations. So, we have: $$\tr(Q) = n - \tr((X'X)^{-1}(X'X)).$$ When we multiply $(X'X)^{-1}$ with $(X'X)$, we get a $p \times p$ identity matrix, whose trace is $p$. So, we get: $$\tr(Q) = n - p.$$

$\endgroup$
6
$\begingroup$

$\newcommand\R{\mathbb R}$Assume that $n \le p$ and that $X$ is full-rank.

Consider the compact singular value decomposition $X = U \Sigma V^T$, where $\Sigma \in \R^{p \times p}$ is diagonal and $U \in \R^{n \times p}, V \in \R^{p \times p}$ have $U^T U = V^T V = V V^T = I_p$ (but note $U U^T$ is rank at most $p$ so it cannot be $I_n$). Then

\begin{align} X (X^T X)^{-1} X^T &= U \Sigma V^T (V \Sigma U^T U \Sigma V^T)^{-1} V \Sigma U^T \\&= U \Sigma V^T (V \Sigma^2 V^T)^{-1} V \Sigma U^T \\&= U \Sigma V^T V \Sigma^{-2} V^T V \Sigma U^T \\&= U U^T .\end{align}

Now, there exists a matrix $U_2 \in \R^{n \times n-p}$ such that $U_n = \begin{bmatrix}U & U_2\end{bmatrix}$ is unitary. We can write \begin{align} I - X (X^T X)^{-1} X^T &= U_n U_n^T - U U^T \\&= U_n \left( I_n - \begin{bmatrix}I_p & 0 \\ 0 & 0\end{bmatrix} \right) U_n^T \\&= U_n \begin{bmatrix}0 & 0 \\ 0 & I_{n-p}\end{bmatrix} U_n^T .\end{align} This form shows that $Q$ is positive semidefinite, and since it is a valid svd and the singular values are the square of the eigenvalues for a square symmetric matrix, also tells us that $Q$ has eigenvalues 1 (of multiplicity $n-p$) and 0 (of multiplicity $p$). Thus the trace of $Q$ is $n-p$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.