On modern array algorithms for optimal discrete filtering

Yu. V. Tsyganova ; M. V. Kulikova

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 11 (2018) no. 4, pp. 5-30

Résumé

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.

Détail

Keywords: discrete filtering, linear stochastic systems, Kalman filter, matrix orthogonal transforms, array algorithms.

Bibliographie

[1] Kalman R. E., “A New Approach to Linear Filtering and Prediction Problems”, Journal of Basic Engineering, 82:1 (1960), 35–45 | DOI

[2] Potter J. E., Stern R. G., “Statistical Filtering of Space Navigation Measurements”, AIAA Guidance, Navigation and Control Conference (Cambridge, 1963), 13 pp. | DOI

[3] Rauch H. E., Striebel C. T., Tung F., “Maximum Likelihood Estimates of Linear Dynamic Systems”, AIAA journal, 3:8 (1965), 1445–1450 | DOI | MR

[4] Dyer P., McReynolds S., “Extension of Square-Root Filtering to Include Process Noise”, Journal of Optimization Theory and Applications, 1969, no. 3, 444–459 | DOI | MR

[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, 16:6 (1971), 727–735 | DOI

[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, 19:11 (1973), 750–760 | DOI | MR | Zbl

[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, 19:4 (1974), 315–323 | DOI | MR | Zbl

[10] Morf M., Kailath T., “Square-Root Algorithms for Least-Squares Estimation”, IEEE Transactions on Automatic Control, 20:4 (1975), 487–497 | DOI | MR | Zbl

[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 pp.

[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, Academic Press, N.Y., 1977 | MR | Zbl

[14] Fomin V. N., Recurrent Estimation and Adaptive Filtering, Nauka, M., 1984 (in Russian)

[15] Verhaegen M., Van Dooren P., “Numerical Aspects of Different Kalman Filter Implementations”, IEEE Transactions on Automatic Control, 31:10 (1986), 907–917 | DOI | Zbl

[16] Jover J. M., Kailath T., “A Parallel Architecture for Kalman Filter Measurement Update and Parameter Estimation”, Automatica, 22:1 (1986), 43–57 | DOI | Zbl

[17] Ogarkov M. A., Methods of Statistical Estimation of Parameters of Random Processes, Energoatomizdat, M., 1990 (in Russian) | MR

[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, 1224–1229 | DOI | MR

[19] Sayed A. H., Kailath T., “Extended Chandrasekhar Recursions”, IEEE Transactions on Automatic Control, 9:3 (1994), 619–622 | DOI | MR

[20] Park P., Kailath T., “New Square-Root Algorithms for Kalman Filtering”, IEEE Transactions on Automatic Control, 40:5 (1995), 895–899 | DOI | MR | Zbl

[21] Golub G., Van Loan Ch., Matrix Computations, Johns Hopkins University Press, 1996 | MR | Zbl

[22] Kailath T., Sayed A. H., Hassibi B., Linear Estimation, Prentice Hall, New Jersey, 2000

[23] Grewal M. S., Andrews A. P., Kalman Filtering: Theory and Practice Using MATLAB, Prentice Hall, New Jersey, 2001 | MR

[24] Higham N. J., Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 2002 | MR | Zbl

[25] Higham N. J., “J-Orthogonal Matrices: Properties and Generalization”, SIAM Review, 45:3 (2003), 504–519 | DOI | MR | Zbl

[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, 18 (2008), 1513–1531 | DOI | MR | Zbl

[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, 4:3 (2010), 329–335 | DOI

[28] Gibbs B. P., Advanced Kalman Filtering. Least-Squares and Modeling: A Practical Handbook, John Wiley and Sons, Hoboken, New Jersey, 2011 | MR

[29] Semushin I. V., Tsyganova Yu.V., Kulikova M. V. et al., Adaptive Systems of Filtering, Control and Detection, UlGU, Ulyanovsk, 2011 (in Russian)

[30] Semushin I. V., Computational Methods of Algebra and Estimation, UlSTU Publishers, Ulyanovsk, 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, 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, 40:3 (2013), 495–507 | DOI | MR

[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), 807–812 | DOI

[34] Tsyganova Yu. V., “On the UD Filter Implementation Methods”, University Proceedings. Volga Region. Physical and Mathematical Sciences, 2013, no. 3, 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, 201 (2017), 726–735 | DOI

[36] Kulikova M. V., Tsyganova J. V., “Improved Discrete-Time Kalman Filtering within Singular Value Decomposition”, IET Control Theory and Applications, 11:5 (2017), 2412–2418 | DOI | MR

[37] Tsyganova Yu. V., Orthogonalized Block Methods for Parameter Identification of Discrete Linear Stochastic Systems, D.Sc. Thesis, Ulyanovsk State University at Ulyanovsk, 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” (Yekaterinburg, Russia, October 15–19, 2018), IFAC-PapersOnLine, 51:32, Proceedings of the 17th IFAC Workshop on Control Applications of Optimization, 568–573 | DOI

[39] D'Souza Ch., Zanetti R., “Information Formulation of the UDU Kalman Filter”, IEEE Transactions on Aerospace and Electronic Systems, 2018 | DOI