Suppose that \(\mathbf{U} \in \mathbb{R}^{n \times h}\) has its \(k\)-th column \(v\) replaced with \(\boldsymbol{w}\), giving the updated U.

(a) If \(\boldsymbol{e} \in \mathbb{R}^{h}\) denotes the unit-length vector such that \(e_{k}=\|\boldsymbol{e}\|=1\) and

\[ \boldsymbol{r}_{ \pm}:=\frac{\sqrt{2}}{2} \mathbf{U}^{\top}(\boldsymbol{w}-\boldsymbol{v})+\frac{\sqrt{2}\|\boldsymbol{w}-\boldsymbol{v}\|^{2}}{4} \boldsymbol{e} \pm \frac{\sqrt{2}}{2} \boldsymbol{e} \]
show that \[ \widetilde{\mathbf{U}}^{\top} \widetilde{\mathbf{U}}=\mathbf{U}^{\top} \mathbf{U}+\boldsymbol{r}_{+} \boldsymbol{r}_{+}^{\top}-\boldsymbol{r}_{-} \boldsymbol{r}_{-}^{\top} . \]
[Hint: You may find Exercise 16 in Chapter 6 useful.]

(b) Let \(\mathbf{B}:=\left(\mathbf{I}_{h}+\mathbf{U}^{\top} \mathbf{U}\right)^{-1}\). Use the Woodbury identity (A.15) to show that \[ \left(\mathbf{I}_{n}+\widetilde{\mathbf{U}} \widetilde{\mathbf{U}}^{\top}\right)^{-1}=\mathbf{I}_{n}-\widetilde{\mathbf{U}}\left(\mathbf{B}+\boldsymbol{r}_{+} \boldsymbol{r}_{+}^{\top}-\boldsymbol{r}_{-} \boldsymbol{r}_{-}^{\top}\right)^{-1} \widetilde{\mathbf{U}}^{\top} \]

(c) Suppose that we have stored \(\mathbf{B}\) in computer memory. Use Algorithm 6.8 .1 and parts

(a) and

(b) to write pseudo-code that updates \(\left(\mathbf{I}_{n}+\mathbf{U}^{\top} \mathbf{U}\right)^{-1}\) to \(\left(\mathbf{I}_{n}+\widetilde{\mathbf{U}} \widetilde{\mathbf{U}}^{\top}\right)^{-1}\) in \(\mathscr{O}((n+h) h)\) computing time.