1 asptarlmsnewt

Purpose

Efficient implementation of the LMS-Newton algorithm using autoregressive modeling.

Syntax

[k,w,b,u,P,y,e]=asptarlmsnewt(k,w,x,b,u,P,d,mu_p,mu_w,maxk)

Description

The LMS-Newton is a stochastic implementation of the Newton search method which solves the eigenvalue spread problem in adaptive filters with colored input signals. The update equation for the LMS-Newton is given by (see Fig. 2.5 and Fig. 2.6)

$$\vw (n+1) = \vw (n) + 2 \mu \; e(n) \mR ^{-1} \; \vx (n),$$ (27)

where $\mR$ is the autocorrelation matrix of the adaptive filter input signal $x(n)$. Direct implementation of the LMS-Newton update (4.1) requires estimation and inversion of $\mR$ and the matrix vector multiplication $\mR ^{-1} \; \vx (n)$ each sample, which is of course very computational demanding. asptarlmsnewt() implements the LMS-Newton method efficiently by recursively estimating the term $u=\mR ^{-1} \; \vx (n)$ using autoregressive modeling. A lattice predictor of $M$ stages is used for the autoregressive modeling part. When the input signal can be modeled with an autoregressive model of length $M$ much less than the adaptive filter length $L$, a significant computational saving is obtained. The input and output parameters of asptarlmsnewt() of $M$ lattice predictor stages and $L$ transversal filter coefficients are summarized below.

Input Parameters [Size]:: 
    k   : vector of lattice predictor coefficients [Mx1]
    w   : vector of linear combiner coefficients [Lx1]
    x   : vector of input samples [Lx1]
    b   : vector of backward prediction error [Lx1]
    u   : u = R^(-1)*x calculated recursively [Lx1]
    P   : vector of last estimated power of b [M+1x1]
    d   : desired response
    mu_p: adaptation constant for the predictor coefficients
    mu_w: adaptation constant for the combiner coefficient
    maxk: maximum allowed value of abs(k)
Output parameters::
    k   : updated lattice predictor coefficients 
    w   : updated linear combiner coefficients 
    b   : updated backward prediction error 
    u   : updated {R^(-1)*x} 
    P   : updated  power estimate of b
    y   : linear combiner output
    e   : error signal [e = d - y]

Example

Figure 4.1: The adaptive filter coefficients after convergence and the learning curve for the complex FIR system identification problem using the ARLMSNEWT algorithm.

% ARLMSNEWT used in a simple system identification application.
% By the end of this script the adaptive filter w 
% should have the same coefficients as the unknown filter h.
iter = 5000;                   % samples to process
% Complex unknown impulse response
h  = [.9 + i*.4; 0.7+ i*.2; .5; .3+i*.1; .1];     
xn = 2*(rand(iter,1)-0.5);   % Input signal
% although xn is real, dn will be complex since h is complex
dn = osfilter(h,xn);         % Unknown filter output 
en = zeros(iter,1);          % error signal
% Initialize ARLMSNEWT with M=2, L=10
M    = 2;                    % AR model length
L    = 10;                   % filter length
mu_w = .01;                  % linear combiner step size
mu_p = 0.001;                % lattice predictor step size
[k,w,x,b,u,P,d,y,e]=init_arlmsnewt(L,M); 

%% Processing Loop
for (m=1:iter)
   x = [xn(m,:);x(1:end-1,:) ]; % update the delay line
   d = dn(m,:) + 1e-3*rand;     % additive noise var = 1e-6 
   [k,w,b,u,P,y,e]=asptarlmsnewt(k,w,x,b,u,P,d,mu_p,mu_w,0.99);  
   % save the last error sample to plot later
   en(m,:) = e;  
end;
% display the results
subplot(2,2,1);stem([real(w) imag(conj(w))]); grid;
subplot(2,2,2);
eb = filter(0.1,[1 -.9], en .* conj(en));
plot(10*log10(eb  ));grid

Running the above script will produce the graph shown in Fig. 4.1. The left side panel of this figure shows the adaptive filter coefficients after convergence which are almost identical to the unknown filter h. The right side graph shows the square error in dB versus time during the adaptation process, which is usually called the learning curve. The lower limit of the error signal power in the learning curve is defined here by the additive white noise added at the filter output (-60 dB).

Algorithm

asptarlmsnewt() performs the following operations every sample

• Calculates the forward and backward prediction errors for the lattice predictor,
• Calculates the power estimate of the backward prediction errors,
• Updates the PARCOR coefficients of the lattice predictor,
• Updates the estimate $u=\mR ^{-1} \; \vx (n)$,
• Evaluates the adaptive transversal filter output,
• Evaluates the error signal,
• Updates the adaptive transversal filter coefficients using the relationship $\vw (n+1) = \vw (n) + 2 \mu \; e(n) \vu (n)$.

Resources

The resources required to implement the ARLMSNEWT with a filter of length $L$ and predictor of length $M$ in real time is given in the table below. The computations given are those required to process one sample.

MEMORY	$4L + 0.5M^{2}+4.5M+6$
MULTIPLY	$3L +2.5M^2+9.5M+5$
ADD	$2L +2.5M^2+4.5M+2$
DIVIDE	L + M

See Also

INIT_ ARLMSNEWT, MODEL_ ARLMSNEWT.

Reference

[2] and [4] for analysis of the adaptive Lattice filters, [2] and [11] for analysis of the LMS-Newton algorithm.