mathematics//linear algebra//matrix factorization//Cholesky decomposition

The Cholesky decomposition is the factorization of a symmetric positive definite matrix into a lower triangular matrix times its own transpose, and it is the matrix square root that estimation code uses everywhere a covariance must be solved with, sampled from or spread into points. For a covariance \(P\),

The Cholesky decomposition is the factorization of a symmetric positive definite matrix into a lower triangular matrix times its own transpose, and it is the matrix square root that estimation code uses everywhere a covariance must be solved with, sampled from or spread into points. For a covariance PPP,

P=LLT.P=LL^{\mathsf T}.P=LLT.

It exists exactly when the matrix is symmetric positive definite, costs about 13n3\tfrac13n^331​n3 operations (half an LU decomposition) and needs no pivoting, because the structure of the matrix already keeps it stable. Just as a standard deviation is the square root of a variance, LLL is a square root of a covariance, and that reading explains its three main uses.

The first is drawing correlated noise. If zzz holds independent standard normal numbers, x=μ+Lzx=\mu+Lzx=μ+Lz has mean μ\muμ and covariance PPP, which is how a Monte Carlo simulation shakes a model with sensor noise whose axes are correlated. The second is the sigma points of an unscented Kalman filter: the 2n+12n+12n+1 points are the mean plus and minus the columns of a scaled LLL, and a 24-state filter pays one Cholesky per step for them. The third is the square-root filter, which propagates LLL instead of PPP. Since the condition number of LLL is the square root of that of PPP, the filter keeps twice the significant digits, and P=LLTP=LL^{\mathsf T}P=LLT cannot lose its positive definiteness by construction.

A failed Cholesky is a diagnosis.

The factorization breaks down exactly when the matrix is not positive definite, so a UKF that stops with a Cholesky error is reporting that its covariance has been corrupted (rounding, a bad QQQ, an update that made a variance negative), and the fault is upstream of the factorization.

Testing positive definiteness by attempting a Cholesky is cheaper and more reliable than computing eigenvalues, and it is how libraries check a covariance before using it.

In least squares the Cholesky of the normal matrix ATAA^{\mathsf T}AATA is the fastest solve and the least accurate, because forming that matrix has already squared the conditioning; it is acceptable when the problem is well scaled, and the QR decomposition is the safe default otherwise.