Efficient algorithm of rank-one update of the Cholesky decomposition

1.7k Views Asked by At

Suppose that I have a symmetric positive definite matrix $X$ and that I Cholesky-decompose it

$$ X = L L^T $$

Now, given a vector $v$, suppose we want to decompose the following matrix using the Cholesky decomposition:

$$ X + v v^T = M M^T $$

I know the complexity of the Cholesky decomposition is $O(n^3)$. Is there a algorithm to compute $M$ given $X$, $L$, $v$, that has a complexity less than $O(n^3)$?