Skip to content

UKF Numerical Stability: Cholesky vs LDL^T Decomposition

The Unscented Kalman Filter (UKF) generates sigma points from the state covariance matrix PP at every time step. This requires a matrix factorization that serves as a “square root” of PP. The choice of factorization has a direct impact on filter stability, particularly when PP becomes ill-conditioned after informative observations.

This document walks through MTL5’s UKF comparison examples, explains why the LDLTLDL^T (square-root-free Cholesky) decomposition provides superior numerical robustness, and offers guidance on when to use each method.

The Problem: Square Roots and Ill-Conditioned Covariances

Section titled “The Problem: Square Roots and Ill-Conditioned Covariances”

The UKF approximates a nonlinear probability distribution by propagating a carefully chosen set of sigma points through the system model. For a state with covariance PP, the sigma points are:

σk=x^±n+λ⋅S:,k\sigma_k = \hat{x} \pm \sqrt{n + \lambda} \cdot S_{:,k}

where SS is a matrix satisfying SST=PSS^T = P. The standard approach computes SS via Cholesky factorization: P=LLTP = LL^T.

How informative observations create ill-conditioning

Section titled “How informative observations create ill-conditioning”

When a measurement is very precise (small measurement noise RR), the Kalman update collapses one or more directions of the state covariance toward machine epsilon while others remain O(1)O(1). This creates extreme eigenvalue spread:

  • Well-observed direction: eigenvalue ∼εmach\sim \varepsilon_{\text{mach}}
  • Poorly-observed direction: eigenvalue ∼O(1)\sim O(1) or larger

The condition number κ(P)=λmax⁡/λmin⁡\kappa(P) = \lambda_{\max} / \lambda_{\min} can reach 10610^6 in double precision and 10310^3 in single precision after just a few updates.

Standard Cholesky factorization computes the diagonal of LL via:

Ljj=Ajj−∑k<jLjk2L_{jj} = \sqrt{A_{jj} - \sum_{k<j} L_{jk}^2}

When AjjA_{jj} is near machine epsilon after the subtraction, the ⋅\sqrt{\cdot} operation halves the number of significant digits:

  • In float64 (53-bit significand): 10−15=3.16×10−8\sqrt{10^{-15}} = 3.16 \times 10^{-8}, losing ~7.5 digits
  • In float32 (24-bit significand): 10−7=3.16×10−4\sqrt{10^{-7}} = 3.16 \times 10^{-4}, losing ~3.5 digits
  • In float16 (11-bit significand): essentially all precision is lost

This degraded diagonal entry propagates into every subsequent column of LL, contaminating the entire factorization.

The LDLTLDL^T decomposition factors a symmetric matrix as:

A=LDLTA = L D L^T

where LL is unit lower triangular (ones on the diagonal) and DD is diagonal. Comparing with Cholesky:

PropertyCholesky (LLTLL^T)LDLTLDL^T
Diagonal of LLpivot values\sqrt{\text{pivot values}}1 (unit diagonal)
Square rootsOne per columnNone
StoresLL (lower triangular)LL (unit lower) + DD (diagonal)
CostO(n3/3)O(n^3/3)O(n3/3)O(n^3/3)
SPD requiredYesNo (works for indefinite)

Why avoiding square roots preserves precision

Section titled “Why avoiding square roots preserves precision”

The LDLTLDL^T algorithm computes DjD_j directly:

Dj=Ajj−∑k<jLjk2⋅DkD_j = A_{jj} - \sum_{k<j} L_{jk}^2 \cdot D_k

No square root is taken. DjD_j retains the full precision of the subtraction result, however small. The unit lower triangular entries are:

Lij=Aij−∑k<jLik⋅Dk⋅LjkDjL_{ij} = \frac{A_{ij} - \sum_{k<j} L_{ik} \cdot D_k \cdot L_{jk}}{D_j}

This is a simple division, not a precision-destroying ⋅\sqrt{\cdot}.

With the LDLTLDL^T factorization, sigma points are generated as:

σk=x^±n+λ⋅L⋅Dk⋅ek\sigma_k = \hat{x} \pm \sqrt{n + \lambda} \cdot L \cdot \sqrt{D_k} \cdot e_k

Each Dk\sqrt{D_k} involves only a single scalar — not an accumulated error propagated from previous columns. This is the fundamental stability advantage.

A critical practical benefit: when the covariance update P=Ppred−KSKTP = P_{\text{pred}} - K S K^T introduces rounding errors that make PP slightly non-SPD (which happens in practice), the two methods behave very differently:

  • Cholesky: attempts negative\sqrt{\text{negative}} and fails completely
  • LDLTLDL^T: produces a negative DD entry, which can be detected and handled (e.g., clamping, covariance reset, or using Bunch-Kaufman pivoting)

MTL5 includes two UKF examples that demonstrate these effects.

Example 1: Range+Bearing UKF (examples/ukf_cholesky_vs_ldlt/)

Section titled “Example 1: Range+Bearing UKF (examples/ukf_cholesky_vs_ldlt/)”

A 4-state nonlinear tracking problem:

  • State: [px, py, vx, vy] — 2D position and velocity
  • Process model: constant velocity with nonlinear quadratic drag
  • Measurement model: range and bearing from a beacon at (10, 0)
  • Scenarios: benign (R = I), moderate (R = diag(0.01, 0.1)), severe (R = diag(1e-14, 1e-2)), and intermittent

Example 2: Bearing-Only UKF (examples/ukf_bearing_only/)

Section titled “Example 2: Bearing-Only UKF (examples/ukf_bearing_only/)”

The canonical ill-conditioning generator:

  • Measurement: bearing only (no range) — one direction of P collapses while the other stays large
  • Tight measurement noise: R = 1e-4
  • Precision comparison: runs in both float64 and float32 to show where Cholesky breaks
  • Key diagnostic: sigma-point mean bias — measures the asymmetry introduced by degraded factorizations
Terminal window
cmake --preset dev
cmake --build build --target example_ukf_comparison example_bearing_only_ukf
./build/examples/example_ukf_comparison
./build/examples/example_bearing_only_ukf

Double precision: both methods perform identically

Section titled “Double precision: both methods perform identically”

In float64, both Cholesky and LDL^T succeed across all scenarios. The condition numbers reach ~10^4, well within the ~10^15 that double precision can handle:

=== Scenario: Benign (R = diag(1.0e+00, 1.0e+00)) ===
Step cond(P) Chol-err LDLT-err Chol-resid LDLT-resid
0 2.21e+00 9.70e-01 9.70e-01 6.12e-17 0.00e+00
100 6.42e+01 1.37e+00 1.37e+00 3.88e-17 2.00e-17
199 3.26e+02 1.50e+00 1.50e+00 1.19e-16 7.49e-18
Cholesky: completed 200 steps, final error = 1.505e+00
LDL^T: completed 200 steps, final error = 1.505e+00

Both methods produce identical estimation errors and residuals at machine epsilon level. This is the expected baseline.

Single precision: Cholesky fails, LDL^T detects the problem

Section titled “Single precision: Cholesky fails, LDL^T detects the problem”

The bearing-only example in float32 shows the critical difference. At step 5, the covariance update rounding errors make P non-SPD:

=== Bearing-Only UKF (float32, 24-bit significand) ===
Step cond(P) Chol LDLT Chol-bias LDLT-bias
0 1.0e+00 OK OK 2.19e-02 2.19e-02
4 6.1e+00 OK OK 3.40e-02 3.40e-02
5 2.1e+02 FAIL FAIL N/A N/A
6 2.1e+02 FAIL FAIL N/A N/A
...
Cholesky: 5/15 steps OK (10 FAILED), max bias = 8.96e-02
LDL^T: 5/15 steps OK (10 FAILED), max bias = 8.96e-02

Both methods detect the failure — but the failure modes differ:

  • Cholesky fails via sqrt(negative), providing no information about which direction went bad
  • LDL^T ldlt_factor() succeeds — it only fails on zero pivots. Negative D entries are representable and indicate indefiniteness when inspected afterward. The caller can examine the D vector to identify exactly which eigenvalue direction became negative.

This diagnostic difference is what enables graceful recovery strategies: inspect D after factorization, clamp negative entries, reset the covariance, or trigger a warning — rather than handling a hard factorization failure.

Indefinite matrices: Cholesky crashes, LDLTLDL^T succeeds

Section titled “Indefinite matrices: Cholesky crashes, LDLTLDL^TLDLT succeeds”

The direct factorization stress test constructs matrices with one deliberately negative eigenvalue — simulating what happens when covariance update rounding goes wrong:

--- Nearly-indefinite matrices (smallest eigenvalue < 0) ---
min_eig Cholesky LDL^T D entries
-1.0e-14 FAIL (non-SPD) OK [+,+,+,-]
-1.0e-10 FAIL (non-SPD) OK [+,+,+,-]
-1.0e-06 FAIL (non-SPD) OK [+,+,+,-]
-1.0e-02 FAIL (non-SPD) OK [+,+,+,-]

Cholesky fails on all four cases. LDLTLDL^T succeeds and reports the DD entry signs, showing exactly one negative pivot. A UKF implementation can use this information to clamp the offending direction, reset the covariance, or trigger a diagnostic warning.

  • The matrix is guaranteed SPD (e.g., formed as ATA+regularizationA^T A + \text{regularization})
  • You need maximum performance and LAPACK dpotrf is available (it’s the most optimized factorization in most BLAS libraries)
  • Working in double precision with well-conditioned matrices (κ<108\kappa < 10^8)
  • Backward compatibility with existing code is required
  • The matrix may be ill-conditioned (Kalman filters, optimization Hessians)
  • The matrix may be symmetric indefinite (modified Newton methods, saddle-point systems)
  • Working in reduced precision (float32, float16, posit, custom types)
  • You need to detect indefiniteness rather than crashing
  • No square root is available for the number type (e.g., some custom arithmetic)

Use Bunch-Kaufman pivoted LDLTLDL^T when:

Section titled “Use Bunch-Kaufman pivoted LDLTLDL^TLDLT when:”
  • The matrix is expected to be indefinite (not just nearly-indefinite)
  • You need a numerically stable factorization regardless of pivot ordering
  • Graceful degradation is more important than raw speed

If κ(P)\kappa(P) can exceed approximately 10810^8 in your application, prefer LDLTLDL^T over Cholesky for sigma point generation. For reduced-precision types (float32, posit), the threshold is proportionally lower — roughly 10b/410^{b/4} where bb is the number of significand bits.

#include <mtl/operation/cholesky.hpp>
// Factor: A = L * L^T (in-place, lower triangle overwritten with L)
int info = mtl::cholesky_factor(A); // returns 0 on success
// Solve: given precomputed L, solve A*x = b
mtl::cholesky_solve(L, x, b);
#include <mtl/operation/ldlt.hpp>
// Factor: A = L * D * L^T (in-place, lower triangle gets L, diagonal gets D)
int info = mtl::ldlt_factor(A); // returns 0 on success, k+1 on zero pivot
// Solve: given precomputed LDL^T factors, solve A*x = b
mtl::ldlt_solve(A, x, b);

Both factorizations have sparse counterparts in mtl::sparse::factorization:: with symbolic/numeric phase separation and fill-reducing ordering support. See <mtl/sparse/factorization/sparse_cholesky.hpp> and <mtl/sparse/factorization/sparse_ldlt.hpp>.

  • Golub & Van Loan, Matrix Computations, Section 4.1.2 (LDLTLDL^T factorization)
  • Julier & Uhlmann, “Unscented Filtering and Nonlinear Estimation”, Proc. IEEE, 92(3), 2004
  • Davis, Direct Methods for Sparse Linear Systems, SIAM, 2006
  • Bar-Shalom, Li, Kirubarajan, Estimation with Applications to Tracking and Navigation, Ch. 11