Analysis of convergence of adaptive single­step algorithms for the identification of non­stationary objects

Authors

DOI:

https://doi.org/10.15587/1729-4061.2019.157288

Keywords:

Markovian model, adaptive algorithm by Kaczmarz, by Nagumo-Noda, regularization, recurrent procedure optimal parameter

Abstract

The study deals with the problem of identification of non-stationary parameters of a linear object which can be described by first-order Markovian model, with the help of the simplest in computational terms single-step adaptive identification algorithms – modified algorithms by Kaczmarz and Nagumo-Noda. These algorithms do not require knowledge of information on the degree of non-stationarity of the studied object. When building the model, they use the information only about one step of measurements. Modification involves the use of the regularizing addition in the algorithms to improve their computing properties and avoid division by zero. Using a Markovian model is quite effective because it makes it possible to obtain analytic estimates of the properties of algorithms.

It was shown that the use of regularizing additions in identification algorithms, while improving stability of algorithms, leads to some slowdown of the process of model construction. The conditions for convergence of regularizing algorithms by Kaczmarz and Nagumo-Noda at the evaluation of stationary parameters in mean and root-mean-square and existing measurement interference were determined.

The obtained estimates differ from the existing ones by higher accuracy. Despite this, they are quite general and depend both on the degree of non-stationarity of an object, and on statistical characteristics of interference. In addition, the expressions for the optimal values of the parameters of algorithms, ensuring their maximum rate of convergence under conditions of non-stationarity and the presence of Gaussian interferences, were determined. The obtained analytical expressions contain a series of unknown parameters (estimation error, degree of non-stationarity of an object, statistical characteristics of interferences). For their practical application, it is necessary to use any recurrent procedure for estimation of these unknown parameters and apply the obtained estimates to refine the parameters that are included in the algorithms

Author Biographies

Oleg Rudenko, Simon Kuznets Kharkiv National University of Economics Nauky ave., 9-A, Kharkiv, Ukraine, 61166

Doctor of Technical Sciences, Professor, Head of Department

Department of Information Systems

Oleksandr Bezsonov, Simon Kuznets Kharkiv National University of Economics Nauky ave., 9-A, Kharkiv, Ukraine, 61166

Doctor of Technical Sciences, Associate Professor

Department of Information Systems

Oleksandr Romanyk, Kharkiv National University of Radio Electronics Nauky ave., 14, Kharkіv, Ukraine, 61166

Postgraduate student

Department of Electronic Computers

Valentyn Lebediev, Kharkiv National University of Radio Electronics Nauky ave., 14, Kharkіv, Ukraine, 61166

Department of Electronic Computers

References

  1. Dupac, V. (1965). A Dynamic Stochastic Approximation Method. The Annals of Mathematical Statistics, 36 (6), 1695–1702. doi: https://doi.org/10.1214/aoms/1177699797
  2. Cypkin, Ya. Z., Kaplinskiy, A. I., Larionov, K. A. (1970). Algoritmy adaptacii i obucheniya v nestacionarnyh usloviyah. Izvestiya AN SSSR. Tekhnicheskaya kibernetika, 5, 9–21.
  3. Ljung, L., Soderstrom, T. (1983). Theory and practice of recursive identification. Cambridge, MA: MIT Press, 529.
  4. Goodwin, G. C., Sin, K. S. (1984). Adaptive filtering prediction and control. Prentice-Hall, 536.
  5. Kaczmarz, S. (1993). Approximate solution of systems of linear equations. International Journal of Control, 57 (6), 1269–1271. doi: https://doi.org/10.1080/00207179308934446
  6. Nagumo, J., Noda, A. (1967). A learning method for system identification. IEEE Transactions on Automatic Control, 12 (3), 282–287. doi: https://doi.org/10.1109/tac.1967.1098599
  7. Chadeev, V. M. (1964). Opredelenie dinamicheskih harakteristik ob'ektov v processe ih normal'noy ekspluatacii dlya celey samonastroyki. Avtomatika i telemekhanika, 25 (9), 1302–1306.
  8. Raybman, N. S., Chadeev, V. M. (1966). Adaptivnye modeli v sistemah upravleniya. Moscow: Sovetskoe radio, 156.
  9. Aved'jan, A. D. (1971). Bestimmung der Parameter linearer Modelle stationarer und instationarer Strecken. Messen, steuern, regeln, 9, 348–350.
  10. Rudenko, O. G. (1982). Ocenka skorosti skhodimosti odnoshagovyh ustoychivyh algoritmov identifikacii. Doklady AN USSR. Ser. A. Fiz-mat i tekhn. nauki, 1, 64–66.
  11. Clarkson, P. M. (1993). Optimal and Adaptive Signal Processing. CRC Press, 560.
  12. Haykin, S. (2014). Adaptive Filter Theory. Boston: Pearson, 913.
  13. Sayed, A. H. (2008). Adaptive Filters. New Jersey: John Wiley & Sons, 786. doi: https://doi.org/10.1002/9780470374122
  14. Benesty, J., Huang, A. (Eds.) (2003). Adaptive Signal Processing: Application to Real-World Problems. Berlin: Springer-Verlag, 356. doi: https://doi.org/10.1007/978-3-662-11028-7
  15. Liberol', B. D., Rudenko, O. G., Bessonov, A. A. (2018). Issledovanie skhodimosti odnoshagovyh adaptivnyh algoritmov identifikacii. Problemy upravleniya i informatiki, 5, 19–32.
  16. Okrug, A. I. (1981). A dynamic Kaczmarz algorithm. Avtomatika i telemekhanika, 1, 74–79.
  17. Lelashvili, Sh. G. (1965). Primenenie odnogo iteracionnogo metoda dlya analiza mnogomernyh avtomaticheskih sistem. Skhemy avtomaticheskogo upravleniya, 19–33.
  18. Lelashvili, Sh. G. (1967). Nekotorye voprosy postroeniya statisticheskoy modeli mnogomernyh ob'ektov. Avtomaticheskoe upravlenie, 59–96.
  19. Avehvyan, E. D. (1978). Modified Kaczmarz algorithms for estimating the parameters of linear plants. Avtomatika i telemekhanika, 5, 64–72.
  20. Liberol', B. D., Rudenko, O. G., Timofeev, V. A. (1995). Modificirovannyy algoritm Kachmazha dlya ocenivaniya parametrov nestacionarnyh ob'ektov. Problemy upravleniya i informatiki, 4, 81–89.
  21. Ishchenko, L. A., Liberol', B. D., Rudenko, O. G. (1986). O svoystvah odnogo klassa mnogoshagovyh adaptivnyh algoritmov identifikacii. Kibernetika, 1, 92–96.
  22. Liberol', B. D., Rudenko, O. G. (1990). O svoystvah proekcionnyh algoritmov ocenivaniya parametrov nestacionarnyh ob'ektov. Doklady AN USSR. Ser. A, 4, 71–74.
  23. Ciochină, S., Paleologu, C., Benesty, J. (2016). An optimized NLMS algorithm for system identification. Signal Processing, 118, 115–121. doi: https://doi.org/10.1016/j.sigpro.2015.06.016
  24. Khong, A. W. H., Naylor, P. A. (2007). Selective-Tap Adaptive Filtering With Performance Analysis for Identification of Time-Varying Systems. IEEE Transactions on Audio, Speech and Language Processing, 15 (5), 1681–1695. doi: https://doi.org/10.1109/tasl.2007.896671
  25. Loganathan, P., Habets, E. A. P., Naylor, P. A. (2010). Performance analysis of IPNLMS for identification of time-varying systems. 2010 IEEE International Conference on Acoustics, Speech and Signal Processing. doi: https://doi.org/10.1109/icassp.2010.5495893
  26. Naylor, P. A., Khong, A. W. H., Brookes, M. (2007). Misalignment Performance of Selective Tap Adaptive Algorithms for System Identification of Time-Varying Unknown Systems. 2007 IEEE International Conference on Acoustics, Speech and Signal Processing – ICASSP ’07. doi: https://doi.org/10.1109/icassp.2007.366625
  27. Benesty, J., Paleologu, C., Ciochina, S. (2011). On Regularization in Adaptive Filtering. IEEE Transactions on Audio, Speech, and Language Processing, 19 (6), 1734–1742. doi: https://doi.org/10.1109/tasl.2010.2097251
  28. Wang, Y., Li, Y. (2017). Norm Penalized Joint-Optimization NLMS Algorithms for Broadband Sparse Adaptive Channel Estimation. Symmetry, 9 (8), 133. doi: https://doi.org/10.3390/sym9080133
  29. Paleologu, C., Ciochină, S., Benesty, J., Grant, S. L. (2015). An overview on optimized NLMS algorithms for acoustic echo cancellation. EURASIP Journal on Advances in Signal Processing, 2015 (1). doi: https://doi.org/10.1186/s13634-015-0283-1
  30. Bershad, N. J., McLaughlin, S., Cowan, C. F. N. (1990). Performance comparison of RLS and LMS algorithms for tracking a first order Markov communications channel. IEEE International Symposium on Circuits and Systems. doi: https://doi.org/10.1109/iscas.1990.112009
  31. Mandic, D. P., Chambers, J. A. (2001). Recurrent neural networks for prediction: learning algorithms, architectures and stability. John Wiley & Sons, 285. doi: https://doi.org/10.1002/047084535x
  32. Shin, H.-C., Sayed, A. H., Song, W.-J. (2004). Variable Step-Size NLMS and Affine Projection Algorithms. IEEE Signal Processing Letters, 11 (2), 132–135. doi: https://doi.org/10.1109/lsp.2003.821722
  33. Paleologu, C., Benesty, J., Ciochina, S. (2008). A Variable Step-Size Affine Projection Algorithm Designed for Acoustic Echo Cancellation. IEEE Transactions on Audio, Speech, and Language Processing, 16 (8), 1466–1478. doi: https://doi.org/10.1109/tasl.2008.2002980
  34. Gupta, D., Gupta, V. K., Chandra, M. (2017). Performance Comparison of Different Affine Projection Algorithms for Noise Minimization from Speech Signals. International Journal of Future Generation Communication and Networking, 10 (1), 261–270. doi: https://doi.org/10.14257/ijfgcn.2017.10.1.21
  35. De Almeida, S. J. M., Bermudez, J. C. M., Bershad, N. J., Costa, M. H. (2005). A statistical analysis of the affine projection algorithm for unity step size and autoregressive inputs. IEEE Transactions on Circuits and Systems I: Regular Papers, 52 (7), 1394–1405. doi: https://doi.org/10.1109/tcsi.2005.851720
  36. Wagner, K. T., Doroslovacki, M. I. (2008). Towards analytical convergence analysis of proportionate-type NLMS algorithms. 2008 IEEE International Conference on Acoustics, Speech and Signal Processing. doi: https://doi.org/10.1109/icassp.2008.4518487

Downloads

Published

2019-02-21

How to Cite

Rudenko, O., Bezsonov, O., Romanyk, O., & Lebediev, V. (2019). Analysis of convergence of adaptive single­step algorithms for the identification of non­stationary objects. Eastern-European Journal of Enterprise Technologies, 1(4), 6–14. https://doi.org/10.15587/1729-4061.2019.157288

Issue

Vol. 1 No. 4 (2019): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2019 Oleg Rudenko, Oleksandr Bezsonov, Oleksandr Romanyk, Valentyn Lebediev

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.