Cholesky decomposition

1 Cholesky Decomposition

A symmetric and positive definite matrix can be efficiently decomposed into a lower and upper triangular matrix. For a matrix of any type, this is achieved by the LU decomposition which factorizes $A=LU$. If $A$ satisfies the above criteria, one can decompose more efficiently into $A=L{L}^T$ where $L$ is a lower triangular matrix with positive diagonal elements. $L$ is called the Cholesky triangle.

To solve $Ax=b$, one solves first $Ly=b$ for $y$, and then $L^{T}x=y$ for $x$.

A variant of the Cholesky decomposition is the form $A=R^{T}R$ , where $R$ is upper triangular.

Cholesky decomposition is often used to solve the normal equations in linear least squares problems; they give $A^{T}Ax=A^{T}b$ , in which $A^{T}A$ is symmetric and positive definite.

To derive $A=L{L}^T$, we simply equate coefficients on both sides of the equation:

Solving for the unknowns (the nonzero $l_{ji}$s), for $i=1,\mathrm{\cdots },n$ and $j=i-1,\mathrm{\dots },n$, we get:

$l_{ii}$$=$$\sqrt{\left(a_{ii}-{\displaystyle \sum _{k=1}^{i-1}}{l}_{ik}^2\right)}$

$l_{ji}$$=$$\left(a_{ji}-{\displaystyle \sum _{k=1}^{i-1}}{l}_{jk}{l}_{ik}\right)/l_{ii}$

Because $A$ is symmetric and positive definite, the expression under the square root is always positive, and all $l_{ij}$ are real.