Ex. 3.8

Consider the \(QR\) decomposition of the uncentered \(N\times (p+1)\) matrix \(\textbf{X}\) (whose first column is all ones), and the SVD of the \(N\times p\) centered matrix \(\tilde{\textbf{X}}\). Show that \(\textbf{Q}_2\) and \(\textbf{U}\) span the same subspace, where \(\textbf{Q}_2\) is the sub-matrix of \(\textbf{Q}\) with the first column removed. Under what circumstances will they be the same, up to sign flips?

Soln. 3.8

Let \(\textbf{x}_i=(x\_{1i}, ..., x\_{Ni})^T\in \mathbb{R}^{N\times 1}\) and \(\textbf{1} = (1,...,1)^T\in \mathbb{R}^{N\times 1}\) be the column vectors of \(\textbf{X}\).

Let \(\textbf{q}_i = (q\_{1i}, ..., q\_{Ni})^T\in \mathbb{R}^{N\times 1}\) be the column vectors of \(\textbf{Q}\).

We can write the QR decomposition of \(X\) as

\[\begin{equation} \label{eq:3-8qr} \textbf{X} = \begin{pmatrix} \textbf{1} & \textbf{x}_1 & \cdots & \textbf{x}_p\\ \end{pmatrix} = \begin{pmatrix} \textbf{q}_0 & \textbf{q}_1 & \cdots & \textbf{q}_p\\ \end{pmatrix}\textbf{R} =\textbf{Q}\textbf{R} \in \mathbb{R}^{N\times (p+1)}. \end{equation}\]

Similarly, let \(r_{ij}\) be the entry of \(\textbf{R}\) at \(i\)-th row and \(j\)-th column. Note that \(\textbf{Q}\in\mathbb{R}^{N\times (p+1)}\) and is orthogonal. The matrix \(\textbf{R}\in\mathbb{R}^{(p+1)\times(p+1)}\) is upper triangular.

By matrix multiplication we can verify that

\[\begin{equation} \textbf{1} = r_{00}\textbf{q}_0.\nonumber \end{equation}\]

Since \(\textbf{Q}\) is orthogonal, we obtain \(q_{10}=q_{20} =...=q_{N0}=\frac{1}{\sqrt N}\), i.e., \(\textbf{q}_0=\frac{1}{\sqrt N}\textbf{1}\), and \(r_{00}=\sqrt N\). Therefore, for \(j=1,...,p\), we have

\[\begin{equation} \label{eq:3-8a} \bar{q}_j = \sum_{k=1}^Nq_{ij}/N = \frac{1}{N}\textbf{1}^T\textbf{q}_j = \frac{1}{\sqrt N}\textbf{q}_0^T\textbf{q}_j = 0. \end{equation}\]

Let \(\bar x_i = \frac{1}{N}\sum_{k=1}^Nx_{ki}\) and \(\tilde{\textbf{x}}_i = \textbf{x}_i - \bar x_i \textbf{1}\). By QR decomposition of \(X\) we can verify that for \(1\le j \le p\),

\[\begin{equation} \textbf{x}_j = \sum_{k=0}^jr_{kj}\textbf{q}_k,\nonumber \end{equation}\]

so that

\[\begin{equation} \bar x_j = r_{0j}\bar q_0 + \sum_{k=1}^jr_{kj}\bar q_k=r_{0j}\bar q_0 = \frac{r_{0j}}{\sqrt N}.\nonumber \end{equation}\]

Now, we can see for \(1\le j\le p\),

\[\begin{eqnarray} \tilde{\textbf{x}}_j &=& \textbf{x}_j -\bar x_j\textbf{1}\nonumber\\ &=& \sum_{k=0}^jr_{kj}\textbf{q}_k - r_{0j}\cdot\frac{1}{\sqrt N}\textbf{1}\nonumber\\ &=& \sum_{k=0}^jr_{kj}\textbf{q}_k - r_{0j}\textbf{q}_0\nonumber\\ &=& \sum_{k=1}^jr_{kj}\textbf{q}_k.\label{eq:3-8b} \end{eqnarray}\]

Now we are ready to finish the proof.

Let

\[\begin{equation} \textbf{Q}_2 = \begin{pmatrix} \textbf{q}_1 & \cdots & \textbf{q}_p\\ \end{pmatrix}. \nonumber \end{equation}\]

We write the SVD decomposition of \(\tilde{\textbf{X}}\) as

\[\begin{equation} \tilde{\textbf{X}} = \begin{pmatrix} \tilde{\textbf{x}}_1 & \cdots & \tilde{\textbf{x}}_p\\ \end{pmatrix}=\textbf{U}\textbf{D}\textbf{V}^T\in\mathbb{R}^{N\times p}.\nonumber \end{equation}\]

Here \(\textbf{U}\) and \(\textbf{V}\) are \(N\times p\) and \(p\times p\) orthogonal matrices, with columns of \(\textbf{U}\) spanning the column space of \(\tilde{\textbf{X}}\), and the columns of \(\textbf{V}\) spanning the row space. \(\textbf{D}\) is a \(p\times p\) diagonal matrix, with diagonal entries \(d_1\ge d_2\ge ... \ge d_p\ge 0\) called the singular values of \(\tilde{\textbf{X}}\) (see page 65 and 66 in the text).

Therefore, it suffices to prove that \(\textbf{Q}_2\) spans the column space of \(\tilde{\textbf{X}}\) (because \(\textbf{U}\) does). However, note that columns in \(\textbf{Q}_2\) are orthogonal, and \(\eqref{eq:3-8b}\), the proof is complete.