Editing Adaptive filter (section)

===LMS algorithm===
{{Main|Least mean squares filter}}
If the variable filter has a tapped delay line FIR structure, then the LMS update algorithm is especially simple. Typically, after each sample, the coefficients of the FIR filter are adjusted as follows:<ref>Widrow p. 100</ref>

: for <math> l = 0 \dots L </math>

:<math> w_{l,k+1} = w_{lk} + 2 \mu \ \epsilon_k \ x_{k-l}    </math>  
:::μ is called the ''convergence factor''.

The LMS algorithm does not require that the X values have any particular relationship; therefore it can be used to adapt a linear combiner as well as an FIR filter.  In this case the update formula is written as:

:<math> w_{l,k+1} = w_{lk} + 2 \mu \ \epsilon_k \ x_{lk}    </math>

The effect of the LMS algorithm is at each time, k, to make a small change in each weight. The direction of the change is such that it would decrease the error if it had been applied at time k.  The magnitude of the change in each weight depends on μ, the associated X value and the error at time k.  The weights making the largest contribution to the output, <math> y_k </math>, are changed the most.  If the error is zero, then there should be no change in the weights.  If the associated value of X is zero, then changing the weight makes no difference, so it is not changed.

====Convergence====

μ controls how fast and how well the algorithm converges to the optimum filter coefficients.  If μ is too large, the algorithm will not converge. If μ is too small the algorithm converges slowly and may not be able to track changing conditions.  If μ is large but not too large to prevent convergence, the algorithm reaches steady state rapidly but continuously overshoots the optimum weight vector.  Sometimes, μ is made large at first for rapid convergence and then decreased to minimize overshoot.

Widrow and Stearns state in 1985 that they have no knowledge of a proof that the LMS algorithm will converge in all cases.<ref name="Widrow p 103">Widrow p 103</ref>

However under certain assumptions about stationarity and independence it can be shown that the algorithm will converge if

:<math> 0 < \mu < \frac {1} {\sigma^2} </math>

::where 
:::<math>\sigma^2 = \sum_{l=0}^L \sigma_l^2  </math> = sum of all input power

:::<math>\sigma_l</math> is the [[Root mean square|RMS]] value of the <math>l </math>'th input

In the case of the tapped delay line filter, each input has the same RMS value because they are simply the same values delayed.  In this case the total power is
:<math> \sigma^2 = (L+1) \sigma_0^2 </math>

::where 
:::<math>\sigma_0</math> is the RMS value of <math>x_k</math>, the input stream.<ref name="Widrow p 103"/>

This leads to a normalized LMS algorithm:

:<math> w_{l,k+1} = w_{lk} + \left ( \frac { 2 \mu_{\sigma} } {\sigma^2} \right )  \epsilon_k \ x_{k-l}    </math> in which case the convergence criteria becomes: <math> 0 < \mu_{\sigma} < 1 </math>.