Excursions of Adaptive Algorithms via
the Poisson Clumping Heuristic

by William A. Sethares and James A. Bucklew

This paper details the application of the Poisson Clumping Heuristic to the Least Mean Square adaptive algorithm and its signed variants. Under mild conditions on the input and disturbance statistics, the parameter estimate errors form a Markov process. The PCH asserts that large excursions of the parameter estimates occur in clumps, and that these clumps are distributed in a Poisson manner with parameter l(b). Expressions are derived for each of the four algorithms in the scalar case, which allow calculation of l(b) in a relatively straightforward manner, and these values are compared to simulations of the algorithms. Given that the results are only asymptotic in b, the close agreement between these values is striking, even for very modest b. The four algorithms are then compared in terms of l(b). Some observations are made regarding the relative performance of the four variants, and no single LMS variant always outperforms the others. Suggestions are made as to how this technique might be applied in the vector case, and the crucial "monotonicity property" is verified.

This analysis of adaptive algorithms first appeared in the IEEE Transactions on Signal Processing, in June 1992.

To get to my homepage, click here.