cholUpdate: Different Cholesky factor updates

Description

Provides functions that implements different types of updates of a Cholesky factor that includes rank-one update, single row/column deletion update and a block deletion update.

Usage

cholUpdateRankOne(A, v, alpha, beta, lower = TRUE)
cholUpdateDel(A, del.index, lower = TRUE)
cholUpdateDelBlock(A, del.start, del.end, lower = TRUE)

Value

An $m \times m$ lower-triangular matrix with $m = n$ in case of cholUpdateRankOne(), $m = n - 1$ in case of cholUpdateDel(), and, $m = n - n_{k}$ in case of cholUpdateDelBlock() where $n_{k}$ is the size of the block removed.

Arguments

A: an $n \times n$ triangular matrix
v: an $n \times 1$ matrix/vector
alpha: scalar; if not supplied, default is 1
beta: scalar; if not supplied, default is 1
lower: logical; if A is lower-triangular or not
del.index: an integer from 1 to $n$ indicating the row/column to be deleted
del.start: an integer from 1 to $n$ indicating the first row/column of a block to be deleted, must be at least 1 less than del.end
del.end: an integer from 1 to $n$ indicating the last row/column of a block to be deleted, must be at least 1 more than del.start

Author

Soumyakanti Pan span18@ucla.edu,
Sudipto Banerjee sudipto@ucla.edu

Details

Suppose $B = A A^{⊤}$ is a $n \times n$ matrix with $A$ being its lower-triangular Cholesky factor. Then rank-one update corresponds to finding the Cholesky factor of the matrix $C = α B + β v v^{⊤}$ for some $α, β \in R$ given $A$ (see, Krause and Igel 2015). Similarly, single row/column deletion update corresponds to finding the Cholesky factor of the $(n - 1) \times (n - 1)$ matrix $B_{i}$ which is obtained by removing the $i$ -th row and column of $B$ , given $A$ for some $i - 1, \dots, n$ . Lastly, block deletion corresponds to finding the Cholesky factor of the $(n - n_{k}) \times (n - n_{k})$ matrix $B_{I}$ for a subset $I$ of ${1, \dots, n}$ containing $n_{k}$ consecutive indices, given the factor $A$ .

References

Oswin Krause and Christian Igel. 2015. "A More Efficient Rank-one Covariance Matrix Update for Evolution Strategies". In Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15). Association for Computing Machinery, New York, NY, USA, 129-136. tools:::Rd_expr_doi("10.1145/2725494.2725496").

Examples

Run this code

n <- 10
A <- matrix(rnorm(n^2), n, n)
A <- crossprod(A)
cholA <- chol(A)

## Rank-1 update
v <- 1:n
APlusvvT <- A + tcrossprod(v)
cholA1 <- t(chol(APlusvvT))
cholA2 <- cholUpdateRankOne(cholA, v, lower = FALSE)
print(all(abs(cholA1 - cholA2) < 1E-9))

## Single Row-deletion update
ind <- 2
A1 <- A[-ind, -ind]
cholA1 <- t(chol(A1))
cholA2 <- cholUpdateDel(cholA, del.index = ind, lower = FALSE)
print(all(abs(cholA1 - cholA2) < 1E-9))

## Block-deletion update
start_ind <- 2
end_ind <- 6
del_ind <- c(start_ind:end_ind)
A1 <- A[-del_ind, -del_ind]
cholA1 <- t(chol(A1))
cholA2 <- cholUpdateDelBlock(cholA, start_ind, end_ind, lower = FALSE)
print(all(abs(cholA1 - cholA2) < 1E-9))

Run the code above in your browser using DataLab

Data Engineering and BI courses are free this week!