Week 4

In Problems 1 and 2, \(\bfX\in\Rbb^{n\times d}\) has rank \(r\geq1\) and compact SVD \[ \bfX=\bfU_r\Sigma_r\bfV_r^\top=\sum_{i=1}^r\sigma_i\bfu_i\bfv_i^\top, \qquad \sigma_1\geq\cdots\geq\sigma_r>0, \] with orthonormal \(\bfu_1,\ldots,\bfu_r\in\Rbb^n\) and orthonormal \(\bfv_1,\ldots,\bfv_r\in\Rbb^d\).

Problem 1

In lecture we used the column space and null space from the SVD without proving it. In this problem you will prove it.

Show that \(\Ccal(\bfX)=\operatorname{span}\{\bfu_1,\ldots,\bfu_r\}\). Hint: Recall, \(\bfX\bfv_i = \sigma_i \bfu_i\).
Conclude that \(\bfP=\bfU_r\bfU_r^\top\) is the orthogonal projection onto \(\Ccal(\bfX)\).
Show that \(\bfX\bfz=\mathbf{0}\) if and only if \(\bfV_r^\top\bfz=\mathbf{0}\).
Explain why part 3 says exactly that \(\Ncal(\bfX)=\operatorname{span}\{\bfv_1,\ldots,\bfv_r\}^\perp\).

Solution sketch

(\(\subseteq\)) For any \(\bftheta\in\Rbb^d\), \[ \bfX\bftheta=\sum_{i=1}^r\sigma_i\bfu_i(\bfv_i^\top\bftheta)=\sum_{i=1}^r\sigma_i(\bfv_i^\top\bftheta)\,\bfu_i, \] a linear combination of \(\bfu_1,\ldots,\bfu_r\). (\(\supseteq\)) Since \(\sigma_i>0\), building the left singular vectors gives \(\bfu_i=\bfX(\bfv_i/\sigma_i)\in\Ccal(\bfX)\) for each \(i\leq r\). Since \(\Ccal(\bfX)\) is a subspace, it contains every linear combination of \(\bfu_1,\ldots,\bfu_r\).
The \(\bfu_i\) are orthonormal, hence linearly independent (orthogonal sets are linearly independent), and by part 1 they span \(\Ccal(\bfX)\). So they are an orthonormal basis of \(\Ccal(\bfX)\), and the definition of the orthogonal projection gives \(\bfP=\bfU_r\bfU_r^\top\).
(\(\Leftarrow\)) If \(\bfV_r^\top\bfz=\mathbf{0}\), then \(\bfX\bfz=\bfU_r\Sigma_r(\bfV_r^\top\bfz)=\mathbf{0}\). (\(\Rightarrow\)) If \(\bfX\bfz=\mathbf{0}\), multiply on the left by \(\bfU_r^\top\) and use \(\bfU_r^\top\bfU_r=\bfI_r\): \[ \mathbf{0}=\bfU_r^\top\bfU_r\Sigma_r\bfV_r^\top\bfz=\Sigma_r\bfV_r^\top\bfz. \] Since \(\Sigma_r\) is diagonal with positive diagonal entries, it is invertible, so \(\bfV_r^\top\bfz=\mathbf{0}\).
The entries of \(\bfV_r^\top\bfz\) are \(\bfv_1^\top\bfz,\ldots,\bfv_r^\top\bfz\). So \(\bfV_r^\top\bfz=\mathbf{0}\) if and only if \(\bfz\) is orthogonal to each \(\bfv_i\), which (by linearity of the inner product) holds if and only if \(\bfz\) is orthogonal to every vector in \(\operatorname{span}\{\bfv_1,\ldots,\bfv_r\}\). Combined with part 3, \(\bfz\in\Ncal(\bfX)\) if and only if \(\bfz\in\operatorname{span}\{\bfv_1,\ldots,\bfv_r\}^\perp\).

Problem 2

Recall the Moore–Penrose pseudoinverse \[ \bfX^\dagger=\bfV_r\Sigma_r^{-1}\bfU_r^\top =\sum_{i=1}^r\frac{1}{\sigma_i}\bfv_i\bfu_i^\top \in\Rbb^{d\times n}. \] In this problem you will show that it, indeed, is almost like an inverse. You may use Problem 1.

Show that \(\bfX\bfX^\dagger=\bfU_r\bfU_r^\top\), the orthogonal projection onto \(\Ccal(\bfX)\).
Show that \(\bfX^\dagger\bfX=\bfV_r\bfV_r^\top\), and that this is the orthogonal projection onto \(\operatorname{span}\{\bfv_1,\ldots,\bfv_r\}\). (Optional) Show that \(\operatorname{span}\{\bfv_1,\ldots,\bfv_r\}=\Ncal(\bfX)^\perp\), so that \(\bfX^\dagger\bfX\) is the orthogonal projection onto \(\Ncal(\bfX)^\perp\). Hint: Problem 1, part 4 gives \(\Ncal(\bfX)=\operatorname{span}\{\bfv_1,\ldots,\bfv_r\}^\perp\). For the harder inclusion, take \(\bfw\in\Ncal(\bfX)^\perp\), write \(\bfw=\bfV_r\bfV_r^\top\bfw+(\bfw-\bfV_r\bfV_r^\top\bfw)\), and show that the second term lies in \(\Ncal(\bfX)\).
Suppose \(\operatorname{rank}(\bfX)=d\). Show directly from the SVD that \(\bfX^\dagger=(\bfX^\top\bfX)^{-1}\bfX^\top\).
Suppose \(\bfX\) is square and invertible. Show that \(\bfX^\dagger=\bfX^{-1}\).

Solution sketch

Using \(\bfV_r^\top\bfV_r=\bfI_r\), \[ \bfX\bfX^\dagger =\bfU_r\Sigma_r\bfV_r^\top\bfV_r\Sigma_r^{-1}\bfU_r^\top =\bfU_r\Sigma_r\Sigma_r^{-1}\bfU_r^\top =\bfU_r\bfU_r^\top, \] which is the orthogonal projection onto \(\Ccal(\bfX)\) by Problem 1, part 2.
Using \(\bfU_r^\top\bfU_r=\bfI_r\), \[ \bfX^\dagger\bfX =\bfV_r\Sigma_r^{-1}\bfU_r^\top\bfU_r\Sigma_r\bfV_r^\top =\bfV_r\bfV_r^\top. \] The \(\bfv_i\) are orthonormal, so by definition this is the orthogonal projection onto \(\operatorname{span}\{\bfv_1,\ldots,\bfv_r\}\).

(Optional part.) Write \(\Scal=\operatorname{span}\{\bfv_1,\ldots,\bfv_r\}\), so Problem 1, part 4 says \(\Ncal(\bfX)=\Scal^\perp\). (\(\subseteq\)) Every vector of \(\Scal\) is orthogonal to every vector of \(\Scal^\perp=\Ncal(\bfX)\), so \(\Scal\subseteq\Ncal(\bfX)^\perp\). (\(\supseteq\)) Let \(\bfw\in\Ncal(\bfX)^\perp\), and write \(\bfw=\bfa+\bfb\) with \(\bfa=\bfV_r\bfV_r^\top\bfw\in\Scal\) and \(\bfb=\bfw-\bfa\). Using \(\bfV_r^\top\bfV_r=\bfI_r\), we get \(\bfV_r^\top\bfb=\bfV_r^\top\bfw-\bfV_r^\top\bfw=\mathbf{0}\), so \(\bfb\in\Ncal(\bfX)\) by Problem 1, part 3. Since \(\bfw\perp\bfb\) and \(\bfa\perp\bfb\) (as \(\bfa\in\Scal\) and \(\bfb\in\Scal^\perp\)), \[ 0=\bfb^\top\bfw=\bfb^\top\bfa+\bfb^\top\bfb=\|\bfb\|_2^2, \] so \(\bfb=\mathbf{0}\) and \(\bfw=\bfa\in\Scal\).
If \(\operatorname{rank}(\bfX)=d\) then \(r=d\), so \(\bfV_d\in\Rbb^{d\times d}\) is square with orthonormal columns. Then \(\bfV_d^\top\) is the inverse of \(\bfV_d\), so \(\bfV_d\bfV_d^\top=\bfI_d\) as well. Now \(\bfX^\top\bfX=\bfV_d\Sigma_d\bfU_d^\top\bfU_d\Sigma_d\bfV_d^\top=\bfV_d\Sigma_d^2\bfV_d^\top\), whose inverse is \(\bfV_d\Sigma_d^{-2}\bfV_d^\top\) (multiply them to check). Therefore \[ (\bfX^\top\bfX)^{-1}\bfX^\top =\bfV_d\Sigma_d^{-2}\bfV_d^\top\bfV_d\Sigma_d\bfU_d^\top =\bfV_d\Sigma_d^{-1}\bfU_d^\top =\bfX^\dagger. \]
If \(\bfX\in\Rbb^{n\times n}\) is invertible then \(r=n=d\), so \(\bfU_r\) and \(\bfV_r\) are both square with orthonormal columns. As in part 3, this gives \(\bfU_r\bfU_r^\top=\bfI_n\) and \(\bfV_r\bfV_r^\top=\bfI_n\). So parts 1 and 2 read \(\bfX\bfX^\dagger=\bfI_n\) and \(\bfX^\dagger\bfX=\bfI_n\), which says \(\bfX^\dagger=\bfX^{-1}\).

Problem 3

In lecture we stated how means and covariances of random vectors behave under linear maps (means and covariances under linear maps) without proving it. In this problem you will prove it. Let \(\bfz\in\Rbb^m\) be a random vector, and let \(\bfA\in\Rbb^{k\times m}\) and \(\bfb\in\Rbb^k\) be fixed.

Show that \(\Ebb[\bfA\bfz+\bfb]=\bfA\,\Ebb[\bfz]+\bfb\). Hint: Proceed from the linearity of expectation of scalar valued random variables.
Show that \(\Cov(\bfA\bfz+\bfb)=\bfA\Cov(\bfz)\bfA^\top\).

Solution sketch

Entry \(i\) of \(\bfA\bfz+\bfb\) is \(\sum_{j=1}^mA_{ij}z_j+b_i\). By linearity of expectation its expectation is \(\sum_{j=1}^mA_{ij}\Ebb[z_j]+b_i\), which is entry \(i\) of \(\bfA\,\Ebb[\bfz]+\bfb\).
By part 1, \((\bfA\bfz+\bfb)-\Ebb[\bfA\bfz+\bfb]=\bfA(\bfz-\Ebb[\bfz])\). Write \(\bfM=(\bfz-\Ebb[\bfz])(\bfz-\Ebb[\bfz])^\top\), so \(\Cov(\bfz)=\Ebb[\bfM]\) and \(\Cov(\bfA\bfz+\bfb)=\Ebb[\bfA\bfM\bfA^\top]\). Entry \((i,l)\) of \(\bfA\bfM\bfA^\top\) is \(\sum_{j,s}A_{ij}M_{js}A_{ls}\), and by linearity of expectation its expectation is \(\sum_{j,s}A_{ij}\Ebb[M_{js}]A_{ls}\), which is entry \((i,l)\) of \(\bfA\,\Ebb[\bfM]\,\bfA^\top\). Therefore \[ \Cov(\bfA\bfz+\bfb) =\Ebb[\bfA\bfM\bfA^\top] =\bfA\,\Ebb[\bfM]\,\bfA^\top =\bfA\Cov(\bfz)\bfA^\top. \]

Problem 4

In lecture we computed the mean and covariance of the least squares estimator under the standard assumptions (A1)–(A3). In this problem you will see what changes when (A2) fails. Keep (A1) and (A3), but replace (A2) by \[ \Cov(\bfvarepsilon)=\sigma^2\bfW \] for some \(\sigma^2>0\) and some fixed positive semidefinite \(\bfW\in\Rbb^{n\times n}\). For example, a diagonal \(\bfW=\operatorname{diag}(w_1,\ldots,w_n)\) says the noise is still uncorrelated, but observation \(i\) has its own variance \(\sigma^2w_i\).

Show that the least squares estimator \(\widehat{\bftheta}_{\mathrm{LS}}=(\bfX^\top\bfX)^{-1}\bfX^\top\bfy\) is still unbiased, that is, \(\Ebb[\widehat{\bftheta}_{\mathrm{LS}}]=\bftheta\).
Show that \[ \Cov(\widehat{\bftheta}_{\mathrm{LS}}) =\sigma^2(\bfX^\top\bfX)^{-1}\bfX^\top\bfW\bfX(\bfX^\top\bfX)^{-1}, \] and check that this agrees with the lecture when \(\bfW=\bfI_n\).
Use Problem 2 to rewrite the covariance in part 2 as \[ \Cov(\widehat{\bftheta}_{\mathrm{LS}})=\sigma^2\bfX^\dagger\bfW(\bfX^\dagger)^\top. \]

Solution sketch

Write \(\widehat{\bftheta}_{\mathrm{LS}}=\bfA\bfy\) with the fixed matrix \(\bfA=(\bfX^\top\bfX)^{-1}\bfX^\top\). By Problem 3, \(\Ebb[\bfy]=\bfX\bftheta+\Ebb[\bfvarepsilon]=\bfX\bftheta\) and \(\Cov(\bfy)=\Cov(\bfvarepsilon)=\sigma^2\bfW\).

Only (A1) and (A3) are needed, exactly as in lecture: \[ \Ebb[\widehat{\bftheta}_{\mathrm{LS}}] =\bfA\,\Ebb[\bfy] =(\bfX^\top\bfX)^{-1}\bfX^\top\bfX\bftheta =\bftheta. \]
By Problem 3, part 2, and the symmetry of \((\bfX^\top\bfX)^{-1}\), \[ \Cov(\widehat{\bftheta}_{\mathrm{LS}}) =\bfA(\sigma^2\bfW)\bfA^\top =\sigma^2(\bfX^\top\bfX)^{-1}\bfX^\top\bfW\bfX(\bfX^\top\bfX)^{-1}. \] When \(\bfW=\bfI_n\), the middle factor is \(\bfX^\top\bfX\), which cancels one \((\bfX^\top\bfX)^{-1}\) and leaves \(\sigma^2(\bfX^\top\bfX)^{-1}\).
By (A3) and Problem 2, part 3, \(\bfX^\dagger=(\bfX^\top\bfX)^{-1}\bfX^\top=\bfA\). Since \((\bfX^\top\bfX)^{-1}\) is symmetric, \((\bfX^\dagger)^\top=\bfA^\top=\bfX(\bfX^\top\bfX)^{-1}\). Substituting into part 2 gives \(\Cov(\widehat{\bftheta}_{\mathrm{LS}})=\sigma^2\bfA\bfW\bfA^\top=\sigma^2\bfX^\dagger\bfW(\bfX^\dagger)^\top\).