Re: LMS Question on step size

On May 27, 2:49 pm, HardySpicer <gyansor...@xxxxxxxxx> wrote:
On May 28, 5:13 am, maury...@xxxxxxxx wrote:





On May 25, 2:05 pm, HardySpicer <gyansor...@xxxxxxxxx> wrote:

There are two conditions for convergence of LMS: Convergence in the
mean and mean-square.Both give a solution for the step size (ie the
maximum)

It appears that neither one of them actually works with any degree of
accuracy. I am then told that the latter expressions is more accurate
than the first. However, if this is the case then the first one must
be wrong! So what's this all about? I suspect that the assumptions on
independence of certain vectors is too simplistic but does anybody
have any more spin on this? Convergence in the mean of the error
vector gives us that that the step size must be less than the
reciprocal of the largest eigenvalue of the covariance matrix. Even
for white noise stationary input (where mu would have to be less than
1 for stability) this doesn't work at all and ditto for the mean-
square convergence where ,many authors add empirical scaling factors
of 0.1 etc

Hardy

As far as I'm concerned, you have opened a big can of worms.  Text
books say this is a well understood problem, but I don't necessarily
agree.  First, I believe there are two conditions of concern, the
condition for convergence and the condition for stability.  They may
not be equal.  First, let's talk about convergence in the mean vs.
mean squared.  The LMS algorithm is derived by minimizing the mean of
the squared error.  The question I have then is why study the
convergence in the mean?  (This is an exercise, by the way.  Look it
up).  Typically, the convergence is studied by looking at the behavior
of the algorithm in the squared error (mean squared) sense.  What must
be remembered is that the LMS/NLMS minimizes ONLY the mean squared
error.  It says NOTHING of the coefficient error.  You can minimize
the squared error and still be no where near a solution that is good
(i.e., non-linear vs. linear systems.  There has been some interesting
research into the Volterra kernel for non-linear systems.  I
personally wonder if principal component analysis can be used to
derive the Volterra kernel using input and output signals alone).  In
my opinion, studying the behavior of the convergence of the
coefficients is an interesting, and maybe necessary task, but says
nothing about the behavior of the convergence or stability of the LMS
algorithm itself.  The stability is based on the squared error.

Traditionally, the condition for convergence is given as an upper
bound on the update gain factor.  The upper bound may be a good one,
but may be so small as to be useless.  What happen with early LMS
study, however, was a step in the other direction.  The upper bound
using the maximum eigenvalue of the input correlation matrix was too
large.  This caused instability in some cases.  It was then found that
the variance of the input played a big role in the stability of the
algorithm, not just the eiganvalue.  This upper bound led to the NLMS
algorithm.  The upper bound here was determined to be 2/3 * tr(R), or
two-thirds the trace of the input correlation matrix.  This upper
bound works, but is itself too small in some cases.  In an attempt to
generalize the bound somewhat, I started looking at what can be done,
rather than what must not be done.  It turns out that some
configurations can use a gain much larger than the accepted.

Don't confuse the upper bound for the LMS with the upper bound for the
NLMS.  They are different.  The upper bound of 1 is for the NLMS, not
the LMS.  This has become the accepted upper bound.  This is what is
taught in all adaptive books and articles I have seen so far.  I say
this is not true in all cases (see IEEE Signal Processing Magazine,
May 2009).  The gain can be much larger than 1.  BTW, this bound is
said to be 1 if derived using 1/2*GRAD(error^2).  It is 2 if derived
using GRAD(error^2).  An upper bound of 1 for the NLMS will give a
stable algorithm that converges (usually).  It does not mean a larger
value can't be used.

The bottom line is that the reason the convergence/stability bounds
are inaccuarate is that we have not yet figured out how to get a tight
bound.  In other words, an upper bound is not necessarily the best
upper bound, i.e it may not be the minimum upper bound.

As for stability, you can have the algorithm be unstable yet
converge.  For example, the NLMS algorithm can CONVERGENCE to the
coefficients of an unstable system, and yet be UNSTABLE itself.  And,
since the system being modeled is unstable, the guarranteed stable
gain of 1 is too large.  This is, admittedly, a special case.

Although it is presented as such, the upper bounds for LMS and NLMS
are not very general, in my opinion.

I hope this helps in some way.  I'm curious, what are you studing, and
where?

Any one else what to chime in?  This could lead to something very
interesting. I think this is an area that needs more study.

Maurice Givens

Hi Maurice

some very good points there and as usual the books seem to just copy
from other books!
I think the point about LMS minimizing mse is the best point and so
convergence in the mean is a bit of a red herring.

regards

Hardy- Hide quoted text -

- Show quoted text -

OK. But, why study convergence in the mean. There is a difference
between convergence in the mean and convergence in the mean square.
They look at two different thinfgs. I would suggest looking at
Haykin's Adaptive Filter Theory book.


Maurice Givens
.

Loading