Department of Information Technology

Global convergence of blind adaptation algorithms

The ill-convergence problem of blind adaptation was highlighted by Professor R. Johnsson in the mid 90´s. This problem is concerned with the fact that blind adaptation schemes do not converge to a unique convergence point for channels described by a few (finite number) of dynamic modes, despite the fact that there are numerous results on global convergence of such algorithms. The problem was found to be that the majority of the convergence proofs relied on channel models with infinitely many parameters.

The research presented in 1 and 2 exploits the fact that many blind adaptation algorithms can be cast in the form of Wiener models, where the linear dynamics is followed by a static nonlinearity. This is e.g. true for the constant modulus algorithms that are treated in 1 and 2. Tools for analysis of the convergence properties of finite dimensional Wiener models where developed and presented in 3. These tools were observed to be directly applicable to convergence analysis of many blind adaptation schemes. The convergence analysis tools are based on nonlinear stability analysis of averaged associated differential equations, using results from Lyapunov stability theory.

The papers 1 and 2

  • revert the design process of the blind adaptation schemes by first defining a general parameter updating rule. Then a Lypunov function candidate is postulated and the updating rule is selected in order to make the derivative of the Lyapunov function non-positive. The result is an associated ODE that is globally stable. The associated blind adaptation algorithm is hence globally convergent.
  • use linearization together with a limiting procedure to secure also local convergence to the true parameter vector.

The resulting algorithm appear to introduce chaos in the adaptation, the effect of this chaos

  • providing sufficient self-excitation of the algorithm to result in global convergence.
  • avoiding convergence to a zero channel setting.

Convergence is established by the use of an adaptation gain that tends to zero as time increases.

An extensive simulation study was performed in 2. This study first used the ill-convergence example of Professor Johnsson's work. It was shown that the ill-convergence does not appear for the algorithm of 2. A larger example was also simulated, using the true parameters -1.3435 and 0.9025. The result of the simulations are displayed in Table 1, using a variety of initial values. The results support the analysis of 2 and indicate that the simulated scheme is indeed globally convergent. The convergence of the parameters are displayed in Figure 1.

Fig13.jpg

Table 1: Parameter convergence of one of the globally convergent algorithms for finite dimensional blind adaptation. The initial values appear at the left and the convergence points at the right.

Note that the results are valid for IIR channels. The algorithm appears to converge slowly and is therefore believed to be mainly of theoretical interest.

Fig12.jpg

Figure 1: Parameter convergence of one of the globally convergent algorithms for finite dimensional blind adaptation.

References

1. T. Wigren, ODE analysis and redesign in blind adaptation, IEEE Trans. Automat. Contr. , vol. 42, no. 12, pp. 1742-1747, 1997.

2. T. Wigren, Avoiding ill-convergence of finite dimensional blind adaptation schemes excited by discrete symbol sequences, Signal Processing, vol. 62, no. 2, pp. 121-162, 1997

3. T. Wigren, Convergence analysis of recursive identification algorithms based on the nonlinear Wiener model, IEEE Trans. Automat. Contr., vol. AC-39, no. 11, pp. 2191-2206, 1994.

Updated  2007-02-01 07:44:20 by Torbjörn Wigren.