In recursive Bayesian estimation—such as Kalman filtering, smoothing, and belief-space planning—the state uncertainty is tracked via a covariance matrix $P$. Mathematically, a valid covariance matrix must always be symmetric and positive semi-definite (PSD), meaning all its eigenvalues are non-negative.
However, when these algorithms are implemented in finite-precision floating-point arithmetic, maintaining these mathematical properties becomes a severe challenge. Standard filtering equations are prone to numerical degradation, often causing the filter to diverge or crash. Square-root filtering solves this fundamental vulnerability by changing how uncertainty is represented and updated.
The Root of Instability: Catastrophic Cancellation
To understand why standard filters fail, consider the classic Kalman covariance update step:
$$P_{k|k} = P_{k|k-1} - K_k S_k K_k^T$$
This operation relies on matrix subtraction. As Duník et al. point out, standard covariance propagation is highly susceptible to numerical rounding errors. When a sensor measurement is highly accurate, the variance reduction term ($K_k S_k K_k^T$) becomes nearly equal to the prior uncertainty ($P_{k|k-1}$). Subtracting two large, nearly identical floating-point numbers results in catastrophic cancellation, where the most significant digits cancel out, leaving only rounding noise.
This precision loss causes the eigenvalues of $P$ to drift. As observed by Totaro et al., standard implementations frequently suffer from numerical instability where covariance matrices lose their symmetry or positive semi-definiteness. Once a covariance matrix develops a negative eigenvalue, the filter enters an unphysical state: it registers negative variances.
Standard Filtering:
[ Prior Covariance P ] minus [ Innovation Gain KSKᵀ ] ==> [ Risk of Negative Eigenvalues! ]
Square-Root Filtering:
[ Cholesky Factor S ] ==(Orthogonal Rotations)==> [ New Factor S' ] ==> P' = S'S'ᵀ (Always PSD)
This failure mode is particularly destructive in modern machine learning pipelines. Kloss et al. and Ansari et al. highlight that during the end-to-end gradient-based training of differentiable filters and continuous-time state-space models, matrix operations easily lead to non-positive-definite matrices. This mathematical collapse triggers singular matrices, exploding gradients, and immediate training failure.
The Square-Root Intuition
Instead of tracking and updating the full covariance matrix $P$, square-root filtering decomposes $P$ into a product of a matrix $S$ and its transpose:
$$P = S S^T$$
Typically, $S$ is chosen to be the lower-triangular Cholesky factor of $P$.
This algebraic shift provides an absolute mathematical guarantee: the reconstructed covariance matrix $P$ can never become non-positive definite. For any real matrix $S$, the product $S S^T$ is inherently positive semi-definite by construction. Even if $S$ accumulates significant rounding errors, squaring it will always yield non-negative eigenvalues, preventing the filter from ever calculating a negative variance.
Furthermore, tracking $S$ instead of $P$ effectively halves the condition number of the numerical operations. If a covariance matrix $P$ has a condition number of $\kappa$, its square root $S$ has a condition number of $\sqrt{\kappa}$. This reduction in dynamic range allows algorithms to remain highly accurate in lower-precision environments. As Demmel et al. and Tronarp demonstrate, square-root formulations allow complex estimation and bundle adjustment tasks to run reliably using single-precision (32-bit) floating-point arithmetic where standard methods completely fail.
Updating the Factor via Orthogonal Transformations
The core trick to making square-root filtering work is that $P$ is never explicitly reconstructed. If an algorithm squares $S$ to compute an update and then takes the Cholesky decomposition of the result, the numerical vulnerability remains. Instead, the filter must update the factor $S$ directly.
Early square-root designs achieved this using Cholesky "downdates" to handle the subtraction step, but Tronarp notes that these subtractions still risk numerical instability on low-precision hardware. Modern implementations bypass subtraction entirely by leveraging QR decomposition and Givens rotations.
To perform a measurement update, the prior square-root factor and the measurement matrix components are stacked into a large compound matrix. An orthogonal transformation matrix $Q$ (where $Q Q^T = I$) is then applied to zero out the lower blocks of this matrix, transforming it into an upper- or lower-triangular form:
$$\begin{pmatrix} S_{prior}^T & H^T \\ 0 & R^{1/2} \end{pmatrix} Q = \begin{pmatrix} S_{post}^T & 0 \\ * & * \end{pmatrix}$$
Because orthogonal matrices preserve vector lengths ($L_2$ norms), multiplying by $Q$ does not amplify rounding errors. The subtraction inherent in the Kalman update is replaced by a sequence of stable coordinate rotations.
Kaess et al. leveraged this property to build fast incremental smoothing algorithms, maintaining an upper-triangular square-root factor of the measurement Jacobian using Givens rotations to preserve both numerical stability and problem sparsity. Similarly, Krämer demonstrates that performing fixed-point smoothing via Cholesky-based QR updates prevents error accumulation in stiff systems, entirely avoiding non-physical artifacts like negative variances without requiring state augmentation.
Alternative Factorizations and Frontiers
While Cholesky-based QR updates are the standard choice, other matrix factorizations are deployed depending on the specific structural constraints of the system:
- Singular Value Decomposition (SVD): In highly noisy or rank-deficient scenarios, SVD serves as a robust alternative to Cholesky decomposition. Shao et al. employ SVD factorization to handle ill-conditioned matrices arising from measurement uncertainties, while Kumatani et al. use SVD to isolate the nullspace of aliasing matrices, ensuring system matrices never become singular during optimization.
- Ensemble Space Transformations: In high-dimensional fluid dynamics or meteorological modeling, tracking full matrices is computationally impossible. Le Provost et al. utilize a deterministic ensemble transform filter that performs updates in a lower-dimensional ensemble space via symmetric square-root factorization, preserving the true posterior covariance without injecting artificial stochastic noise.
- Tensor Networks and High-Order Solvers: For systems with massive state spaces, Batselier et al. and Batselier et al. introduce low-rank Tensor Networks to compress the filter state, identifying the development of square-root tensor variants as the critical open frontier for long-term tracking stability. This structural protection is also vital for probabilistic numerical ODE solvers; Bosch et al. demonstrate that propagating Cholesky factors is essential to keep high-order parallel-in-time solvers from becoming ill-conditioned over long integration horizons.
Key Foundational Work
Fast Incremental Square Root Information Smoothing (2007) — contributed 1 concept elements to this direction.
Filter Bank Design for Subband Adaptive Beamforming and Application to Speech Recognition (2008) — contributed 1 concept elements to this direction.