Cholesky Decomposition

88. Cholesky Decomposition

Every symmetric positive-definite matrix $𝐴$ has a unique factorization:

𝐴 = 𝐿 𝐿^{𝑇}

where $𝐿$ is lower triangular with positive diagonal entries.

The Cholesky decomposition is the symmetric square root of a positive-definite matrix — like writing a positive number $𝑎$ as $\sqrt{𝑎} \cdot \sqrt{𝑎}$ .

88.1. Existence and uniqueness

Cholesky exists iff $𝐴$ is:

Symmetric: $𝐴^{𝑇} = 𝐴$
Positive definite: ${\vec{𝑥}}^{𝑇} 𝐴 \vec{𝑥} > 0$ for all $\vec{𝑥} \neq 𝟎$

If either fails, Cholesky fails. For positive semi-definite $𝐴$ a related decomposition exists but is non-unique.

For symmetric indefinite $𝐴$ , use the $𝐿 𝐷 𝐿^{𝑇}$ variant ( $𝐷$ diagonal with arbitrary signs).

88.2. Algorithm (forward construction)

Compute $𝐿$ column by column, $𝑗 = 1, \dots, 𝑛$ :

𝐿_{𝑗 𝑗} = \sqrt{𝐴_{𝑗 𝑗} - \sum_{𝑘 = 1}^{𝑗 - 1} 𝐿_{𝑗 𝑘}^{2}}

𝐿_{𝑖 𝑗} = \frac{1}{𝐿_{𝑗 𝑗}} (𝐴_{𝑖 𝑗} - \sum_{𝑘 = 1}^{𝑗 - 1} 𝐿_{𝑖 𝑘} 𝐿_{𝑗 𝑘}), for 𝑖 > 𝑗

Cost: about $\frac{𝑛^{3}}{3}$ — half of LU decomposition (we exploit symmetry).

Example

𝐴 = [\begin{matrix} 4 & 12 & - 16 \\ 12 & 37 & - 43 \\ - 16 & - 43 & 98 \end{matrix}]

𝐿 = [\begin{matrix} 2 & 0 & 0 \\ 6 & 1 & 0 \\ - 8 & 5 & 3 \end{matrix}]

Verify: $𝐿 𝐿^{𝑇} = 𝐴$ . ✓

88.3. Why use Cholesky

Solving $𝐴 \vec{𝑥} = \vec{𝑏}$ : split into $𝐿 \vec{𝑦} = \vec{𝑏}$ (forward substitution) then $𝐿^{𝑇} \vec{𝑥} = \vec{𝑦}$ (backward substitution). Twice as fast as LU for symmetric positive-definite $𝐴$ .
Testing positive-definiteness: an attempt to compute Cholesky fails (negative argument to sqrt, or division by zero) iff $𝐴$ is not positive definite. Cheap test.
Sampling from multivariate Gaussian: if $Σ = 𝐿 𝐿^{𝑇}$ is the covariance matrix and $\vec{𝑧} \sim 𝒩︀ (𝟎, 𝐼)$ (standard normal), then $\vec{𝑥} = 𝐿 \vec{𝑧}$ is $𝒩︀ (𝟎, Σ)$ .
Linear least squares (alternative to QR): the normal equations $𝐴^{𝑇} 𝐴 \vec{𝑥} = 𝐴^{𝑇} \vec{𝑏}$ have a symmetric positive-definite system matrix $𝐴^{𝑇} 𝐴$ ; Cholesky solves it.
Determinant: $det (𝐴) = \prod 𝐿_{𝑖 𝑖}^{2}$ — much cheaper than expanding directly.

88.4. Relation to LU and SVD

LU: $𝐴 = 𝐿 𝑈$ — general matrices, $𝐿$ lower-triangular, $𝑈$ upper-triangular
Cholesky: $𝐴 = 𝐿 𝐿^{𝑇}$ — symmetric positive-definite case, $𝑈 = 𝐿^{𝑇}$
SVD: $𝐴 = 𝑈 Σ 𝑉^{𝑇}$ — completely general, gives singular values, more expensive

For symmetric positive-definite $𝐴$ , Cholesky is the fastest and most stable choice.

88.5. See also

Symmetric Matrix
Quadratic Form — positive-definite condition
Triangular Matrix
LU / QR / SVD