
Subsections
The LMS (least mean squares) algorithm is an approximation of the
steepest descent algorithm which uses an instantaneous estimate of
the gradient vector of a cost function. The estimate of the
gradient is based on sample values of the tapinput vector and an
error signal. The algorithm iterates over each coefficient in the
filter, moving it in the direction of the approximated
gradient [1].
For the LMS algorithm it is necessary to have a reference signal
representing the
desired filter output. The difference between the reference signal
and the actual output of the transversal filter (eq. 2) is the error signal

(3)

A schematic of the learning setup is depicted in fig. 2.
Figure 2: Adaptive
transversal filter learning

The task of the LMS algorithm is to find a set of filter
coefficients
that
minimize the expected value of the quadratic error signal, i.e., to
achieve the least mean squared error (thus the name). The squared
error and its expected value are (for simplicity of notation and
perception we drop the dependence of all variables on time
in
eqs. 4 to 7)

(4)

Note, that the squared error is a quadratic function of the coefficient
vector
, and thus
has only one (global) minimum (and no other (local) minima), that
theoretically could be found if the correct expected values in
eq. 5 were known.
The gradient descent approach demands that the position on the
error surface according to the current coefficients should be moved
into the direction of the `steepest descent', i.e., in the
direction of the negative gradient of the cost
function
with respect to the coefficient vector^{2}

(6)

The expected values in this equation,
, the
crosscorrelation vector between the desired output signal and the
tapinput vector, and
,
the autocorrelation matrix of the tapinput vector, would usually
be estimated using a large number of samples from and
. In the
LMS algorithm, however, a very shortterm estimate is used by only
taking into account the current samples:
,
and
,
leading to an update equation for the filter coefficients
Here, we introduced the `stepsize' parameter , which controls the distance we
move along the error surface. In the LMS algorithm the update of
the coefficients, eq. 7, is
performed at every time instant ,

(8)

The `stepsize' parameter introduced in eq. 7 and 8
controls how far we move along the error function surface at each
update step.
certainly has to be chosen (otherwise we would move the coefficient
vector in a direction towards larger squared error). Also,
should not be too
large, since in the LMS algorithm we use a local approximation of
and
in the
computation of the gradient of the cost function, and thus the cost
function at each time instant may differ from an accurate global
cost function.
Furthermore, too large a stepsize causes the LMS algorithm to
be instable, i.e., the coefficients do not converge to fixed values
but oscillate. Closer analysis [1]
reveals, that the upper bound for for stable behavior of the LMS algorithm depends
on the largest eigenvalue
max of the
tapinput autocorrelation matrix
and thus
on the input signal. For stable adaptation behavior the stepsize
has to be

(9)

Since we still do not want to compute an estimate of
and its
eigenvalues, we first approximate
max (
is the trace of matrix
, i.e., the
sum of the elements on its diagonal), and then  in the same way as
we approximated the expected values in the cost function 
,
the tapinput power at the current time . Hence, the upper bound for
for stable
behavior depends on the signal power^{3}.
Summary of the LMS algorithm
 Filter operation:
 Error calculation:
where is the desired
output
 Coefficient adaptation:
