Let \(\mathbf{X}\) be an \(n \times p\) model matrix and let \(\boldsymbol{u} \in \mathbb{R}^{p}\) be the unit-length vector with \(k\)-th entry equal to one \(\left(u_{k}=\|\boldsymbol{u}\|=1\right)\). Suppose that the \(k\)-th column of \(\mathbf{X}\) is \(\boldsymbol{v}\) and that it is replaced with a new predictor \(w\), so that we obtain the new model matrix:

\[ \widetilde{\mathbf{X}}=\mathbf{X}+(\boldsymbol{w}-\boldsymbol{v}) \boldsymbol{u}^{\top} \]

(a) Denoting

\[ \boldsymbol{\delta}:=\mathbf{X}^{\top}(\boldsymbol{w}-\boldsymbol{v})+\frac{\|\boldsymbol{w}-\boldsymbol{v}\|^{2}}{2} \boldsymbol{u} \]

show that

\[ \widetilde{\mathbf{X}}^{\top} \widetilde{\mathbf{X}}=\mathbf{X}^{\top} \mathbf{X}+\boldsymbol{u} \boldsymbol{\delta}^{\top}+\boldsymbol{\delta} \boldsymbol{u}^{\top}=\mathbf{X}^{\top} \mathbf{X}+\frac{(\boldsymbol{u}+\boldsymbol{\delta})(\boldsymbol{u}+\boldsymbol{\delta})^{\top}}{2}-\frac{(\boldsymbol{u}-\boldsymbol{\delta})(\boldsymbol{u}-\boldsymbol{\delta})^{\top}}{2} \]

In other words, \(\widetilde{\mathbf{X}}^{\top} \widetilde{\mathbf{X}}\) differs from \(\mathbf{X}^{\top} \mathbf{X}\) by a symmetric matrix of rank two.

(b) Suppose that \(\mathbf{B}:=\left(\mathbf{X}^{\top} \mathbf{X}+n \gamma \mathbf{I}_{p}\right)^{-1}\) is already computed. Explain how the ShermanMorrison formulas in Theorem A. 10 can be applied twice to compute the inverse and log-determinant of the matrix \(\widetilde{\mathbf{X}}^{\top} \widetilde{\mathbf{X}}+n \gamma \mathbf{I}_{p}\) in \(O((n+p) p)\) computing time, rather than the usual \(O\left(\left(n+p^{2}\right) p\right)\) computing time. \({ }^{3}\)

(c) Write a Python program for updating a matrix \(\mathbf{B}=\left(\mathbf{X}^{\top} \mathbf{X}+n y \mathbf{I}_{p}\right)^{-1}\) when we change the \(k\)-th column of \(\mathbf{X}\), as shown in the following pseudo-code.

Transcribed Image Text:

Algorithm 6.8.1: Updating via Sherman-Morrison Formula input: Matrices X and B, index k, and replacement w for the k-th column of X. output: Updated matrices X and B. 1 Set v RP to be the k-th column of X. 2 Set u RP to be the unit-length vector such that uk ||u|| = 1. 3 B B- 4 B B- 1+8TBu Bou B 1+uTB8 5 Update the k-th column of X with w. 6 return X, B