4.10 The lms adaptive filter algorithm

Recall the Weiner filter problem

Find $W$ minimizing $({}_k^2)$ $${}_k=d_k-y_k=d_k-\sum_{i=0}^{M-1} w_i{x}_{k-i}=d_k-X^k^T{W}^k$$ $$X^k=\begin{pmatrix}{x}_k\\ x_{k-1}\\ \\ x_{k-M+1}\\ \end{pmatrix}$$ $$W^k=\begin{pmatrix}{w}_0^k\\ w_1^k\\ \\ w_{M-1}^k\\ \end{pmatrix}$$ The superscript denotes absolute time, and the subscript denotes time or a vector index.

the solution can be found by setting the gradient $0$

To find the (approximate) Wiener filter, some approximations are necessary. As always, the key is to make the right approximations!

The LMS algorithm is often called a stochastic gradient algorithm, since $({}^k)$ is a noisy gradient. This is by far the most commonly used adaptive filtering algorithm, because

• it was the first
• it is very simple
• in practice it works well (except that sometimes it converges slowly)
• it requires relatively litle computation
• it updates the tap weights every sample, so it continually adapts the filter
• it tracks slow changes in the signal statistics well

Computational cost of lms

So the LMS algorithm is $O(M)$ per sample. In fact, it is nicely balanced in that the filter computation and the adaptation require the sameamount of computation.

Note that the parameter $$ plays a very important role in the LMS algorithm. It can also be varied with time, but usually a constant $$ ("convergence weight facor") is used, chosen after experimentation for a givenapplication.

Tradeoffs

large $$ : fast convergence, fast adaptivity

small $$ : accurate $W$ less misadjustment error, stability