According to the docs on lowrankupdate!, I can compute the cholesky factor of A + vv' in \mathcal{O}(n^2) time by updating an existing cholesky factor of A.
How would this syntax work if I want the cholesky factor of A + e_i * e_j'? Here e_i and e_j are zero everywhere except it is 1 at the i or j th position. Clearly e_i * e_j' is a rank 1 matrix, but I don’t think it is possible to write e_i e_j' = vv' for some v right?
Actually, what I really need is update according to A + e_i * e_j' + e_j * e_i', i.e. a rank 2 update. Is this achievable?
A condition to have Cholesky decompositions is that the matrix is positive-definite which requires in particular: symmetric (real case) or Hermitian (complex case). The matrix A + e_i e_j^T would break this assumption.
However, adding A + e_i e_j^T + e_j e_i^T stays at least symmetric/Hermitian. (But might fail to be positive-definite.)
You could use three steps:
A + (e_i + e_j) (e_i + e_j)^T - e_i e_i^T - e_j e_j^T
That should correspond to one low-rank update and two downgrades, kind of like
a = randn(3,3)
A = a' * a
ei = [1.0, 0, 0]; ej = [0.0, 1, 0]
C = cholesky(A)
lowrankupdate!(C, ei + ej)
lowrankdowndate!(C, ei)
lowrankdowndate!(C, ej)
However, this will fail if a non-positive-definite matrix occurs as any of the results.
3 Likes
Beautiful. Thank you so much.