I have a problem, I have access to a matrix $G = (A^t A)^{-1}$, but I want to compute a second matrix $\bar{G} = (\bar{A}^t \bar{A})^{-1}$, where $\bar{A} = A + b c^t$ is a rank one update of matrix $A$. I was wondering if there exist a formula to easily obtain the second matrix from the first?
I already know the Sherman-Morrison formula, I tried to use it by developing $\bar{G}$ into $ (A^t A + c b^t A + A^t b c^t + c b^t b c^t)^{-1}$ and recursively update it, but the result is too complicated.
Thank you in advance.
Best Answer
Square $A$
Let's assume $A$ is square of size $n$ and that you have access to $G$, $b$, $c$ and either $A$ or $A^{-1}$ (without $A$ or $A^{-1}$, I doubt the problem is even well defined).
You could apply Sherman-Morrison formula to $A$ alone: $$\bar{A}^{-1} = \left(A+bc^t\right)^{-1} = A^{-1}-{A^{-1}bc^t A^{-1} \over 1+c^t A^{-1}b}.$$
Then $$\bar{G} = (\bar{A}^t \bar{A})^{-1} = \bar{A}^{-1} \bar{A}^{-t} = \left(A^{-1}-{A^{-1}bc^t A^{-1} \over 1+c^t A^{-1}b}\right) \left(A^{-1}-{A^{-1}bc^t A^{-1} \over 1+c^t A^{-1}b}\right)^t. $$
Calling $d=A^{-1}b=G A^t b$ and $\alpha=1/(1 + c^t d)$, we have: $$\bar{G} = G - \alpha \, d c^t G - \alpha \, G\, c d^t + \alpha^2 \, d c^t G \, c d^t. $$
This can be $O(n^2)$ for a careful choice of the order in which the products are taken.
General $A$
For a general $m\times n$ matrix $A$, I think your approach of applying S-H recursively is a good idea. Defining $q = A^t b + \frac12 c \, b^t b$: $$ H = (A^t A + cq^t)^{-1} = G - \frac{G \, c \, q^t G}{1 + q^t G\, c} $$ $$ \bar{G} = (H^{-1} + qc^t)^{-1} = H - \frac{H \, q \, c^t H}{1 + c^t H \, q}. $$ Unless you really need to write a direct relationship from $G$ to $\bar{G}$, this cascade of two rank-one updates is perfectly fine from a computational point of view. Assuming $m\ge n$, the complexity is $O(mn)$ due to the computation of $q$.
If, for any reason, you really care about a direct relationship from $G$ to $\bar{G}$, you can define: $$ U = [q, c] \; \text{and} \; V = [c, q]^t $$ and then apply Woodbury matrix identity as follows: $$ \bar{G} = G - G U (I_2 + VGU)^{-1} V G. $$