On Modern Array Algorithms for Optimal Discrete Filtering

Nowadays, computational methods for optimal estimation have become an independent field of research and have received a great progress. Modern numerically efficient array algorithms are attractive not only because of their robustness to machine round-off errors, but additionally because of utilization various types of matrix orthogonal transformations. Thus, their design pattern is well suited for parallel implementations on modern computing systems. These properties allow to develop new efficient information technologies, in particular, the techniques that are applicable for solving real-time problems as well as for processing big data arrays. This paper gives a brief survey of modern array algorithms for optimal linear discrete-time filtering. Four large classes of array algorithms are considered:
square-root array algorithms, array algorithms based on weighted orthogonalization, J-orthogonal array algorithms and methods based on singular value decomposition. We suggest a classification of array algorithms according to the type of the utilized matrix orthogonal transformation on the basis of which these algorithms are designed. Such classification suggests a more simple way for understanding the array filtering methods' design and gives a choice for finding their most effective implementation for estimating multivariable discrete-time linear stochastic systems. The computational aspects of array algorithms are investigated. It includes the numerical stability to machine round-off errors, and discussion of efficient software implementation for the array algorithms under examination. Finally, the array algorithms investigated in this paper are algebraically equivalent to the conventional implementation of the discrete-time Kalman filter, but they possess the significantly improved computational properties. The results of the presented comparative study allow to conclude that the use of array algorithms in solving practical problems helps to obtain numerically efficient and reliable solutions.

Keywords

discrete filtering; linear stochastic systems; Kalman filter; matrix orthogonal transforms; array algorithms.

References

1. Kalman R.E. A New Approach to Linear Filtering and Prediction Problems. Journal of Basic Engineering, 1960, vol. 82, no. 1, pp. 35-45. DOI: 10.1115/1.3662552
2. Potter J.E., Stern R.G. Statistical Filtering of Space Navigation Measurements. AIAA Guidance, Navigation and Control Conference, Cambridge, 1963, 13 p. DOI: 10.2514/6.1963-333
3. Rauch H.E., Striebel C.T., Tung F. Maximum Likelihood Estimates of Linear Dynamic Systems. AIAA journal, 1965, vol. 3, no. 8, pp. 1445-1450. DOI: 10.2514/3.3166
4. Dyer P., McReynolds S. Extension of Square-Root Filtering to Include Process Noise. tJournal of Optimization Theory and Applications, 1969, no. 3, pp. 444-459. DOI: 10.1007/BF00929358
5. Schmidt S.F. Computational Techniques in Kalman Filtering Theory and Applications of Kalman Filtering. NATO Advisory Group for Aerospace Research and Development, 1970.
6. Kaminski P.G., Bryson A.E., Schmidt S.F. Discrete Square-Root Filtering: A Survey of Current Techniques. IEEE Transactions on Automatic Control, 1971, vol. 16, no. 6, pp. 727-735. DOI: 10.1109/TAC.1971.1099816
7. Kaminski P.G. Square Root Filtering and Smoothing for Discrete Processes. Ph.D. Thesis, Stanford University, 1971.
8. Kailath T. Some New Algorithms for Recursive Estimation in Constant Linear System. IEEE Transactions on Information Theory, 1973, vol. 19, no. 11, pp. 750-760. DOI: 10.1109/TIT.1973.1055104
9. Morf M., Sidhu G.S., Kailath T. Some New Algorithms for Recursive Estimation in Constant. Linear Discrete-Time Systems. IEEE Transactions on Automatic Control, 1974, vol. 19, no. 4, pp. 315-323. DOI: 10.1109/TAC.1974.1100576
10. Morf M., Kailath T. Square-Root Algorithms for Least-Squares Estimation. IEEE Transactions on Automatic Control, 1975, vol. 20, no. 4, pp. 487-497. DOI: 10.1109/TAC.1975.1100994
11. Thornton C.L., Bierman G.J. Numerical Comparison of Discrete Kalman Filtering Algorithms: an Orbit Determination Case Study. JPL Technical Memorandum 33-771, 1976, 48 p.
12. Thornton C.L. Triangular Covariance Factorizations for Kalman Filtering. Ph.D. Thesis, University of California at Los Angeles, 1976.
13. Bierman G.J. Factorization Methods For Discrete Sequential Estimation. N.Y., Academic Press, 1977.
14. Fomin V.N. Rekurrentnoe otsenivanie i adaptivnaya fil'tratsiya [Recurrent Estimation and Adaptive Filtering]. Мoscow, Nauka, 1984. (in Russian)
15. Verhaegen M., Van Dooren P. Numerical Aspects of Different Kalman Filter Implementations. IEEE Transactions on Automatic Control, 1986, vol. 31, no. 10, pp. 907-917. DOI: 10.1109/TAC.1986.1104128
16. Jover J.M., Kailath T. A Parallel Architecture for Kalman Filter Measurement Update and Parameter Estimation. Automatica, 1986, vol. 22, no. 1, pp. 43-57. DOI: 10.1016/0005-1098(86)90104-4
17. Ogarkov M.A. Metody statisticheskogo otsenivaniya parametrov sluchajnykh protsessov [Methods of Statistical Estimation of Parameters of Random Processes]. Moscow, Energoatomizdat, 1990. (in Russian)
18. Wang L., Libert G., Manneback P. Kalman Filter Algorithm Based on Singular Value Decomposition. Proceedings on the IEEE Conference on Decision and Control, 1992, pp. 1224-1229. DOI: 10.1109/CDC.1992.371522
19. Sayed A.H., Kailath T. Extended Chandrasekhar Recursions. IEEE Transactions on Automatic Control, 1994, vol. 9, no. 3, pp. 619-622. DOI: 10.1109/9.280773
20. Park P., Kailath T. New Square-Root Algorithms for Kalman Filtering. IEEE Transactions on Automatic Control, 1995, vol. 40, no. 5, pp. 895-899. DOI: 10.1109/9.384225
21. Golub G., Van Loan Ch. Matrix Computations. Johns Hopkins University Press, 1996.
22. Kailath T., Sayed A.H., Hassibi B. Linear Estimation. New Jersey, Prentice Hall, 2000.
23. Grewal M.S., Andrews A.P. Kalman Filtering: Theory and Practice Using MATLAB. New Jersey, Prentice Hall, 2001.
24. Higham N.J. Accuracy and Stability of Numerical Algorithms. Philadelphia, SIAM, 2002.
25. Higham N.J. J-Orthogonal Matrices: Properties and Generalization. SIAM Review, 2003, vol. 45, no. 3, pp. 504-519. DOI: 10.1137/S0036144502414930
26. Zhou B., Han J., Liu G. A UD Factorization-Based Nonlinear Adaptive Set-Membership Filter for Ellipsoidal Estimation. International Journal of Robust and Nonlinear Control, 2008, vol. 18, pp. 1513-1531. DOI: 10.1002/rnc.1289
27. Daowang F., Teng L., Tao H.Z. Square-Root Second-Order Extended Kalman Filter and Its Application in Target Motion Analysis. Radar, Sonar and Navigation, 2010, vol. 4, no. 3, pp. 329-335. DOI: 10.1049/iet-rsn.2008.0070
28. Gibbs B.P. Advanced Kalman Filtering. Least-Squares and Modeling: A Practical Handbook. Hoboken, New Jersey, John Wiley and Sons, 2011.
29. Semushin I.V., Tsyganova Yu.V., Kulikova M.V. et al. Adaptivnye sistemy fil'tracii, upravleniya i obnaruzheniya [Adaptive Systems of Filtering, Control and Detection]. Ulyanovsk, UlGU, 2011. (in Russian)
30. Semushin I.V. Vychislitel'nye metody algebry i otsenivaniya. Uchebnoe posobie [Computational Methods of Algebra and Estimation]. Ulyanovsk, UlSTU Publishers, 2011. (in Russian)
31. Semushin I.V., Tsyganova Yu.V., Zakharov K.V. [Robust Filter Algorithms - Survey and New Results for Ship Navigation]. Informatsionnye tekhnologii i vychislitel'nye sistemy, 2013, no. 4, pp. 90-112. (in Russian)
32. Kulikova M.V., Taylor D.R. Stochastic Volatility Models for Exchange Rates and Their Estimation Using Quasi-Maximum-Likelihood Methods: an Application to the South African Rand. Journal of Applied Statistics, 2013, vol. 40, no. 3, pp. 495-507. DOI: 10.1080/02664763.2012.740791
33. Kulikova M.V., Tsyganova J.V., Semushin I.V. Adaptive Wave Filtering for Marine Vessels within UD-Based Algorithms. Proceedings of the ECC2016, European Control Conference, Aalborg, 2016, pp. 807-812. DOI: 10.1109/ECC.2016.7810388
34. Tsyganova Yu.V. [On the UD Filter Implementation Methods]. University Proceedings. Volga Region. Physical and Mathematical Sciences, 2013, no. 3, pp. 84-104. (in Russian)
35. Semushin I.V., Tsyganova Yu.V., Tsyganov A.V., Prokhorova E.F. Numerically Efficient UD Filter Based Channel Estimation for OFDM Wireless Communication Technology. Procedia Engineering, 2017, vol. 201, pp. 726-735. DOI: 10.1016/j.proeng.2017.09.597
36. Kulikova M.V., Tsyganova J.V. Improved Discrete-Time Kalman Filtering within Singular Value Decomposition. IET Control Theory and Applications, 2017, vol. 11, no. 5, pp. 2412-2418. DOI: 10.1049/iet-cta.2016.1282
37. Tsyganova Yu.V. Orthogonalized Block Methods for Parameter Identification of Discrete Linear Stochastic Systems: D.Sc. Thesis. Ulyanovsk, Ulyanovsk State University at Ulyanovsk, 2017.
38. Semushin I.V., Tsyganova J.V., Tsyganov A.V. Numerically Efficient LD-computations for the Auxiliary Performance Index Based Control Optimization under Uncertainties. Proceedings of the 17th IFAC Workshop on Control Applications of Optimization Yekaterinburg, Russia, October 15-19, 2018, Yekaterinburg, 2018, vol. 51, pp. 568-573.
39. D'Souza Ch., Zanetti R. Information Formulation of the UDU Kalman Filter. IEEE Transactions on Aerospace and Electronic Systems, 2018. DOI: 10.1109/TAES.2018.2850379