Cholesky Decomposition

The Cholesky decomposition decomposes a symmetric positive-definite (SPD) matrix into a product of a lower triangular matrix and its transpose:

$$\begin{array}{rl}A& =L^{T}L\\ \left[\begin{array}{cccc}{a}_{11}& a_{12}& a_{13}& a_{14}\\ a_{21}& a_{22}& a_{23}& a_{24}\\ a_{31}& a_{32}& a_{33}& a_{34}\\ a_{41}& a_{42}& a_{43}& a_{44}\end{array}\right]& =\left[\begin{array}{cccc}{l}_{11}& 0& 0& 0\\ l_{21}& l_{22}& 0& 0\\ l_{31}& l_{32}& l_{33}& 0\\ l_{41}& l_{42}& l_{43}& l_{44}\end{array}\right]\left[\begin{array}{cccc}{l}_{11}& l_{12}& l_{13}& l_{14}\\ 0& l_{22}& l_{23}& l_{24}\\ 0& 0& l_{33}& l_{34}\\ 0& 0& 0& l_{44}\end{array}\right]\end{array}$$

If matrix $A$ is positive semi-definite, then the diagonal entries of L are allowed to be zero.

Cholesky Decomposition Algorithm

Diagonal elements of $L$:

$$l_{vv}=\sqrt{a_{vv}-\sum _{u<v}{l}_{vu}^2}$$

Off-diagonal elements of $L$:

$$l_{tv}=\frac{1}{l_{vv}}\left(a_{tv}-\sum _{u<v}{l}_{tu}{l}_{vu}\right)$$

Applications

The Cholesky decomposition enhances numerical stability when dealing with symmetric positive-definite matrices in solving linear systems or inverting matrices.

• SPD matrices: No pivoting required to maintain numerical stability, because the positive-definite condition (remember that Cholesky is specifically for SPD matrices!) ensures that all pivot elements are positive and significantly reduces the risk of encountering very small (near-zero) pivot values that can lead to numerical instability.
• Straightforward forward and backward substitution without the numerical difficulties associated with general matrices. This ensures more stable computations, especially in iterative algorithms where errors can accumulate.
• Simplifies these operations by reducing the problem to two simpler systems of equations through forward and backward substitution.

Kalman Filter

For example, the Cholesky can be useful for Kalman Filter, where you have to solve for the Kalman gain by finding:

$${\mathbf{K}}_k^{\prime }={\mathbf{P}}_k{\mathbf{H}}_k^T({\mathbf{H}}_k{\mathbf{P}}_k{\mathbf{H}}_k^T+{\mathbf{R}}_k{)}^{-1}$$

Specifically, calculating $({\mathbf{H}}_k{\mathbf{P}}_k{\mathbf{H}}_k^T+{\mathbf{R}}_k{)}^{-1}$ is equivalent to solving a linear system of equations ($Ax=b$ is the same as $x=A^{-1}b$). This matrix is SPD by construction:

Symmetry:

• ${\mathbf{P}}_k$ (predicted state covariance) is symmetric by definition
• When multiplied by ${\mathbf{H}}_k$ on the left and ${\mathbf{H}}_k^T$ on the right, it remains symmetric
• ${\mathbf{R}}_k$ (measurement noise covariance matrix) is also symmetric by definition maintains the symmetry

Positive-Definiteness

• For a matrix $A$ to be positive-definite, it must satisfy the condition that for any non-zero vector $x$, $x^{T}Ax>0$. In our case, $A$ is ${\mathbf{H}}_k{\mathbf{P}}_k{\mathbf{H}}_k^T+{\mathbf{R}}_k$.
• $P_k$ is positive definite to reflect the uncertainty in the system’s state estimation
• $R_k$ is positive definite to reflect the uncertainty in measurements
• Combination should still be positive definite

The primary scenario where ${\mathbf{H}}_k{\mathbf{P}}_k{\mathbf{H}}_k^T+{\mathbf{R}}_k$ might not be positive-definite (and thus not suitable for Cholesky decomposition) involves numerical inaccuracies or improper initialization, like floating-point arithmetic errors, or incorrect initialization.

Cholesky is also useful in calculating Unscented Kalman Filters.