Cholesky decomposition

Given a symmetric positive definite matrix , the Cholesky decomposition constructs a lower triangular matrix L which has the following property: . A symmetric matrix is positive definite if, for any vector , the product is positive.

The matrix is sometimes called the « square root » of . The Cholesky decomposition is often used to calculate the inverse matrix $A^{-1}$ and the determinant of (equal to the square of the product of the diagonal elements of ).

Example

The symmetric matrix $A=\begin{pmatrix} 1 & 1 & 1 & 1 \cr 1 & 5 & 5 & 5 \cr 1 & 5 & 14 & 14 \cr 1 & 5 & 14 & 15 \end{pmatrix}$

is equal to the product of the triangular matrix and of its transposed :

$\begin{pmatrix} 1 & 1 & 1 & 1 \cr 1 & 5 & 5 & 5 \cr 1 & 5 & 14 & 14 \cr 1 & 5 & 14 & 15 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 \cr 1 & 2 & 0 & 0 \cr 1 & 2 & 3 & 0 \cr 1 & 2 & 3 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 & 1 \cr 0 & 2 & 2 & 2 \cr 0 & 0 & 3 & 3 \cr 0 & 0 & 0 & 1 \end{pmatrix}$

with

$L= \begin{pmatrix} 1 & 0 & 0 & 0 \cr 1 & 2 & 0 & 0 \cr 1 & 2 & 3 & 0 \cr 1 & 2 & 3 & 1 \end{pmatrix}$

Theorem

Cholesky Factorization:

If is a symmetric positive definite matrix, there is at least a lower triangular real matrix such as :

We can also impose that the diagonal elements of the matrix are all positive, and corresponding factorization is then unique.

Algorithm

The Cholesky matrix is given by:

$L=\begin{pmatrix}{ l_{11}\cr l_{21} & l_{22}\cr \vdots & \vdots & \ddots\cr l_{n1} & l_{n2} & \cdots & l_{nn} \end{pmatrix}$

Equality gives : $a_{ij}=\left(LL^{T}\right)_{ij}={\sum_{k=1}^{n}l_{ik}l_{jk}}={\sum_{k=1}^{\min\left\{ i,j\right\} }l_{ik}l_{jk}},\;1\leq i,j\leq n$

since $l_{ij}=0$ if $1 \leq i < j \leq n.$

The matrix being symmetric, it is enough that the relations above are checked for $i\leq j$ , i.e. the elements $l_{ij}$ of the matrix must satisfy: $a_{ij}={\sum_{k=1}^{i}l_{ik}l_{jk}},\;1\leq i,j\leq n$

For j=1, we determine the first column of :
(i=1) $a_{11}=l_{11}l_{11}$ so $l_{11}=\sqrt{a_{11}}$
(i=2) $a_{12}=l_{11}l_{21}$ so $l_{21}=\frac{a_{12}}{l_{11}}$
...
(i=n) $a_{1n}=l_{11}l_{n1}$ so $l_{n1}=\frac{a_{1n}}{l_{11}}$

After having calculated the (j-1) first columns, we determine the j-th column of :
(i=j) $a_{ii}=l_{i1}l_{i1}+\ldots+l_{ii}l_{ii}$ so $l_{ii}=\sqrt{a_{ii}-{\sum_{k=1}^{i-1}l_{ik}^{2}}}$
(i=j+1) $\displaystyle a_{i,i+1}=l_{i1}l_{i+1,1}+\ldots+l_{ii}l_{i+1,i}$ so $l_{i+1,i}=\displaystyle\frac{a_{i,i+1}-{\displaystyle\sum_{k=1}^{i-1}l_{ik}l_{i+1,k}}}{l_{ii}}$
...
(i=n) $\displaystyle a_{i,n}=l_{i1}l_{n1}+\ldots+l_{ii}l_{ni}$ so $l_{ni}=\displaystyle\frac{a_{in}-{\displaystyle\sum_{k=1}^{i-1}l_{ik}l_{nk}}}{l_{ii}}$

Solution of linear system

For the resolution of linear system : , the system becomes

$LL^Tx = b \Leftrightarrow \left\{\begin{array}{cc} Ly = b& (1),\\ L^Tx = y &(2). \end{array}\right.$

We solve the system (1) to find the vector , then the system (2) to find the vector . The resolution is facilitated by the triangular shape of the matrices.

Calculating Matrix Determinant

The Cholesky decomposition also makes it possible to calculate the determinant of , which is equal to the square of the product of the diagonal elements of the matrix , since

$det(A) = det(L)\times det(L^T)=det(L)^2$

Keywords:

Example

Theorem

Algorithm

Solution of linear system

Calculating Matrix Determinant

1 Message

Sections

In the same section

Keywords