UKF Numerical Stability: Cholesky vs LDL^T Decomposition
The Unscented Kalman Filter (UKF) generates sigma points from the state covariance matrix at every time step. This requires a matrix factorization that serves as a “square root” of . The choice of factorization has a direct impact on filter stability, particularly when becomes ill-conditioned after informative observations.
This document walks through MTL5’s UKF comparison examples, explains why the (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”Why the UKF needs a matrix square root
Section titled “Why the UKF needs a matrix square root”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 , the sigma points are:
where is a matrix satisfying . The standard approach computes via Cholesky factorization: .
How informative observations create ill-conditioning
Section titled “How informative observations create ill-conditioning”When a measurement is very precise (small measurement noise ), the Kalman update collapses one or more directions of the state covariance toward machine epsilon while others remain . This creates extreme eigenvalue spread:
- Well-observed direction: eigenvalue
- Poorly-observed direction: eigenvalue or larger
The condition number can reach in double precision and in single precision after just a few updates.
The precision loss mechanism
Section titled “The precision loss mechanism”Standard Cholesky factorization computes the diagonal of via:
When is near machine epsilon after the subtraction, the operation halves the number of significant digits:
- In float64 (53-bit significand): , losing ~7.5 digits
- In float32 (24-bit significand): , losing ~3.5 digits
- In float16 (11-bit significand): essentially all precision is lost
This degraded diagonal entry propagates into every subsequent column of , contaminating the entire factorization.
The Solution: Factorization
Section titled “The Solution: LDLTLDL^TLDLT Factorization”Mathematical relationship
Section titled “Mathematical relationship”The decomposition factors a symmetric matrix as:
where is unit lower triangular (ones on the diagonal) and is diagonal. Comparing with Cholesky:
| Property | Cholesky () | |
|---|---|---|
| Diagonal of | 1 (unit diagonal) | |
| Square roots | One per column | None |
| Stores | (lower triangular) | (unit lower) + (diagonal) |
| Cost | ||
| SPD required | Yes | No (works for indefinite) |
Why avoiding square roots preserves precision
Section titled “Why avoiding square roots preserves precision”The algorithm computes directly:
No square root is taken. retains the full precision of the subtraction result, however small. The unit lower triangular entries are:
This is a simple division, not a precision-destroying .
Sigma point generation with
Section titled “Sigma point generation with LDLTLDL^TLDLT”With the factorization, sigma points are generated as:
Each involves only a single scalar — not an accumulated error propagated from previous columns. This is the fundamental stability advantage.
Detecting indefiniteness
Section titled “Detecting indefiniteness”A critical practical benefit: when the covariance update introduces rounding errors that make slightly non-SPD (which happens in practice), the two methods behave very differently:
- Cholesky: attempts and fails completely
- : produces a negative entry, which can be detected and handled (e.g., clamping, covariance reset, or using Bunch-Kaufman pivoting)
Experiment Setup
Section titled “Experiment Setup”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
Building and running
Section titled “Building and running”cmake --preset devcmake --build build --target example_ukf_comparison example_bearing_only_ukf./build/examples/example_ukf_comparison./build/examples/example_bearing_only_ukfResults and Interpretation
Section titled “Results and Interpretation”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+00Both 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-02Both 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, 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. succeeds and reports the 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.
When to Use Which
Section titled “When to Use Which”Use Cholesky () when:
Section titled “Use Cholesky (LLTLL^TLLT) when:”- The matrix is guaranteed SPD (e.g., formed as )
- You need maximum performance and LAPACK
dpotrfis available (it’s the most optimized factorization in most BLAS libraries) - Working in double precision with well-conditioned matrices ()
- 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 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
Rule of thumb
Section titled “Rule of thumb”If can exceed approximately in your application, prefer over Cholesky for sigma point generation. For reduced-precision types (float32, posit), the threshold is proportionally lower — roughly where is the number of significand bits.
MTL5 API Reference
Section titled “MTL5 API Reference”Dense Cholesky
Section titled “Dense Cholesky”#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 = bmtl::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 = bmtl::ldlt_solve(A, x, b);Sparse versions
Section titled “Sparse versions”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>.
Further Reading
Section titled “Further Reading”- Golub & Van Loan, Matrix Computations, Section 4.1.2 ( 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