# LMS convergence and step size $\mu$

I am running the LMS algorithm based on Haykin's Adaptive filter theory. I aim to plot the cost function $$\mathbf{J}$$ and calculate $$\mathbf{J}_{\tt min}$$ and the simulation excess mean square error $$\mathbf{J}_{\tt x}$$.

I have two questions:

1. Based on theory, LMS converges when $$0 \lt \mu \lt \frac{2}{\lambda_{\tt max}}$$. But this is not the case here since while I have calculated theoretical $$\mu=0.0019$$, the algorithm converges when $$\mu$$ is about $$0.28$$!!

2. Is this the proper way to calculate the simulation excess mean square error $$\mathbf{J}_{\tt x}$$?

Could you help me find the mistake, either in my code or in theory?

clear all
clc
close all

sysorder = 3;
ap1 = 1.2;
ap2 = 0.53;
h=[1; ap1; ap2];

N = 1000;
N1 = 60;

lmw2 = zeros(1,N1);
lmw3 = zeros(1,N1);
lmw4 = zeros(1,N1);

x=randn(N,1);
corr_xx=xcorr(x);
for i=0:2
for j=0:2
R_xx(i+1,j+1)= corr_xx(N+i-j);
end
end

d=conv(x,h);

[R_dd,lags]=xcorr(d,1);
corr_xd = xcorr(d,x);
for i=0:2
R_dx(i+1) = corr_xd(N+i);
end

mu_max = 2/eigs(R_xx,1);%__________________________________________________mu step
%mu_max = 2/trace(R_xx);
mu = 0.1*mu_max;
%mu = 0.28;
%__________________________________________________________________________

[Jx,lmw,lme]=lm_s(x,d,N,N1,mu);

lm_mse = lme(1,sysorder:N).^2;%____________________________________________LMS MSE
Jmin = min(lme(1,sysorder:N).^2);%_________________________________________Jmin
Jx = mean(Jx);%____________________________________________________________Jexcess

figure(1)
plot(h, 'ko');
hold on
plot(lmw(:,N1), 'r*');

figure(2)
plot([sysorder-1:N1-1],lm_mse(sysorder:N1),'-','color','r');grid on;

%__________________________________________________________________________

function [Jx,wf,e]=lm_s(x,d,N,N1,mu)%______________________________________LMS algorithm
sysorder = 3;
w = zeros ( sysorder, 1 );
wf = zeros(length(w),N);

for n = sysorder : N1
u = x(n:-1:n-sysorder+1);
y(n)= w' * u;
e(n) = d(n) - y(n);
w = w + mu * u * e(n) ;
wf(:,n) = w;
end

for n =  N1+1 : N
u = x(n:-1:n-sysorder+1) ;
y(n) = w' * u ;
e(n) = d(n) - y(n) ;
Jx(n) = w'*(u*u')*w;
end
end

LMS pseudocode:

Intitialization:
w [0] = 0

Computation:
for n = 0, 1, 2, 3, . . .
1. y[n] = wT[n]x[n].
2. e[n] = d[n] - y[n].
3. w[n + 1] = w[n] + µe[n]x[n].
end
$$$$

• Haykin, 4th edition (p238, Table 5.1) suggests that the upper limit is $\frac{2}{M S_{\tt max}}$ where $M$ is the filter length and $S_{\tt max}$ is the maximum value of the power spectral density of the input. But that doesn't seem to help for your example.
– Peter K.
Jan 14 at 20:22
• i dunno if i can decode the code. can you state the LMS equation in $\LaTeX$? something like $$y[n] = \sum\limits_{m=0}^{M} h_m[n] x[n-m]$$ $$e[n] = y[n] - d[n]$$ $$h_m[n+1] = h_m[n] - \mu e[n] x[n-m]$$ is $\mu$ that? Jan 15 at 8:06
• Robert I have included the pseudocode above. Jan 15 at 10:21
• I presume that the FIR tap coefficients are w[n] and it's a vector and wT[n] is the transpose of the vector and wT[n]x[n] is the dot product and w[n + 1] = w[n] + µe[n]x[n] is a vector equation, right? but e[n]` is a scaler, not a vector, right? Jan 15 at 19:25
• That's right! During the for loop, the number of elements of w[n] (tap coefficients) equal the rank of the filter's transfer function, that is 3. Jan 15 at 22:45

1. In that range it is guaranteed to converge. It doesn't mean it will necesseraly won't converge for higher values. If you want deeper understanding you can read about the step size in Convex Optimization context where there the step size related to the Lipschitz Constant of the function (Which matches the eigen value for Quadratic functions).

2. If you share the problem itself from the book, we'll be able to solve the problem.

• What puzzles me is that it doesn't converge for the guaranteed range, but only for higher values. If you try the exact same signals using steepest descent, it does converge only in the expected range but not for higher values. Jan 15 at 14:14
• LMS is basically Stochastic Gradient Descent, nothing more or nothing less. For smaller values you probably have to make much more iterations.
– Royi
Jan 15 at 14:23
• Thank you Royi! But in the above example isn't there any theoretical way to determine the optimal range? It converges to zero within the first 40 iterations. Also, according to Hayes, the optimal range for steepest descent and LMS is the same. Jan 15 at 14:55
• Of course it is the same. This is what I wrote above. LMS is stochastic gradient descent. Hence all the properties of any Stochastic Gradient Descent applies to it. The range is where convergence is guaranteed, it doesn't mean ti won't converge for higher values.
– Royi
Jan 15 at 15:00
• In the above code this range is (0,mu_max) which is about (0,0.0019). The problem is that there is no converge there! You can try it yourself for various values Jan 15 at 15:05