(MVUE) ). This result is proved using
the Cramer-Rao lower bound.
24
Extension to Nonlinear Systems
The extended Kalman filter (EKF) and
unscented Kalman filter (UKF) are heuristic approaches to using Kalman
filtering for nonlinear systems. The
state evolution and measurement
equations for nonlinear systems with
additive noise can be written as follows; in these equations, f and h are
nonlinear functions.
( 42)
( 43)
Intuitively, the EKF constructs
linear approximations to the nonlinear functions f and h and applies the
Kalman filter equations, whereas the
UKF constructs approximations to
probability distributions and propagates these through the nonlinear
functions to construct approximations
to the posterior distributions.
EKF. Examining Figure 6d, we see
that the a priori state estimate in the predictor can be computed using the system model: . However,
as the system dynamics and measurement equations are nonlinear, it is not
clear how to compute the co-variance
matrices for the a priori estimate and
the measurement. In the EKF, these
matrices are computed by linearizing
Equations 42 and 43 using the Taylor
series expansions for the nonlinear
functions f and h. This requires computing the following Jacobians,e which play
the role of Ft and Ht in Figure 6d.
The EKF performs well in some
applications such as navigation systems
and GPS.
28
UKF. When the system dynamics
and observation models are highly
nonlinear, the unscented Kalman filter (UKF)
15 can be an improvement
over the EKF. The UKF is based on the
unscented transformation, which is a
method for computing the statistics
of a random variable x that undergoes
e The Jacobian matrix is the matrix of all first
order partial derivatives of a vector-valued
function.
a nonlinear transformation (y = g(x)).
The random variable x is sampled
using a carefully chosen set of sigma
points and these sample points are
propagated through the nonlinear
function g. The statistics of y are estimated using a weighted sample mean
and covariance of the posterior sigma
points. The UKF tends to be more
robust and accurate than the EKF but
has higher computation overhead
due to the sampling process.
Conclusion
In this article, we have shown that
two concepts—optimal linear estimators for fusing uncorrelated estimates
and best linear unbiased estimators
for correlated variables—provide the
underpinnings for Kalman filtering.
By combining these ideas, standard
results on Kalman filtering for linear
systems can be derived in an intuitive
and straightforward way that is simpler
than other presentations of this material in the literature. This approach
makes clear the assumptions that
underlie the optimality results associated with Kalman filtering and should
make it easier to apply Kalman filtering
to problems in computer systems.
Acknowledgments
This research was supported by NSF
grants 1337281, 1406355, and 1618425,
and by DARPA contracts FA8750-16-
2-0004 and FA8650-15-C-7563. We are
indebted to K. Mani Chandy (Caltech),
Ivo Babuska (UT Austin,) and Augusto
Ferrante (Padova, Italy) for their valuable feedback.
References
1. Babb, T. How a Kalman filter works, in pictures
| bzarg. 2018. https://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/. Accessed: 2018-11-30
2. Balakrishnan, A.V. Kalman Filtering Theory. Optimization
Software, Inc., Los Angeles, CA, USA, 1987.
3. Barker, A.L., Brown, D. E., Martin, W.N. Bayesian
Estimation and the Kalman Filter. Technical Report.
Charlottesville, VA, USA, 1994.
4. Becker, A. Kalman filter overview. https://www.
kalmanfilter.net/default.aspx. 2018. Accessed: 2018-11-08.
5. Bergman, K. Nanophotonic interconnection networks
in multicore embedded computing. In 2009 IEEE/
LEOS Winter Topicals Meeting Series (2009), 6–7.
6. Cao, L., Schwartz, H.M. Analysis of the Kalman
filter based estimation algorithm: An orthogonal
decomposition approach. Automatica 1, 40 (2004), 5–19.
7. Chui, C. K., Chen, G. Kalman Filtering: With Real- Time
Applications, 5th edn. Springer Publishing Company,
Incorporated, 2017.
8. Eubank, R.L. A Kalman Filter Primer (Statistics: Textbooks
and Monographs). Chapman & Hall/CRC, 2005.
9. Evensen, G. Data Assimilation: The Ensemble Kalman
Filter. Springer-Verlag New York, Inc., Secaucus, NJ,
USA, 2006.
10. Faragher, R. Understanding the basis of the Kalman
filter via a simple and intuitive derivation. IEEE Signal
Process. Mag. 5, 29 (2012), 128–132.
11. Grewal, M.S., Andrews, A.P. Kalman Filtering: Theory and
Practice with MATLAB, 4th edn. Wiley-IEEE Press, 2014.
12. Hess, A.-K., Rantzer, A. Distributed Kalman filter
algorithms for self-localization of mobile devices.
In Proceedings of the 13th ACM International
Conference on Hybrid Systems: Computation and
Control, HSCC ‘ 10, 2010, 191–200.
13. Imes, C., Kim, D. H. K., Maggio, M., Hoffmann, H. POE T:
A portable approach to minimizing energy under soft
real-time constraints. In 21st IEEE Real-Time and
Embedded Technology and Applications Symposium,
April 2015, 75–86.
14. Imes, C., Hoffmann, H. Bard: A unified framework
for managing soft timing and power constraints. In
International Conference on Embedded Computer
Systems: Architectures, Modeling and Simulation
(SAMOS), 2016.
15. Julier, S. J., Uhlmann, J. K. Unscented filtering and non-
linear estimation. Proc. IEEE 3, 92 (2004), 401–422.
16. Kitanidis, P.K. Unbiased minimum-variance linear
state estimation. Automatica 6, 23 (1987), 775–778.
17. Lindquist, A., Picci, G. Linear Stochastic Systems.
Springer-Verlag, 2017.
18. Maybeck, P. S. Stochastic Models, Estimation, and
Control, volume 3. Academic Press, 1982.
19. Mendel, J.M. Lessons in Estimation Theory for Signal
Processing, Communications, and Control. Pearson
Education, 1995.
20. Nagarajan, K., Gans, N., Jafari, R. Modeling human gait
using a Kalman filter to measure walking distance. In
Proceedings of the 2nd Conference on Wireless Health,
WH ‘ 11 (New York, NY, USA, 2011). ACM, 34:1–34: 2.
21. Nakamura, E.F., Loureiro, A.A.F., Frery, A. C. Information
fusion for wireless sensor networks: methods, models,
and classifications. ACM Comput. Surv. 3, 39 (2007).
22. Petersen, K.B., Pedersen, M.S. The Matrix Cookbook.
http://www2.imm.dtu.dk/pubdb/views/publication_
details.php?id=3274. November 2012. Version 20121115.
23. Pothukuchi, R.P., Ansari, A., Voulgaris, P., Torrellas, J.
Using multiple input, multiple output formal control
to maximize resource efficiency in architectures. In
Proceedings of the 2016 ACM/IEEE 43rd Annual
International Symposium on Computer Architecture
(ISCA) (2016), IEEE, 658–670.
24. Rao, C.R. Information and the accuracy attainable
in the estimation of statistical parameters. Bull.
Calcutta Math. Soc., 37 (1945), 81–89.
25. Rhudy, M. B., Salguero, R. A., Holappa, K. A Kalman
filtering tutorial for undergraduate students. Int. J.
Comp. Sci. Eng. Surv. ( 1), 8 (2017).
26. Sengupta, S.K. Fundamentals of statistical signal
processing: Estimation theory. Technometrics ( 4), 37
(1995), 465–466.
27. Souza, É. L., Nakamura, E. F., Pazzi, R. W. Target
tracking for sensor networks: A survey. ACM Comput.
Surv. (
2), 49 (2016), 30:1–30: 31.
28. Thrun, S., Burgard, W., Fox, D. Probabilistic Robotics
(Intelligent Robotics and Autonomous Agents). The
MI T Press, 2005.
29. Welch, G., Bishop, G. An Introduction to the Kalman
Filter. Technical Report. Chapel Hill, NC, USA, 1995.
30. Pei, Y., Biswas, S., Fussell, D.S., Pingali, K. An
Elementary Introduction to Kalman Filtering. ArXiv
e-prints. October 2017.
The online appendix for this article can be found at http://
dl.acm.org/citation.cfm?doid=3363294&picked=formats
Yan Pei ( ypei@cs.utexas.edu) is a graduate research
assistant in the Department of Computer Science at the
University of Texas, Austin, TX, USA.
Swarnendu Biswas ( swarnendu@cse.iitk.ac.in) is
an assistant professor in the Department of Computer
Science and Engineering at the Indian Institute of
Technology, Kanpur, India.
Donald S. Fussell ( fussell@cs.utexas.edu) is the Trammell
Crow Regents Professor in the Department of Computer
Science at the University of Texas, Austin, TX, USA.
Keshav Pingali ( pingali@cs.utexas.edu) is a professor in
the Department of Computer Science at the University
of Texas, Austin, and the W.A.” Tex” Moncrief Chair of
Computing in the UT Oden Institute of Computational
Engineering and Science, Austin, TX, USA.
© 2019 ACM 0001-0782/19/11 $15.00