update rule for the inverse after a rank-1 update plus scaled identity

Question

Is there an update rule for $$\left(\tilde{X}^T\tilde{X}+\alpha\cdot I\right)^{-1}$$ with $\tilde{X}=[X\;\; a]$ as a function of $A\triangleq (X^TX)^{-1}$, $X$ and $a$? I know that when $\alpha=0$ we have $$\left(\tilde{X}^T\tilde{X}\right)^{-1}= \left[ \begin{array}\; A+\frac{AX^Taa^TXA^T}{a^Ta-a^TXAX^Ta}&\; \frac{-AX^Ta}{a^Ta-a^TXAX^Ta}\\ \frac{-a^TXA^T}{a^Ta-a^TXAX^Ta} &\; \frac{1}{a^Ta-a^TXAX^Ta}\end{array}\right].$$ Is there a variation of this for when $\alpha\neq 0$?

---

Update - this can be easily done using the Schur complement, by writing

$$\tilde{X}^T\tilde{X}= \left[ \begin{array}\; X^TX+ \alpha\cdot I &\; X^Ta\\ a^TX &\; a^Ta+\alpha\end{array}\right],$$ and then using the formula for the inverse in the Wiki page.

Answer 1

No, there is no cheap ($O(n^2)$ or less) formula to update the inverse, or the LU factorization, of a matrix, after adding a multiple of the identity.

It is hard to prove a negative, but this question (and variants) get asked a lot on [scicomp.se], and the answer is invariably that there is no technique to do it; see for instance this answer.

If this were possible, many practically-relevant algorithms such as the rational Krylov algorithm would have a significant speed-up, so people have definitely been working on related themes and found nothing yet.

The closest thing you can do is performing a $O(n^3)$ precomputation on a symmetric matrix $M=M^*$ that lets you solve, in time $O(n)$ each, linear systems of the form $M+\alpha_k I$, for many values $\alpha_1,\dots,\alpha_m$: reduce $M$ to tridiagonal form $M=QTQ^*$, and use a tridiagonal solver on $M+\alpha_k I = Q(T+\alpha_k I)Q^*$. This algorithm is provably stable only for positive definite matrices, unfortunately, but that still covers many cases.

Tridiagonal reduction, i.e., finding an orthogonal $Q$ such that $M=QTQ^*$, with $T$ tridiagonal, is a part of algorithms to compute eigenvalues and is available in Lapack and many higher-level languages.

For a general nonsymmetric matrix, you can use a similar trick with Hessenberg reduction rather than tridiagonal, getting $O(n^3+mn^2)$. Hessenberg systems can be solved with QR factorization in time $O(n^2)$.