Let $A$ be a real, symmetric, positive definite matrix. It has at least 500 rows, possibly much more. I compute its Cholesky decomposition, which allows me to calculate
- $det(A)$
- $A^{-1}X$ for some vector/matrix $X$
- $A^{-1}$ (I am aware of the warnings here)
Unfortunately, this operation needs to be performed a lot of times (say, a million), on matrices which are closely related but different from $A$. Formally, $A$ and any other similar matrix $A'$ differ by a full-rank update $E$ such that
$$A' = A+E \quad \frac{\|E\|}{\|A\|}\ll 1 \quad rank(E)=dim(E)$$
For now, I am computing the Cholesky decomposition of every matrix at every step. In order to speed up my calculation, I would like to use the information that two consecutive matrices are closely related. How can I do that?
I am looking for something $O(N^2)$ instead of the $O(N^3)$ of the Cholesky decomposition. Currently the matrices are dense, but I am also interested in solutions for banded sparse matrices.
EDIT Since this question was general and gave a great general answer, I will mark it as accepted. However, as far as my more specific problem is concerned, see full rank update to cholesky decomposition for multivariate normal distribution