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.