Efficient algorithm of rank-one update of the Cholesky decomposition

Question

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)$?

Answer 1

Tensorflow uses the implementation recorded in Krause & Igel (2015).

reference: Krause, O., & Igel, C. (2015, January). A more efficient rank-one covariance matrix update for evolution strategies. In Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII (pp. 129-136).