Suppose that [ mathbf{U}=left[boldsymbol{u}_{0}, boldsymbol{u}_{1}, ldots, boldsymbol{u}_{h-1} ight] ] where all (boldsymbol{u} in mathbb{R}^{n}) are column vectors

Suppose that

\[ \mathbf{U}=\left[\boldsymbol{u}_{0}, \boldsymbol{u}_{1}, \ldots, \boldsymbol{u}_{h-1}\right] \]

where all \(\boldsymbol{u} \in \mathbb{R}^{n}\) are column vectors and we have computed \(\left(\mathbf{I}_{n}+\mathbf{U U}^{\top}\right)^{-1}\) via the QR factorization method in Exercise 5.

If the columns of matrix \(\mathbf{U}\) are updated to

\[ \left[\boldsymbol{u}_{1}, \ldots, \boldsymbol{u}_{h-1}, \boldsymbol{u}_{h}\right] \]

show that the inverse \(\left(\mathbf{I}_{n}+\mathbf{U} \mathbf{U}^{\top}\right)^{-1}\) can be updated in \(\mathscr{O}(h n)\) time (rather than computed from scratch in \(\mathscr{O}\left(h^{2} n\right)\) time). Deduce that the computing cost of updating the Hessian approximation (9.10) is the same as that for the limited-memory BFGS Algorithm 9.4.3.

In your solution you may use the following facts from [29]. Suppose we are given the \(\mathbf{Q}\) and \(\mathbf{R}\) factors in the \(\mathrm{QR}\) factorization of a matrix \(\mathbf{A} \in \mathbb{R}^{n \times h}\). If a row/column is added to matrix \(\mathbf{A}\), then the \(\mathbf{Q}\) and \(\mathbf{R}\) factors need not be recomputed from scratch (in \(\mathscr{O}\left(h^{2} n\right)\left(h^{2} n\right)\) time), but can be updated efficiently in \(\mathscr{O}(h n)\) time. Similarly, if a row/column is removed from matrix \(A\), then the \(\mathbf{Q}\) and \(\mathbf{R}\) factors can be updated in \(\mathscr{O}\left(h^{2}\right)\) time.