The Reversed Cholesky Decomposition
Cholesky-like decomposition with upper-triangular matrices.
The Cholesky decomposition of a positive definite matrix is the unique factorization of the form such that is lower triangular with positive entries on its diagonal. We refer to as the Cholesky factor of , and denote this relationship by . Intuitively, it seems that the focus on lower triangular matrices is just a convention, and that we could alternatively consider factorizations of the form where is upper triangular with positive diagonal entries. This is no longer what is commonly called the Cholesky decomposition, but is similar in spirit. We will refer to this as the reversed Cholesky decomposition, or rCholesky for short. We call the rCholesky factor, and write . In this post, we explore this alternative factorization, and demonstrate (i.) its close connections to the Cholesky factorization of ; and (ii.) its interpretation as the Cholesky factorization under a reverse ordering of the variable indices. These connections have various applications, including in high-dimensional covariance estimation; see, e.g., (Jurek & Katzfuss, 2021) for one such example.
Connections to the Inverse Matrix
The first order of business is to ensure that we have the same uniqueness and existence properties for (2) as we do for (1). The below result shows that the rCholesky factorization inherits these properties from the Cholesky factorization.
Existence and Uniqueness.
If is positive definite, then there exists a unique decomposition of the form such that is upper triangular with positive entries on the diagonal.
Proof. Since is positive definite, then exists and is itself positive definite. Thus, there is a unique factorization of the form , where is lower triangular with positive diagonal entries. Therefore, is invertible and Setting , we obtain .
We see from the above proof that the rCholesky factor of is closely related to the Cholesky factor of . This corollary is summarized below.
Connection to Inverse Matrix.
Let be a positive definite matrix. Then \begin{align} \text{rchol}(C) &= \text{chol}(C)^{-\top} \tag{4} \newline \text{chol}(C) &= \text{rchol}(C)^{-\top}. \tag{5} \end{align}
A consequence of (4) and (5) is that we can easily transform between the Cholesky factorization of a matrix and the rCholesky factorization of its inverse.
Reverse Ordering
The Reversal Operator
As we will see, the rCholesky decomposition can be interpreted as a Cholesky decomposition of a matrix under reverse ordering. By reverse ordering, we mean that the order of both the rows and the columns of are reversed. This notion is more intuitive when viewing as a covariance matrix for some random variables , such that . We thus see that the ordering of the variables determines the ordering of the matrix. Let be the vector of variables such that . We will denote by the reversed vector. The reversal operation is linear and can thus be represented by a matrix. In particular, is given by where is the square permutation matrix with ones on the anti-diagonal; i.e., the non-main diagonal going from the lower-left to the upper-right corner. For example, if then \begin{align} P &= \begin{bmatrix} 0 & 0 & 1 \newline 0 & 1 & 0 \newline 1 & 0 & 0 \end{bmatrix}. \tag{8} \end{align}
We will make use of the following properties of the matrix .
Properties of Reversal Operator.
The matrix that reverses the order of a vector satisfies
The first property is true of any anti-diagonal matrix, and the latter two simply reflect the fact that applying the reversal operation twice results in the original vector. With these properties in hand, note that
In words, this says that the covariance matrix of the reversed vector is given by , where is the covariance of the original vector. If you prefer to avoid probabilistic language, then is simply the result of reversing the order of the columns and rows of . Reversing induces the same operation on its inverse, since where we have used (9).
Cholesky Factorization of Reversed Matrix
We now derive the form of the Cholesky and rCholesky decompositions of the reversed matrix . Notation becomes a bit confusing here, so we separate the two results for clarity.
Cholesky under reverse ordering.
Let be the rCholesky decomposition of . Then the Cholesky decomposition of is given by This can be equivalently be written as In words, this says that the Cholesky factor of is given by reversing the rCholesky factor of .
Proof. Using the fact that we have The result is now immediate upon noticing that is lower triangular and has positive diagonal entries.
rCholesky under reverse ordering.
Let be the Cholesky decomposition of . Then the rCholesky decomposition of is given by This can be equivalently be written as In words, this says that the rCholesky factor of is given by reversing the Cholesky factor of .
Proof. Using the fact that we have The result is now immediate upon noticing that is upper triangular and has positive diagonal entries.
These results tell us that we can use a Cholesky factorization of to immediately compute the rCholesky factorization of the reversed matrix . This statement is the same with the roles of Cholesky and rCholesky swapped. In (13) and (15) we can left and right multiply by to obtain the equivalent expressions \begin{align} \text{chol}(C) &= P\text{rchol}(PCP)P \tag{16} \newline \text{rchol}(C) &= P\text{chol}(PCP)P. \tag{17} \newline \end{align} See remark 1 in (Jurek & Katzfuss, 2021) for an example of an expression of this form, though the authors are decomposing in place of .
Other Resources
- Jurek, M., & Katzfuss, M. (2021). Hierarchical sparse Cholesky decomposition with applications to high-dimensional spatio-temporal filtering. https://arxiv.org/abs/2006.16901