Cholesky Decomposition

Visualize the factorization of a symmetric positive-definite matrix into a lower triangular matrix and its transpose.

Cholesky Decomposition

Concept Overview

The Cholesky Decomposition is a specialized matrix factorization technique applicable exclusively to symmetric positive-definite matrices. It decomposes a given matrix into the product of a lower triangular matrix and its transpose. Because it specifically targets symmetric positive-definite matrices, it is roughly twice as efficient as a general LU decomposition.

Mathematical Definition

For a symmetric, positive-definite matrix A, its Cholesky decomposition is defined as:

A = L × L^T

Where:

A is an n × n symmetric matrix (meaning A = A^T) and positive-definite (x^TAx > 0 for all non-zero vectors x).
L is a lower triangular matrix with strictly positive real numbers on its main diagonal.
L^T is the transpose of L, rendering it an upper triangular matrix.

Key Concepts

Positive-Definiteness: The matrix A must be positive-definite. If A is not positive-definite, the algorithm will attempt to take the square root of a negative number or divide by zero when computing the diagonal elements of L.
Efficiency & Numerical Stability: The Cholesky algorithm requires approximately n³/3 floating-point operations, which is half the number required for LU decomposition. It is also exceptionally numerically stable; unlike Gaussian elimination, it rarely necessitates pivoting.
Computing the Factorization: The elements of L are determined iteratively. Each diagonal element L_ii is calculated using a square root, while the off-diagonal elements L_ij rely on previously computed entries in L.

Historical Context

The decomposition was developed by André-Louis Cholesky, a French military officer and mathematician. Around 1910, he invented the procedure to efficiently solve normal equations related to topographic surveying and mapping. Although Cholesky perished in World War I before publishing his work, his colleague Commandant Benoît published the method in 1924, ensuring its widespread adoption.

Real-world Applications

Solving Systems of Linear Equations: Primarily used to solve normal equations in linear least squares approximation, formulated as (A^TA)x = A^Tb, where A^TA is symmetric positive-definite.
Monte Carlo Simulation: Generating correlated random variables. By generating independent standard normal variables Z, the transformed variables X = LZ will possess a covariance matrix equal to LL^T = A.
Kalman Filters: Used heavily in control theory and signal processing to update covariance matrices while guaranteeing they remain positive-definite.
Optimization: Calculating search directions in numerical optimization algorithms like Newton's method or interior-point methods.

Related Concepts

LU Decomposition: The more general form of factorization for any non-singular square matrix.
Positive Definite Matrices: The strict property requirement for A.
Least Squares Approximation: A classic problem directly solved using Cholesky on the normal equations.

Cholesky Decomposition