×

Local minima escape transients by stochastic gradient descent algorithms in blind adaptive equalizers. (English) Zbl 0822.93076

Summary: Many adaptive algorithms perform stochastic gradient descent on performance surfaces that are not guaranteed to be unimodal. In some examples, it is possible to show that not only is there more than one stationary point on this performance surface, but also that there is at least one incorrect local minimum. In the past, many authors have noted the existence of these incorrect stable equilibria, and noted that transitions between the regions of attraction of these local equilibria are possible. However, very little work has been done to determine the escape times, beyond observing that if the valleys surrounding these undesirable equilibria are very small and shallow, the escape time should not be too large. Here, we begin with a general discussion of the escape behaviour of adaptive algorithms, and follow this with an analysis, using diffusion approximations and large deviations theory, of the escape behaviour of the Godard class of blind equalizers. From this analysis, we obtain asymptotic estimates for the expected value of the escape time when leaving the region of attraction of local equilibria. Some observations are made also on the trajectories followed during such escapes. The basis for the computation of escape time estimates is the connection between large deviations and optimal control theory. For this interesting class of adaptive estimation problems, possessing multiple equilibria, the construction and solution of the optimal control problem is approximated, and shown to yield reasonable quantifications.

MSC:

93E99 Stochastic systems and control
93E20 Optimal stochastic control
60F10 Large deviations
Full Text: DOI

References:

[1] Benveniste, A.; Goursat, M.; Ruget, G., Robust identification of a non-minimum phase system: blind adjustment of a linear equalizer in data communications, IEEE Trans. Autom. Control, AC-25, 385-399 (1980) · Zbl 0439.93055
[2] Benveniste, A.; Metivier, M.; Priouret, P., Algorithmes Adaptatifs et Approximations Stochastiques (1987), Masson: Masson Paris · Zbl 0639.93002
[3] Bitmead, R. R.; Anderson, B. D.O.; Ng, T. S., Convergence rate determination for gradient based adaptive estimators, Automatica, 22, 185-191 (1986) · Zbl 0605.93054
[4] Bitmead, R. R.; Caines, P. E., Escape time formulation of robust stochastic control, (Narendra, K. S.; Ortega, R.; Dorato, P., Advances in Adaptive Control (1991), IEEE Press: IEEE Press New York), 197-202
[5] Cramer, H.; Leadbetter, M. R., Stationary and Related Stochastic Processes (1967), Wiley: Wiley New York · Zbl 0162.21102
[6] Ding, Z.; Kennedy, R. A.; Anderson, B. D.O.; Johnson jun, C. R., Ill-convergence of Godard blind equalizers in communications systems, IEEE Trans. Commun., COM-39, 1313-1327 (1991) · Zbl 0739.94001
[7] Frater, M. R.; Bitmead, R. R., Escape of adaptive equalizers from local equilibria, (Proc. Int. Symp. Signal Processing and Applications. Proc. Int. Symp. Signal Processing and Applications, Gold Coast, Australia (1990)), 279-282
[8] Frater, M. R.; Bitmead, R. R.; Johnson jun, C. R., Escape from stable equilibria in blind adaptive equalizers, (Proc. 31st IEEE Conf. on Decision and Control. Proc. 31st IEEE Conf. on Decision and Control, Tuscon, AZ (1992)), 1756-1761
[9] Frater, M. R.; Johnson jun, C. R., Local minima escape transients of CMA, (Proc. IEEE Conf. on Acoustics, Speech and Signal Processing, Vol. III (1994)), 37-40, Adelaide
[10] Freidlin, M. I.; Wentzell, A. D., Random Perturbations of Dynamical Systems (1984), Springer: Springer New York · Zbl 0522.60055
[11] Freund, R. B.; Williamson, G. A.; Johnson jun, C. R.; Ljung, L., Alternate realizations of an adaptive FIR filter: properties of the average squared prediction error surface, (Proc. 25th Conf. on Information Sciences and Systems. Proc. 25th Conf. on Information Sciences and Systems, Baltimore (1991)), 226-232
[12] Godard, D. N., Self-recovering equalization and carrier tracking in two-dimensional data communication systems, IEEE Trans. Commun., COM-28, 1867-1875 (1980)
[13] Iosifescu, M.; Theodorescu, R., Random Processes and Learning (1969), Springer: Springer New York · Zbl 0194.51101
[14] Johnson jun, C. R., Lectures on Adaptive Parameter Estimation (1988), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 0695.93001
[15] Loève, M., Probability Theory (1977), Springer: Springer New York · Zbl 0359.60001
[16] Mazo, J. E., Analysis of decision-directed equalizer, Bell Syst. Tech. J., 59, 1857-1876 (1980)
[17] Nayeri, M.; Fan, H.; Jenkins, W. K., Some characteristics of error surfaces for insufficient order adaptive IIR filters, IEEE Trans. Acoustics, Speech Signal Process, ASSP-38, 1222-1227 (1990)
[18] Proakis, J. G., Digital Communications (1989), McGraw-Hill: McGraw-Hill New York
[19] Treichler, J. R.; Larimore, M. G., New processing techniques based on the constant modulus adaptive algorithm, IEEE Trans. Acoustics, Speech Signal Process, ASSP-33, 421-431 (1985)
[20] Wozencraft, J. M.; Jacobs, I. M., (Principles of Communication Engineering (1965), John Wiley: John Wiley New York)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.