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

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

Oleg Rudenko, Oleksandr Bezsonov, Oleksandr Romanyk, Valentyn Lebediev

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

Keywords


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

References


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

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.

Ljung, L., Soderstrom, T. (1983). Theory and practice of recursive identification. Cambridge, MA: MIT Press, 529.

Goodwin, G. C., Sin, K. S. (1984). Adaptive filtering prediction and control. Prentice-Hall, 536.

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

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

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.

Raybman, N. S., Chadeev, V. M. (1966). Adaptivnye modeli v sistemah upravleniya. Moscow: Sovetskoe radio, 156.

Aved'jan, A. D. (1971). Bestimmung der Parameter linearer Modelle stationarer und instationarer Strecken. Messen, steuern, regeln, 9, 348–350.

Rudenko, O. G. (1982). Ocenka skorosti skhodimosti odnoshagovyh ustoychivyh algoritmov identifikacii. Doklady AN USSR. Ser. A. Fiz-mat i tekhn. nauki, 1, 64–66.

Clarkson, P. M. (1993). Optimal and Adaptive Signal Processing. CRC Press, 560.

Haykin, S. (2014). Adaptive Filter Theory. Boston: Pearson, 913.

Sayed, A. H. (2008). Adaptive Filters. New Jersey: John Wiley & Sons, 786. doi: https://doi.org/10.1002/9780470374122

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

Liberol', B. D., Rudenko, O. G., Bessonov, A. A. (2018). Issledovanie skhodimosti odnoshagovyh adaptivnyh algoritmov identifikacii. Problemy upravleniya i informatiki, 5, 19–32.

Okrug, A. I. (1981). A dynamic Kaczmarz algorithm. Avtomatika i telemekhanika, 1, 74–79.

Lelashvili, Sh. G. (1965). Primenenie odnogo iteracionnogo metoda dlya analiza mnogomernyh avtomaticheskih sistem. Skhemy avtomaticheskogo upravleniya, 19–33.

Lelashvili, Sh. G. (1967). Nekotorye voprosy postroeniya statisticheskoy modeli mnogomernyh ob'ektov. Avtomaticheskoe upravlenie, 59–96.

Avehvyan, E. D. (1978). Modified Kaczmarz algorithms for estimating the parameters of linear plants. Avtomatika i telemekhanika, 5, 64–72.

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.

Ishchenko, L. A., Liberol', B. D., Rudenko, O. G. (1986). O svoystvah odnogo klassa mnogoshagovyh adaptivnyh algoritmov identifikacii. Kibernetika, 1, 92–96.

Liberol', B. D., Rudenko, O. G. (1990). O svoystvah proekcionnyh algoritmov ocenivaniya parametrov nestacionarnyh ob'ektov. Doklady AN USSR. Ser. A, 4, 71–74.

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

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

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

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

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

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

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

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

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

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

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

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

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

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


GOST Style Citations


Dupac V. A Dynamic Stochastic Approximation Method // The Annals of Mathematical Statistics. 1965. Vol. 36, Issue 6. P. 1695–1702. doi: https://doi.org/10.1214/aoms/1177699797 

Cypkin Ya. Z., Kaplinskiy A. I., Larionov K. A. Algoritmy adaptacii i obucheniya v nestacionarnyh usloviyah // Izvestiya AN SSSR. Tekhnicheskaya kibernetika. 1970. Issue 5. P. 9–21.

Ljung L., Soderstrom T. Theory and practice of recursive identification. Cambridge, MA: MIT Press, 1983. 529 р.

Goodwin G. C., Sin K. S. Adaptive filtering prediction and control. Prentice-Hall, 1984. 536 p.

Kaczmarz S. Approximate solution of systems of linear equations // International Journal of Control. 1993. Vol. 57, Issue 6. P. 1269–1271. doi: https://doi.org/10.1080/00207179308934446 

Nagumo J., Noda A. A learning method for system identification // IEEE Transactions on Automatic Control. 1967. Vol. 12, Issue 3. P. 282–287. doi: https://doi.org/10.1109/tac.1967.1098599 

Chadeev V. M. Opredelenie dinamicheskih harakteristik ob'ektov v processe ih normal'noy ekspluatacii dlya celey samonastroyki // Avtomatika i telemekhanika. 1964. Vol. 25, Issue 9. P. 1302–1306.

Raybman N. S., Chadeev V. M. Adaptivnye modeli v sistemah upravleniya. Moscow: Sovetskoe radio, 1966. 156 p.

Aved'jan A. D. Bestimmung der Parameter linearer Modelle stationarer und instationarer Strecken // Messen, steuern, regeln. 1971. Vol. 9. P. 348–350.

Rudenko O. G. Ocenka skorosti skhodimosti odnoshagovyh ustoychivyh algoritmov identifikacii // Doklady AN USSR. Ser. A. Fiz-mat i tekhn. nauki. 1982. Issue 1. P. 64–66.

Clarkson P. M. Optimal and Adaptive Signal Processing. CRC Press, 1993. 560 p.

Haykin S. Adaptive Filter Theory. 5-th ed. Boston: Pearson, 2014. 913 p.

Sayed A. H. Adaptive Filters. New Jersey: John Wiley & Sons, 2008. 786 p. doi: https://doi.org/10.1002/9780470374122 

Adaptive Signal Processing: Application to Real-World Problems / J. Benesty, A. Huang (Eds.). Berlin: Springer-Verlag, 2003. 356 p. doi: https://doi.org/10.1007/978-3-662-11028-7 

Liberol' B. D., Rudenko O. G., Bessonov A. A. Issledovanie skhodimosti odnoshagovyh adaptivnyh algoritmov identifikacii // Problemy upravleniya i informatiki. 2018. Issue 5. P. 19–32.

Okrug A. I. A dynamic Kaczmarz algorithm // Avtomatika i telemekhanika. 1981. Issue 1. P. 74–79.

Lelashvili Sh. G. Primenenie odnogo iteracionnogo metoda dlya analiza mnogomernyh avtomaticheskih sistem // Skhemy avtomaticheskogo upravleniya. 1965. P. 19–33.

Lelashvili Sh. G. Nekotorye voprosy postroeniya statisticheskoy modeli mnogomernyh ob'ektov // Avtomaticheskoe upravlenie. 1967. P. 59–96.

Avehvyan E. D. Modified Kaczmarz algorithms for estimating the parameters of linear plants // Avtomatika i telemekhanika. 1978. Issue 5. P. 64–72.

Liberol' B. D., Rudenko O. G., Timofeev V. A. Modificirovannyy algoritm Kachmazha dlya ocenivaniya parametrov nestacionarnyh ob'ektov // Problemy upravleniya i informatiki. 1995. Issue 4. P. 81–89.

Ishchenko L. A., Liberol' B. D., Rudenko O. G. O svoystvah odnogo klassa mnogoshagovyh adaptivnyh algoritmov identifikacii // Kibernetika. 1986. Issue 1. P. 92–96.

Liberol' B. D., Rudenko O. G. O svoystvah proekcionnyh algoritmov ocenivaniya parametrov nestacionarnyh ob'ektov // Doklady AN USSR. Ser. A. 1990. Issue 4. P. 71–74.

Ciochină S., Paleologu C., Benesty J. An optimized NLMS algorithm for system identification // Signal Processin. 2016. Vol. 118. P. 115–121. doi: https://doi.org/10.1016/j.sigpro.2015.06.016 

Khong A. W. H., Naylor P. A. Selective-Tap Adaptive Filtering With Performance Analysis for Identification of Time-Varying Systems // IEEE Transactions on Audio, Speech and Language Processing. 2007. Vol. 15, Issue 5. P. 1681–1695. doi: https://doi.org/10.1109/tasl.2007.896671 

Loganathan P., Habets E. A. P., Naylor P. A. Performance analysis of IPNLMS for identification of time-varying systems // 2010 IEEE International Conference on Acoustics, Speech and Signal Processing. 2010. doi: https://doi.org/10.1109/icassp.2010.5495893 

Naylor P. A., Khong A. W. H., Brookes M. 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. 2007. doi: https://doi.org/10.1109/icassp.2007.366625 

Benesty J., Paleologu C., Ciochina S. On Regularization in Adaptive Filtering // IEEE Transactions on Audio, Speech, and Language Processing. 2011. Vol. 19, Issue 6. P. 1734–1742. doi: https://doi.org/10.1109/tasl.2010.2097251 

Wang Y., Li Y. Norm Penalized Joint-Optimization NLMS Algorithms for Broadband Sparse Adaptive Channel Estimation // Symmetry. 2017. Vol. 9, Issue 8. P. 133. doi: https://doi.org/10.3390/sym9080133 

An overview on optimized NLMS algorithms for acoustic echo cancellation / Paleologu C., Ciochină S., Benesty J., Grant S. L. // EURASIP Journal on Advances in Signal Processing. 2015. Vol. 2015, Issue 1. doi: https://doi.org/10.1186/s13634-015-0283-1 

Bershad N. J., McLaughlin S., Cowan C. F. N. Performance comparison of RLS and LMS algorithms for tracking a first order Markov communications channel // IEEE International Symposium on Circuits and Systems. 1990. doi: https://doi.org/10.1109/iscas.1990.112009 

Mandic D. P., Chambers J. A. Recurrent neural networks for prediction: learning algorithms, architectures and stability. John Wiley & Sons, 2001. 285 p. doi: https://doi.org/10.1002/047084535x 

Shin H.-C., Sayed A. H., Song W.-J. Variable Step-Size NLMS and Affine Projection Algorithms // IEEE Signal Processing Letters. 2004. Vol. 11, Issue 2. P. 132–135. doi: https://doi.org/10.1109/lsp.2003.821722 

Paleologu C., Benesty J., Ciochina S. A Variable Step-Size Affine Projection Algorithm Designed for Acoustic Echo Cancellation // IEEE Transactions on Audio, Speech, and Language Processing. 2008. Vol. 16, Issue 8. P. 1466–1478. doi: https://doi.org/10.1109/tasl.2008.2002980 

Gupta D., Gupta V. K., Chandra M. Performance Comparison of Different Affine Projection Algorithms for Noise Minimization from Speech Signals // International Journal of Future Generation Communication and Networking. 2017. Vol. 10, Issue 1. P. 261–270. doi: https://doi.org/10.14257/ijfgcn.2017.10.1.21 

A statistical analysis of the affine projection algorithm for unity step size and autoregressive inputs / De Almeida S. J. M., Bermudez J. C. M., Bershad N. J., Costa M. H. // IEEE Transactions on Circuits and Systems I: Regular Papers. 2005. Vol. 52, Issue 7. P. 1394–1405. doi: https://doi.org/10.1109/tcsi.2005.851720 

Wagner K. T., Doroslovacki M. I. Towards analytical convergence analysis of proportionate-type NLMS algorithms // 2008 IEEE International Conference on Acoustics, Speech and Signal Processing. 2008. doi: https://doi.org/10.1109/icassp.2008.4518487 







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.

ISSN (print) 1729-3774, ISSN (on-line) 1729-4061