`cholupdate`

Rank-one update or downdate of a Cholesky factor.

Syntax

R1 = cholupdate(R, x)

Returns the Cholesky factor of R'*R + x*x'.

R1 = cholupdate(R, x, '-')

Returns the factor of R'*R - x*x' (a downdate).

Description

When a matrix changes by a rank-one term, recomputing its Cholesky factor from scratch costs order n^3 operations. cholupdate obtains the new factor from the old one with plane rotations in order n^2 operations, which pays off in algorithms that add one data sample at a time.

A downdate is only possible when the result stays positive definite; otherwise an error is raised.

Input arguments

R: Upper triangular Cholesky factor.
x: Column vector with size(R,1) elements.
'-': Selects the downdate. The default sign is '+'.

Output arguments

R1: Updated upper triangular factor.

Example

Adding xx' to A = R'R

A = [4 2; 2 3];
R = chol(A);
x = [1; 1];
R1 = cholupdate(R, x)
disp(norm(R1'*R1 - (A + x*x')) < 1e-12)

Output

R1 = 2×2

    2.2361    1.3416
         0    1.4832
   1

cholupdate