(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 ( [e-mail]) is a graduate research assistant in the Department of Computer Science at the University of Texas, Austin, TX, USA.

Swarnendu Biswas ( [e-mail]) is an assistant professor in the Department of Computer Science and Engineering at the Indian Institute of Technology, Kanpur, India.

Donald S. Fussell ( [e-mail]) is the Trammell Crow Regents Professor in the Department of Computer Science at the University of Texas, Austin, TX, USA. Keshav Pingali ( [e-mail]) 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