Behavior of Algorithms

This book chapter summarizes the three major ways that people analyze adaptive algorithms (the expected value, deterministic averaging, and ODE approaches), and contains applications in several signal processing areas.

W. A. Sethares, The LMS Family, in Efficient System Identification and Signal Processing Algorithms, Ed. N. Kalouptsidis and S. Theodoridis, Springer-Verlag, 1993.

First demonstration of global instability of LMS under lack of excitation. Introduces notion of partitioning input space into persistent, nonpersistent subspaces. Approach has been utilized in S. Haykin's recent revisions of Adaptive Filter Theory.

W. A. Sethares, D. A. Lawrence, C. R. Johnson, Jr., R. R. Bitmead, "Parameter Drift in LMS Adaptive Filters," IEEE Trans. on Acoustics, Speech, and Signal Processing, Vol. ASSP-34, No. 4, pp. 868-879, Aug. 1986.

D. A. Lawrence, W. A. Sethares and W. Ren, "Parameter drift instability in adaptive feedback systems," IEEE Trans. on Automatic Control, Vol. 38, No. 4, April 1993.

A generic counterexample to stability of all LMS variants with nonlinearities applied to regressor is given in

W. A. Sethares, "Adaptive algorithms with nonlinear data and error functions," IEEE Trans. on Signal Processing, Vol. 40, No. 9, pp. 2199-2206, Sept. 1992.

Conditions under which sign-regressor LMS algorithm will diverge. Lays to rest a long standing discussion in the literature regarding sign LMS. Use of deterministic averaging theory.

W. A. Sethares, I. M. Y. Mareels, B. D. O. Anderson, C. R. Johnson, Jr., "Excitation Conditions for Sign-Regressor LMS," IEEE Trans. on Circuits and Systems, Vol. 35, No. 6, pp. 613-624, June 1988.

J. A. Bucklew, T. Kurtz and W. A. Sethares, "Weak convergence and local stability properties of fixed stepsize recursive algorithms," IEEE Trans. on Information Theory, Vol. 39, No. 3, May 1993.

To get to my homepage, click here.