2.12 Cholesky Decomposition of a matrix

 Cholesky Decomposition

We have square root like operation that gives us a decomposition of the numbers into identical components eg 9= 3.3. For matrices we need to be careful that we compute a square root like operation on positive quantities.For symmetric positive definite matrices. we can choose from a number of square root equivalent operation.The Cholesky decomposition/Cholesky factorization provides a square root equivalent operation on symmetric positive definite matrices that is useful in practice.

The decomposition is defined as follows:

$A = L \times L^T$
Where $A$ is the matrix being decomposed, $L$ is the lower triangular matrix and $L^T$ is the transpose of  $L$. The decompose can also be written as the product of the upper triangular matrix, for example:
$A = U^T \times U$

Where $U$ is the upper triangular matrix. The Cholesky decomposition is used for solving linear least squares for linear regression, as well as simulation and optimization methods. When decomposing symmetric matrices, the Cholesky decomposition is nearly twice as efficient as the LU decomposition and should be preferred in these cases.

Eg:consider a 3x3 matrix

Multiplying the right hand side yields

Comparing the left hand side and right hand side

$l_{11}=\sqrt{a_{11}}$          $l_{21}=a_{21}/l_{11}$      $l_{31}=a_{31}/l_{11}$

$l_{22}=\sqrt{a_{22}-l_{21}^2}$      $l_{32}=(a_{32}-l_{31}l_{21})/l_{22}$

$l_{33}=\sqrt{a_{33}-l_{31}^2-l_{32}^2}$

While symmetric, positive definite matrices are rather special, they occur quite frequently in some applications, so their special factorization, called Cholesky decomposition,is good to know about. When you can use it, Cholesky decomposition is about a factor of two faster than alternative methods for solving linear equations.The Cholesky factorization of covariance matrix allows us to generate samples from Gaussian distribution, it also allow us to perform a linear transformation of random variables.The Cholesky decomposition also allows us to compute the determinant efficiently.

$det(A)=det(L)del(L^T)$  

$det(A)= \prod_{i} l_{ii}^2$

Example:

Let $A=\begin{bmatrix}
4 &1\\
1 & 4
\end{bmatrix}$

$
\begin{bmatrix}
a_{11} & a_{12}\\
a_{21} & a_{22}
\end{bmatrix}=\begin{bmatrix}
l_{11} & 0 \\
l_{21}& l_{22}
\end{bmatrix}
\begin{bmatrix}
l_{11} & l_{21}\\
0& l_{22}
\end{bmatrix}=\begin{bmatrix}
l_{11}^2 & l_{11}l_{21}\\
l_{21}l_{11}&l_{21}^2+l_{22}^2
\end{bmatrix}$

So

$l_{11}=\sqrt(a_{11})=\sqrt(4)=2$

$l_{21}=a_{21}/l_{11}=1/2$

$l_{21}^2+l_{22}^2=a_{22}$ so $l_{22}=\sqrt{a_{22}-l_{21}^2}=\sqrt(4-{\frac{1}{2}}^2)=\sqrt{15}/2$

$\begin{bmatrix}
4 & 1\\
1 & 4
\end{bmatrix}=\begin{bmatrix}
2 & 0 \\
1/2& \sqrt(15)/2
\end{bmatrix}
\begin{bmatrix}
2 & 1/2\\
0& \sqrt(15)/2
\end{bmatrix}$

The Cholesky decomposition can be implemented in NumPy by calling the cholesky() function. The function only returns L as we can easily access the L transpose as needed.
# Cholesky decomposition

from numpy import array

from numpy.linalg import cholesky

# define symmetrical matrix

A = array([

[4, 1],

[1, 4]])

print("A")

print(A)

# factorize

L= cholesky(A)

print("Decompostion L and L^T")

print(L)

print(L.T)

# reconstruct

print("Reconstructing A=L.L^T")

B= L.dot(L.T)

print(B)

o/p
A 

[[4 1] 

 [1 4]] 

Decompostion L and L^T 

[[2. 0. ] 

 [0.5 1.93649167]] 

[[2. 0.5 ] 

 [0. 1.93649167]] 

Reconstructing A=L.L^T

 [[4. 1.]

 [1. 4.]]

from numpy import array
from numpy.linalg import cholesky
# define symmetrical matrix
A = array([
[2, 1, 1],
[1, 2, 1],
[1, 1, 2]])
print(A)
# factorize
L= cholesky(A)
print(L)
# reconstruct
B = L.dot(L.T)
print(B)
o/p:
[[2 1 1]
[1 2 1]
[1 1 2]]

[[ 1.41421356 0. 0. ]
[ 0.70710678 1.22474487 0. ]
[ 0.70710678 0.40824829 1.15470054]]

[[ 2. 1. 1.]
[ 1. 2. 1.]
[ 1. 1. 2.]]