3
$\begingroup$

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?

Thanks for your time guys!!

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
```
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter K. Jan 14 at 20:22
  • $\begingroup$ 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? $\endgroup$ – robert bristow-johnson Jan 15 at 8:06
  • $\begingroup$ Robert I have included the pseudocode above. $\endgroup$ – k_gelloch Jan 15 at 10:21
  • $\begingroup$ 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? $\endgroup$ – robert bristow-johnson Jan 15 at 19:25
  • $\begingroup$ 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. $\endgroup$ – k_gelloch Jan 15 at 22:45
2
$\begingroup$
  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.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ – k_gelloch Jan 15 at 14:14
  • $\begingroup$ LMS is basically Stochastic Gradient Descent, nothing more or nothing less. For smaller values you probably have to make much more iterations. $\endgroup$ – Royi Jan 15 at 14:23
  • $\begingroup$ 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. $\endgroup$ – k_gelloch Jan 15 at 14:55
  • $\begingroup$ 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. $\endgroup$ – Royi Jan 15 at 15:00
  • $\begingroup$ 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 $\endgroup$ – k_gelloch Jan 15 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.