A Novel Convergence Accelerator for the LMS Adaptive Algorithm

Authors: Jeng-Shin Sheu, Jenn-Kaie Lain, Tai-Kuo Woo, Jyh-Horng Wen

Abstract:

The least mean square (LMS) algorithmis one of the most well-known algorithms for mobile communication systems due to its implementation simplicity. However, the main limitation is its relatively slow convergence rate. In this paper, a booster using the concept of Markov chains is proposed to speed up the convergence rate of LMS algorithms. The nature of Markov chains makes it possible to exploit the past information in the updating process. Moreover, since the transition matrix has a smaller variance than that of the weight itself by the central limit theorem, the weight transition matrix converges faster than the weight itself. Accordingly, the proposed Markov-chain based booster thus has the ability to track variations in signal characteristics, and meanwhile, it can accelerate the rate of convergence for LMS algorithms. Simulation results show that the LMS algorithm can effectively increase the convergence rate and meantime further approach the Wiener solution, if the Markov-chain based booster is applied. The mean square error is also remarkably reduced, while the convergence rate is improved.

Keywords: LMS, Markov chain, convergence rate, accelerator.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1327734

References:

[1] S. Gazor, "Predictions in LMS-type adaptive algorithms for smoothly time-varying environments," IEEE Trans. Signal Process., vol. 47, no. 7, pp. 1735-1739, Jun. 1999.
[2] D. G. Manolakis, V. K. Ingle, and S. M.Kogan, Statistical and Adaptive Signal Processing. New York: McGraw-Hill Int. Editions, 2000.
[3] Haykin, S.: ÔÇÿAdaptive Filter Theory- (Prentice Hall, 1995.)
[4] V. Solo and X. Kong, Adaptive Signal Processing Algorithms: Stability and Performance. Englewood Cliffs, NJ: Prentice-Hall, 1995.
[5] Evans, J. B., Xue, P. and Liu, B.: ÔÇÿAnalysis and implementation of variable step size adaptive algorithm-, IEEE Trans. Signal Processing, 1993, vol. 41, pp. 2517-2535.
[6] Aboulnasr, T. and Mayyas, K.: ÔÇÿA robust variable step-size LMS-type algorithm: Analysis and simulations-, IEEE Trans. Signal Processing, 1997, vol. 45, pp. 631-639.
[7] Hosur, S. and Tewfik, A. H., "Wavelet transform domain LMS algorithm," Proc. ICASSP, April 1993, Minneapolis, Minnesota, USA, pp. 508-510.
[8] Erdol, N. and Basbug, F., "Performance of wavelet transform based adaptive filters-. Proc.ICASSP, April 1993, Minneapolis, Minnesota, USA, pp. 500-503.
[9] Narayan, S. S., Peterson, A. M. and Narashima, M. J., "Transform domain LMS algorithm", IEEE Trans. Acoust., Speech, Signal Processing, June. 1983, vol. 31, pp. 4609-615.
[10] Widrow, B., "Fundamental relations between the LMS algorithm and the DFT," IEEE Trans. Circuits Syst., vol. CAS-34, pp. 814-819.
[11] Von Neumann, J., Kent, R. H., Bellinson, H. R. and Habt, B. I., "The mean square successive difference,"Ann.Math. Statist. Vol. 12, 1941, pp. 153-162.
[12] Ghosh, M. and Meeden, G.: ÔÇÿOn the non-attainability of Chebychev bounds-, American Statistician, 1977, 31, pp. 35-36.