Cholesky decomposition

Cholesky decomposition factors A = LLᵀ for symmetric positive definite matrices

The Cholesky decomposition is a numerical method used to decompose symmetric positive definite matrices into a product of a lower triangular matrix and its conjugate transpose. This decomposition is particularly useful for solving systems of linear equations efficiently.

The Cholesky decomposition is approximately twice as efficient as the LU decomposition when solving systems of linear equations. This efficiency is due to the reduced number of operations required compared to the LU decomposition.

The Cholesky decomposition is applicable only to Hermitian, positive-definite matrices. It was discovered by André-Louis Cholesky and published posthumously in 1924.

Example

Given a symmetric positive definite matrix A, the Cholesky decomposition yields A = LL^T, where L is a lower triangular matrix. For instance, if A = [[4, 12], [12, 37]], then L = [[2, 0], [6, 1]] and L^T = [[2, 6], [0, 1]], confirming A = LL^T.

Remember this

Understanding the Cholesky decomposition is crucial for efficient numerical solutions, especially in Monte Carlo simulations and solving systems of linear equations.

Text adapted from Wikipedia, licensed under CC BY-SA 4.0.

Related concepts

LU decomposition

LU decomposition factors a matrix as the product of a lower triangular matrix and an upper triangular matrix

QR decomposition

QR decomposition factors A = QR

Eigenvalues and eigenvectors

Eigenvectors are unchanged in direction by a linear transformation

Kullback–Leibler divergence

KL divergence is not symmetric: D_KL(P||Q) ≠ D_KL(Q||P)

Invertible matrix

Rank-nullity theorem: rank(A) + nullity(A) = n

the determinant tells you about volume scaling under a linear transformation

The determinant of a matrix representing a linear transformation indicates the factor by which volumes are scaled

Swipe through 100 ML concepts daily

Open Pocket Polymath