The Reversed Cholesky Decomposition

Cholesky-like decomposition with upper-triangular matrices.

The Cholesky decomposition of a positive definite matrix CC is the unique factorization of the form C=LL,(1) C = LL^\top, \tag{1} such that LL is lower triangular with positive entries on its diagonal. We refer to LL as the Cholesky factor of CC, and denote this relationship by L:=chol(C)L := \text{chol}(C). Intuitively, it seems that the focus on lower triangular matrices is just a convention, and that we could alternatively consider factorizations of the form C=UU,(2) C = UU^\top , \tag{2} where UU 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 UU the rCholesky factor, and write U:=rchol(C)U := \text{rchol}(C). In this post, we explore this alternative factorization, and demonstrate (i.) its close connections to the Cholesky factorization of C1C^{-1}; 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 CC is positive definite, then there exists a unique decomposition of the form C=UUC = UU^\top such that UU is upper triangular with positive entries on the diagonal.

Proof. Since CC is positive definite, then C1C^{-1} exists and is itself positive definite. Thus, there is a unique factorization of the form C1=LLC^{-1} = LL^{\top}, where LL is lower triangular with positive diagonal entries. Therefore, LL is invertible and C=LL1.(3) C = L^{-\top}L^{-1}. \tag{3} Setting U:=LU := L^{-\top}, we obtain C=UUC = UU^\top. \qquad \blacksquare

We see from the above proof that the rCholesky factor of CC is closely related to the Cholesky factor of C1C^{-1}. This corollary is summarized below.

Connection to Inverse Matrix.
Let CC 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 CC are reversed. This notion is more intuitive when viewing CC as a n×nn \times n covariance matrix for some random variables x1,,xnx_1, \dots, x_n, such that Cij=Cov[xi,xj]C_{ij} = \text{Cov}[x_i,x_j]. We thus see that the ordering of the variables determines the ordering of the matrix. Let x:=(x1,,xn)x := (x_1, \dots, x_n)^\top be the vector of variables such that C=Cov[x]C = \text{Cov}[x]. We will denote by x~:=(xn,,x1)(6) \tilde{x} := (x_n, \dots, x_1)^\top \tag{6} the reversed vector. The reversal operation xx~x \mapsto \tilde{x} is linear and can thus be represented by a matrix. In particular, x~\tilde{x} is given by x~=Px(7) \tilde{x} = Px \tag{7} where PP 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 n=3n=3 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 PP.

Properties of Reversal Operator.
The matrix PP that reverses the order of a vector satisfies P=P,P=P1,P2=P(9) P = P^\top, \qquad P = P^{-1}, \qquad P^2 = P \tag{9}

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 C~:=Cov[x~]=Cov[Px]=PCov[x]P=PCP=PCP.(10) \tilde{C} := \text{Cov}[\tilde{x}] = \text{Cov}[Px] = P\text{Cov}[x]P^\top = PCP^\top = PCP. \tag{10}

In words, this says that the covariance matrix of the reversed vector is given by PCPPCP, where CC is the covariance of the original vector. If you prefer to avoid probabilistic language, then PCPPCP is simply the result of reversing the order of the columns and rows of CC. Reversing CC induces the same operation on its inverse, since (C~)1:=(PCP)1=P1C1P=PC1P,(11) (\tilde{C})^{-1} := (PCP)^{-1} = P^{-1}C^{-1}P = PC^{-1}P, \tag{11} 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 C~\tilde{C}. Notation becomes a bit confusing here, so we separate the two results for clarity.

Cholesky under reverse ordering.
Let C=UUC = UU^\top be the rCholesky decomposition of CC. Then the Cholesky decomposition of C~=PCP\tilde{C} = PCP is given by C~=(PUP)(PUP).(12) \tilde{C} = (PUP)(PUP)^\top. \tag{12} This can be equivalently be written as chol(C~)=chol(PCP)=PUP=Prchol(C)P.(13) \text{chol}(\tilde{C}) = \text{chol}(PCP) = PUP = P\text{rchol}(C)P. \tag{13} In words, this says that the Cholesky factor of C~\tilde{C} is given by reversing the rCholesky factor of CC.

Proof. Using the fact that P2=IP^2 = I we have C~=PCP=P(UU)P=PUP2UP=(PUP)(PUP). \tilde{C} = PCP = P(UU^\top)P = PUP^2 U^\top P = (PUP)(PUP)^\top. The result is now immediate upon noticing that PUPPUP is lower triangular and has positive diagonal entries. \qquad \blacksquare

rCholesky under reverse ordering.
Let C=LLC = LL^\top be the Cholesky decomposition of CC. Then the rCholesky decomposition of C~=PCP\tilde{C} = PCP is given by C~=(PLP)(PLP).(14) \tilde{C} = (PLP)(PLP)^\top. \tag{14} This can be equivalently be written as rchol(C~)=rchol(PCP)=PLP=Pchol(C)P.(15) \text{rchol}(\tilde{C}) = \text{rchol}(PCP) = PLP = P\text{chol}(C)P. \tag{15} In words, this says that the rCholesky factor of C~\tilde{C} is given by reversing the Cholesky factor of CC.

Proof. Using the fact that P2=IP^2 = I we have C~=PCP=P(LL)P=PLP2LP=(PLP)(PLP). \tilde{C} = PCP = P(LL^\top)P = PLP^2 L^\top P = (PLP)(PLP)^\top. The result is now immediate upon noticing that PLPPLP is upper triangular and has positive diagonal entries. \qquad \blacksquare

These results tell us that we can use a Cholesky factorization of CC to immediately compute the rCholesky factorization of the reversed matrix C~\tilde{C}. This statement is the same with the roles of Cholesky and rCholesky swapped. In (13) and (15) we can left and right multiply by PP 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 C1C^{-1} in place of CC.

Other Resources

  1. Jurek, M., & Katzfuss, M. (2021). Hierarchical sparse Cholesky decomposition with applications to high-dimensional spatio-temporal filtering. https://arxiv.org/abs/2006.16901