# 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=LL^{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=LL^{T}$, we simply equate coefficients on both sides of the equation:

 $\begin{bmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ a_{31}&a_{32}&\cdots&a_{3n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\cdots&a_{nn}\end{bmatrix}=\begin{bmatrix}l_{11}&0&\cdots&0\\ l_{21}&l_{22}&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ l_{n1}&l_{n2}&\cdots&l_{nn}\end{bmatrix}\begin{bmatrix}l_{11}&l_{21}&\cdots&l_% {n1}\\ 0&l_{22}&\cdots&l_{n2}\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&l_{nn}\end{bmatrix}$

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

 $\displaystyle l_{ii}$ $\displaystyle=$ $\displaystyle\sqrt{\left(a_{ii}-\sum_{k=1}^{i-1}l_{ik}^{2}\right)}$ $\displaystyle l_{ji}$ $\displaystyle=$ $\displaystyle\left(a_{ji}-\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.

## References

• 1 Originally from The Data Analysis Briefbook (http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html)
 Title Cholesky decomposition Canonical name CholeskyDecomposition Date of creation 2013-03-22 12:07:38 Last modified on 2013-03-22 12:07:38 Owner gufotta (12050) Last modified by gufotta (12050) Numerical id 16 Author gufotta (12050) Entry type Definition Classification msc 62J05 Classification msc 65-00 Classification msc 15-00 Synonym Cholesky factorization Synonym matrix square root Related topic SquareRootOfPositiveDefiniteMatrix Defines Cholesky triangle