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 .

88.1. Existence and uniqueness

Cholesky exists iff is:

  1. Symmetric:
  2. Positive definite: for all

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, :

Cost: about — half of LU decomposition (we exploit symmetry).

Example

Verify: . ✓

88.3. Why use Cholesky

  1. Solving : split into (forward substitution) then (backward substitution). Twice as fast as LU for symmetric positive-definite .

  2. Testing positive-definiteness: an attempt to compute Cholesky fails (negative argument to , or division by zero) iff is not positive definite. Cheap test.

  3. Sampling from multivariate Gaussian: if is the covariance matrix and (standard normal), then is .

  4. Linear least squares (alternative to QR): the normal equations have a symmetric positive-definite system matrix ; Cholesky solves it.

  5. Determinant: — much cheaper than expanding directly.

88.4. Relation to LU and SVD

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

88.5. See also