Hello all,
I have a question regarding the square-root Kalman Filter section of the Wikipedia article about Kalman filters (https://en.wikipedia.org/wiki/Kalman_filter).
The text reads as follows:
"Between the two (regular square-root implementation), the U-D factorization uses the same amount of storage, and somewhat less computation, and is the most commonly used square root form."
I see that they need the same amount of storage, but I don't understand why the U-D should is computationally more efficient (in which step do we same computations?).
Furthermore, is the U-D form really the most commonly used from? I mostly saw papers using the standard Cholesky decomposition.
And last but not least, what properties does the state space model need to have (I guess badly conditioned covariance matrices among others) in order
for standard Kalman filters and smoothers to fail?
For which type of concrete problems (examples?) are those square-root filters used?
Thanks a lot in advance!
Yes sure, I know scholar or IEEE Xplore. However, I wanted to hear from someone who ideally has first-hands practical experience with square-root implementations, which one they used e.g. in an industrial setting.
What one finds in papers is usually some small toy examples, I'd be happy to hear about someone having solved a real-world problem with square-root filters.
1. LD factorisation spares of taking square-roots of numbers, which was important say
10 years ago and which is still important if you have processors without (or with expensive) floating-point operations.
2. Use of square-root or LD versions is still important in poorly condition cases,
caused either by almost singular covariance matrices (almost deterministic dependences, whic can be suppressed by careful modelling) or dependences caused by feedback (which cannot be avoided). All these is strenghten when you have to employ a sort of forgetting.
3. All these aspects were touched in the book
@Book(KarBoh:20050084,
title = {Optimized {B}ayesian Dynamic Advising: {T}heory and Algorithms},
author = {M. K{\'{a}}rn{\'{y}} and J. B{\"{o}}hm and T. V. Guy and
L. Jirsa and I. Nagy and P. Nedoma and L. Tesa{\v{r}}},
publisher = {Springer},
year = {2006},
ident = {UTIA-B 20050084} )
which is poorly readable but which can serve you as a starting point for a huge amount of works related to the topic and which (unlie majority of existing works) uses square-root or LD decompositions for control design, too.
Federico,
Well, "small toy examples" are hardly likely to bring out the comparative advantages of Cholesky vs. U-D, if any !!
I too, seem to share the same concern and observation as you, that is:
Any inputs on #1 please, anyone ??
-Sanjay
Speaking of advantages of various square-root implementations, I would suggest considering the V-Lambda SR filtering approach (with which I am sort of acquainted, for proper disclosure :-)) Not mentioned in Wikipedia, this approach does not offer computational advantages, but 1) it is a SR approach (namely, a numerically-stable implementation), and moreover 2) it works with the spectral decomposition of the covariance, i.e., you get to actually see the eigenvalues and eigenvectors of the covariance at all times. This can become very useful at times!
-- Yaakov
The U-D filter implementation does not require computing square roots, and the "multiplies" by the diagonal elements of U do not require a multiplication (by 1)
The first "square root" implementation of the Kalman filter was derived by the late James Potter at what was then the MIT Instrumentation Laboratory. It enabled the Apollo computer to implement the space navigation problem for the moon missions in 15-bit fixed-point arithmetic. The late Gerald Bierman, co-developer of the U-D filter (along with Catherine Thornton), characterized square-root implementations as "achieving the same accuracy with half as many bits." All the square-root implementations use a square-root factorization of the covariance matrix of estimation, the condition number of which (a metric for digital inversion accuracy) is the square root of the condition number of the covariance matrix. Otherwise, relative performances of the various square-root implementations are not predominantly application-dependent.
The UDU is computationally efficient but it is NOT a square root formulation and does not necessarily improve the condition number. That’s the price to pay to save the computations of actual square roots. Considere the UDU factorization of a diagonal covariance matrix P. Then U is the identity matrix and D = P, therefore D and P have the same condition number.
UDU is super convenient because it is numerically efficient in ensuring symmetry (by construction) and positive definiteness (by checking the sign of the Elements of D). having checks for positive definiteness for full covariances in flight software is not trivial.
Today, sparsity computation is popular. When you choose batch estimation, square root method is better than UD method. Square root method can keep the sparsity of the problem. However, if you choose sequential filtering, UD is better.
The wiki article is misleading or unclear, as are some of the explanations here. For example:
"All the square-root implementations use a square-root factorization of the covariance matrix of estimation, the condition number of which (a metric for digital inversion accuracy) is the square root of the condition number of the covariance matrix."
and from my friend Renato,
"The UDU is computationally efficient but it is NOT a square root formulation and does not necessarily improve the condition number. "
My point is that any Kalman filter implementation in which the covariance is factorized in the time or measurement update, and then re-computed from the factors, is not a true square root implementation. (Yes, I have seen that.) Such an algorithm is not necessarily numerically stable or efficient. The condition number is squared when the covariance is formed from the factors. Likewise, computing the factorization (UDU, Cholesky, or whatever) from the covariance matrix does not improve the condition number. A true square root implementation maintains the covariance matrix in factorized form and uses orthogonalization in the time and measurement updates, and so is numerically stable and does not worsen the condition number. The factors are just a representation of the covariance matrix. The only time the covariance matrix has to be computed is for output, and even then one does not have to compute every element in the matrix. Note that the process noise matrix should not be computed and factored either, though some imprecision in the process noise is usually tolerable.
- Badges
- Science topic
- Similar topics
- Social Psychology
- Attitude