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.

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

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, where Q is orthogonal, R is upper triangular

Eigenvalues and eigenvectors

Eigenvectors are unchanged in direction by a linear transformation

orthogonal matrices preserve distances: O^T O = I means no stretching or squashing

Orthogonal matrices preserve distances because O^T O = I ensures no stretching or squashing occurs

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

One email a day: 5 concepts + the 5 stories that matter →

Swipe through 100 ML concepts daily

Open TickerNews