The Kalman Filter and Unscented Kalman Filter are occasionally prone to failure due to numerical errors, causing the algorithm to return incorrect estimates or fail entirely. These errors typically surface when one or more of the filtered_state_covariances have very, very small eigenvalues. In order to remain a valid covariance matrix, all of the eigenvalues of filtered_state_covariances must remain positive – in other words, must remain positive definite. Unfortunately, the Kalman Filter update equations involve subtracting two positive definite matrices which, due to numerical error, can result in a negative definite matrix that is no longer a proper covariance matrix! Once that happens, the filter can no longer continue.

To combat this, two versions of the Kalman Filter and a version of the Additive-noise Unscented Kalman Filter are implemented which use factorized versions of filtered_state_covariances. Unlike their standard counterparts, these implementations are far less susceptible to numerical error, but do require roughly 20% more time to run.

Cholesky-Based Kalman Filter

The first is CholeskyKalmanFilter, which uses the Cholesky factorization to decompose a covariance matrix into the product of two lower triangular matrices, that is

System Message: WARNING/2 (\Sigma = L L^{T})

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2014) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9k> and hyphenation patterns for 2 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.131 \endinput ^^M No pages of output. Transcript written on math.log.

Since

System Message: WARNING/2 (L)

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2014) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9k> and hyphenation patterns for 2 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.131 \endinput ^^M No pages of output. Transcript written on math.log.
is used instead of

System Message: WARNING/2 (\Sigma)

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2014) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9k> and hyphenation patterns for 2 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.131 \endinput ^^M No pages of output. Transcript written on math.log.
, you can’t accidentally create a matrix that’s negative definite. CholeskyKalmanFilter is designed to be a drop-in replacement for KalmanFilter:

>>> import numpy as np
>>> from pykalman import KalmanFilter as KF1              # standard Kalman Filter formulation
>>> from pykalman.sqrt import CholeskyKalmanFilter as KF2 # LL' decomposition Kalman Filter
>>> from numpy.testing import assert_array_almost_equal
>>> transition_matrix = [[1, 1], [0, 1]]                  # parameters
>>> observation_matrix = [[0.1, 0.5], [-0.3, 0.0]]
>>> measurements = [[1,0], [0,0], [0,1]]                  # measurements
>>> kf1 = KF1(transition_matrices=transition_matrix, observation_matrices=observation_matrix)
>>> kf2 = KF2(transition_matrices=transition_matrix, observation_matrices=observation_matrix)
>>> assert_array_almost_equal(kf1.filter(measurements)[0], kf2.filter(measurements)[0])

Currently only CholeskyKalmanFilter.filter() makes use the Cholesky factorization, so the smoother may still suffer numerical instability.

References:

  • Salzmann, M. A. Some Aspects of Kalman Filtering. August 1988. Page 31.

UDU’-Based Kalman Filter

A second implementation named after its inventor, G. J. Bierman, is the BiermanKalmanFilter. This version is based on a less common matrix decomposition,

System Message: WARNING/2 (\Sigma = U D U^{T})

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2014) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9k> and hyphenation patterns for 2 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.131 \endinput ^^M No pages of output. Transcript written on math.log.

Here

System Message: WARNING/2 (U)

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2014) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9k> and hyphenation patterns for 2 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.131 \endinput ^^M No pages of output. Transcript written on math.log.
is an upper triangular matrix with 1s along the diagonal and

System Message: WARNING/2 (D)

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2014) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9k> and hyphenation patterns for 2 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.131 \endinput ^^M No pages of output. Transcript written on math.log.
is diagonal matrix. The beauty of this representation is that the Kalman Filter update doesn’t require reconstructing

System Message: WARNING/2 (\Sigma)

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2014) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9k> and hyphenation patterns for 2 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.131 \endinput ^^M No pages of output. Transcript written on math.log.
. To use the BiermanKalmanFilter, one only need import it instead of the CholeskyKalmanFilter in the previous example:

>>> from pykalman.sqrt import BiermanKalmanFilter as KF2

Currently only BiermanKalmanFilter.filter() makes use the

System Message: WARNING/2 (UDU^{T})

latex exited with error [stdout] This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2014) (preloaded format=latex) restricted \write18 enabled. entering extended mode (./math.tex LaTeX2e <2011/06/27> Babel <3.9k> and hyphenation patterns for 2 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class (/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo)) (/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty ! LaTeX Error: File `utf8x.def’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: def) Enter file name: ! Emergency stop. <read *> l.131 \endinput ^^M No pages of output. Transcript written on math.log.
factorization, so the smoother may still suffer numerical instability.

References:

  • Gibbs, Bruce P. Advanced Kalman Filtering, Least-Squares, and Modeling: A Practical Handbook. Page 396

Square Root Unscented Kalman Filter

In 2001, the original inventors of the Unscented Kalman Filter derived a “square root” form based on the Cholesky Factorization. Like its standard Kalman Filter counterpart, the “square root” form is less likely to suffer from numerical errors. Its use is identical to the typical AdditiveUnscentedKalmanFilter:

>>> from pykalman.sqrt import AdditiveUnscentedKalmanFilter

The implementations of both AdditiveUnscentedKalmanFilter.filter() and AdditiveUnscentedKalmanFilter.smooth() make use of the Cholesky factorization.

References:

  • Terejanu, G.A. Towards a Decision-Centric Framework for Uncertainty Propagation and Data Assimilation. 2010.
  • Van Der Merwe, R. and Wan, E.A. The Square-Root Unscented Kalman Filter for State and Parameter-Estimation. 2001.

Table Of Contents

This Page