Cholesky Decomposition

Cholesky Decomposition

Procedures

1. Choose an n X n matrix

2. The chosen matrix should be symmetric

Let’s assume, A = $\begin{bmatrix} a1 & a2 & a3 \\ a2 & a4 & a5 \\ a3 & a5 & a6 \end{bmatrix}$

a matrix A is symmetric if

1. A is a square matrix

2. and A = A^T

Otherwise-Pop up error – entered matrix should be symmetric

3. The chosen matrix should be positive definite as well.

a matrix A is positive definite if determinants of all upper-left sub-matrices are positive or,

$\left| \begin{matrix} a1 \end{matrix} \right|$ > 0

$\left| \begin{matrix} a1 & a2 \\ a2 & a4 \end{matrix} \right|$ > 0

$\left| \begin{matrix} a1 & a2 & a3 \\ a2 & a4 & a5 \\ a3 & a5 & a6 \end{matrix} \right|\ $> 0

Otherwise-Pop up error – entered matrix should be positive definite

4. Every symmetric positive definite matrix A can be decomposed into a product of a unique lower triangular matrix L and its transpose.

A = L*L^T

5. There is a clear-cut formula to find the elements of matrix L

Where, for example, l_ki denotes the matrix L’s entry/element in k^th row and i^th column.

l_kk denotes the main diagonal elements of matrix L

Example:

Given matrix, A = $\begin{bmatrix} 4 & 2 & 14 \\ 2 & 17 & - 5 \\ 14 & - 5 & 83 \end{bmatrix}$

The matrix A is symmetric as A = A^T

Now, we’ll check given matrix A is positive definite or not.

$\left| \begin{matrix} 4 \end{matrix} \right|$ > 0

$\left| \begin{matrix} 4 & 2 \\ 2 & 17 \end{matrix} \right|$ = 68 – 4 = 64 > 0

$\left| \begin{matrix} 4 & 2 & 14 \\ 2 & 17 & - 5 \\ 14 & - 5 & 83 \end{matrix} \right|$ = 1600 > 0

So, the matrix is positive definite as well.

Any symmetric positive definite matrix A can be decomposed into a product of a unique lower triangular matrix L and its transpose or,

A = L*L^T

Formula

l₁₁ = √4 = 2

l₂₁ = a₂₁ / l₁₁ = 2/2 =1

l₂₂ = √( a₂₂ – (l₂₁)²) = √(17 – 1) = 4

l₃₁ = a₃₁ / l₁₁ = 14/2 = 7

l₃₂ = (a₃₂ – l₃₁ * l₂₁) / l₂₂ = (-5 – (7)*(1)) / 4 = -3

l₃₃ = √( a₃₃ – (l₃₁)² - (l₃₂)²) = √(83 – (7)² - (-3)²) = 5

Now, from the solutions of the aforementioned equations we obtain the matrix L.

L = $\begin{bmatrix} l11 & 0 & 0 \\ l21 & l22 & 0 \\ l31 & l32 & l33 \end{bmatrix}$ = $\begin{bmatrix} 2 & 0 & 0 \\ 1 & 4 & 0 \\ 7 & - 3 & 5 \end{bmatrix}$

And L*L^T = $\begin{bmatrix} 2 & 0 & 0 \\ 1 & 4 & 0 \\ 7 & - 3 & 5 \end{bmatrix}*\ \begin{bmatrix} 2 & 1 & 7 \\ 0 & 4 & - 3 \\ 0 & 0 & 5 \end{bmatrix}$ = $\begin{bmatrix} 4 & 2 & 14 \\ 2 & 17 & - 5 \\ 14 & - 5 & 83 \end{bmatrix}$ = A

Some more discussion about Cholesky decomposition (Extra)

a square matrix A can be factorized as

A = L*U

Where L is a lower triangular matrix and U is an upper triangular matrix. We’ve already discussed in detail about ‘LU decomposition’

For a symmetric and positive definite matrix

U = L^T

So, in this case, A = L*U = L * L^T

For a system of linear equations

Ax = b

Or, L* L^T * x = b

Let, L^T * x = y

Then, L * y = b

Now, one need to find the value of L by calculating

L * L^T = A

Or, $\begin{bmatrix} l11 & 0 & 0 \\ l21 & l22 & 0 \\ l31 & l32 & l33 \end{bmatrix}*\begin{bmatrix} l11 & l21 & l31 \\ 0 & l22 & l23 \\ 0 & 0 & l33 \end{bmatrix}$ = $\begin{bmatrix} 4 & 2 & 14 \\ 2 & 17 & - 5 \\ 14 & - 5 & 83 \end{bmatrix}$

See above to find the solution of matrix L. This is already discussed as a formula.

Once, one has solved y from L*y = b

Then solve x from ‘L^T * x = y’

In the above, we’ve discussed the whole procedure of finding matrix L from a given matrix.