16 asptrls

Purpose

Sample per sample filtering and coefficient update using the Recursive Least Squares (RLS) Adaptive algorithm.

Syntax

[w,y,e,R]=asptrls(x,w,d,R,a)

Description

asptrls() implements the recursive least squares adaptive algorithm used to update transversal adaptive filters. Referring to the general adaptive filter shown in Fig. 2.6, asptrls() takes an input samples delay line $x(n)$, a desired sample $d(n)$, the vector of the adaptive filter coefficients from previous iteration $w(n-1)$, the estimate of the inverse correlation matrix from previous iterations $R(n-1)$, the forgetting factor $a$, and returns the filter output $y(n)$, the error sample $e(n)$, the updated vector of filter coefficients $w(n)$, and the updated matrix $R(n)$. The update equation of asptrls() is given by

$$\vw (n) = \vw (n-1) + \frac{\mR (n-1) \; \vx (n) \; e(n)}{a + \; \vx ^{T}(n) \; \mR (n-1) \vx (n)} .$$ (36)

The input and output parameters of asptrls() for an FIR adaptive filter of $L$ coefficients are summarized below.

Input Parameters [Size]:: 
   x   : vector of input samples at time n, [L x 1]
   w   : vector of filter coefficients w(n-1), [L x 1]
   d   : desired response d(n), [1 x 1]
   R   : last estimate of the inverse of the weighted 
         auto correlation matrix of x, [L x L]
   a   : forgetting factor, [1 x 1]
Output parameters::
   w   : updated filter coefficients w(n)
   y   : filter output y(n)
   e   : error signal, e(n)=d(n)-y(n)
   R   : updated R

Example

% RLS 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;                  % Number of 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, zero mean random.
% although xn is real, dn will be complex since h is complex
dn   = osfilter(h,xn);        % Unknown filter output 
en   = zeros(iter,1);         % vector to collect the error
% Initialize RLS with a filter of 10 coef.
[w,x,d,y,e,R]=init_rls(10,0.1); 

%% Processing Loop
for (m=1:iter)
   % update the input delay line
   x = [xn(m,:); x(1:end-1,:)];

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

   d = dn(m,:) + 1e-3*rand;      % additive noise of var = 1e-6   
   % call RLS to calculate the filter output, estimation error
   % and update the filter coefficients. 
   [w,y,e,R]=asptrls(x,w,d,R,0.98);
   % 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(.1, [1 -.9], en .* conj(en));
plot(10*log10(eb  ));grid

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

Remarks

• The closer the value of the forgetting factor $\lambda$ to one, the longer the memory of the algorithm becomes. Roughly, the algorithm will take into account up to $1/(1-\lambda)$ past samples.
• The RLS algorithm has only one convergence mode, and does not suffer from the eigenvalue spread problem as in the LMS and its variants. In general, the RLS converges within $2L$ to $3L$ samples, where $L$ is the filter length, and therefore very suitable for tracking applications
• asptrls() supports both real and complex data and filters. The adaptive filter for the complex RLS algorithm converges to the complex conjugate of the optimum solution.
• asptrls() does not update the input delay line for $x(n)$, this has been chosen to provide more flexibility, so that the same function can be used with transversal as well as linear combiner structures. Delay line update, by inserting the newest sample at the beginning of the buffer and shifting the rest of the samples to the right, has to be done before calling asptrls() as in the example above.

Algorithm

Unlike the LMS and its derivatives which use statistical (expected values) approach, the RLS is a deterministic algorithm based only on observed data. The practical implementation of the RLS algorithm adjusts the coefficients of an adaptive filter to minimize the following quantity

$$\xi(n) = \lambda^{n-k} e^{2}(n),$$ (37)

where $e(n)$ is the error signal and $\lambda$ is a positive constant close to but less than one usually called the forgetting factor. This choice for the $\xi(n)$ in (4.11) puts more emphasis on recent observed data samples and exponentially less emphasis on past samples. The current implementation of asptrls() performs the following operations

• Filters the input signal $x(n)$ through the adaptive filter $w(n-1)$ to produce the filter output $y(n)$.
• Calculates the error sample $e(n) = d(n) - y(n)$.
• Recursively updates the gain vector $\vK (n)$ given by
  

  $$\vK (n) = \frac{\mR (n-1) \; \vx (n)}{a + \; \vx ^{T}(n) \; \mR (n-1) \vx (n)}.$$ (38)

  
  

• Updates the adaptive filter coefficients according to (4.10)

Resources

The resources required to implement the RLS algorithm for a transversal adaptive FIR filter of $L$ coefficients in real time is given in the table below. The computations given are those required to process one sample.

MEMORY	$L^2+2L+4$
MULTIPLY	$2L^2 + 4L$
ADD	$1.5L^2 + 2.5L$
DIVIDE	L

See Also

INIT_ RLS, EQUALIZER_ RLS.

Reference

[2] and [4] for analysis of the RLS algorithm and its variants.