[Math] updating of the cholesky decomposition

linear algebraMATLABmatrices

I try cholrank1 update (wikipedia) of the symmetric positive definite (SPD) matrix .

function [L] = cholupdate(L,x)
    p = length(x);
    for k=1:p
        r = sqrt(L(k,k)^2 + x(k)^2);
        c = r / L(k, k);
        s = x(k) / L(k, k);
        L(k, k) = r;
        L(k+1:p,k) = (L(k+1:p,k) + s*x(k+1:p)) / c;
        x(k+1:p) = c*x(k+1:p) - s*L(k+1:p,k);
    end
end

Get SPD matrix and factorize it:

H = J'*J
L = chol(H)';
L_updated = cholupdate(L, new_J_row');

It works well. But how can I modify algorithm when I need to do normalization of the SPD matrix?

% normalization
n = 1 ./ sqrt(diag(H));
Hn = diag(n) * H * diag(n);
Ln = chol(Hn)';

Ln_updated = ???

Best Answer

Given the cholesky decomposition $LL^T = DHD$ for some positive definite diagonal matrix $D$, another positive definite diagonal matrix $\tilde D$ and a vector $u$. You can compute the decomposition $$\tilde L \tilde L^T = \tilde D (H+uu^T) \tilde D = \tilde D H\tilde D + (\tilde D u)(\tilde D u)^T$$ as follow:

  1. Let $\bar L = \tilde D D^{-1} L$, which gives $\bar L \bar L = \tilde D H \tilde D$.
  2. Update $\bar L$ to $\tilde L$.
Related Question