cholupdates.rank_1

This subpackage contains implementations of rank-1 modifications to Cholesky factorizations.

Rank-1 Up- and Downdates

Consider a symmetric positive-definite matrix \(A \in \mathbb{R}^{n \times n}\) and a vector \(v \in \mathbb{R}^n\). The vector \(v \in \mathbb{R}^n\) defines a symmetric positive semi-definite rank-1 matrix \(v v^T \in \mathbb{R}^{n \times n}\) which we can apply to \(A\) to obtain

\[A^\pm := A \pm v v^T.\]

If \(v v^T\) is added to \(A\), we refer to the operation and \(v v^T\) itself as a rank-1 update to \(A\), and to \(A^+\) as the updated matrix. Conversely, if \(v v^T\) is subtracted from \(A\), we refer to the operation and \(v v^T\) itself as a rank-1 downdate to \(A\), and to \(A^-\) as the downdated matrix.

Rank-1 updates are needed in (online) frequentist (general) linear regression, while both up- and downdates appear in (online) linear Gaussian inference, and hence in (online) Bayesian (general) linear regression, as well as in Quasi-Newton methods for unconstrained minimization.

In these applications, one usually wants to compute a Cholesky factorization of \(A^\pm\), i.e. \(A^\pm = L^\pm (L^\pm)^T\) with \(L^\pm \in \mathbb{R}^{n \times n}\) lower-triangular. Note that \(A^+\) is always symmetric and positive-definite, while, depending on the choice of \(v\), \(A^-\) need not be positive definite. Hence, rank-1 downdates are not always well-defined, in that computing a Cholesky actorization of the downdated matrix is not always possible.

If a Cholesky factor \(L\) of \(A\) is given, there are more efficient methods to compute \(L^\pm\) from \(L\) than simply running a Cholesky factorization algorithm on \(A^\pm\), which generally have complexity \(O(n^3)\). This submodule contains implementations of such methods.

Interface Functions

update(L, v[, check_diag, overwrite_L, ...])	Update a Cholesky factorization after addition of a positive-semidefinite symmetric rank-1 matrix.
downdate(L, v[, check_diag, overwrite_L, ...])	Update a Cholesky factorization after subtraction of a symmetric positive semidefinite rank-1 matrix.

Update Algorithms

update_seeger(L, v[, check_diag, ...])

Update a Cholesky factorization after addition of a positive semidefinite symmetric rank-1 matrix using the algorithm from section 2 of [Seeger, 2008].

Downdate Algorithms

downdate_seeger(L, v[, check_diag, ...])

Update a Cholesky factorization after subtraction of a positive semidefinite symmetric rank-1 matrix using the algorithm from section 3 of [Seeger, 2008].