Adaptive Filters (Vaseghi - Advanced Digital Signal Processing and Noise Reduction), страница 2

Using theKalman algorithm, we have the following recursive solutions:Initial Conditions:σ 2x˜ (0) = δxˆ (0 −1) = 0(7.43)(7.44)Adaptive Filters212For m = 0, 1, ...Kalman gain:σ ~x2 (m)σ ~x2 (m) + σ n2 (m)(7.45)v(m) = y (m)− xˆ (m| m − 1)(7.46)k ( m) =Innovation signal:Prediction signal update:xˆ (m + 1 | m)= xˆ (m | m − 1) + k (m)v(m)Prediction error update:σ ~x2 (m + 1)=[1 − k (m)]2 σ ~x2 (m) + k 2 (m)σ n2 (m)(7.47)(7.48)7.2 Sample-Adaptive FiltersSample adaptive filters, namely the RLS, the steepest descent and the LMS,are recursive formulations of the least square error Wiener filter.

Sampleadaptive filters have a number of advantages over the block-adaptive filtersof Chapter 6, including lower processing delay and better tracking of nonstationary signals. These are essential characteristics in applications such asecho cancellation, adaptive delay estimation, low-delay predictive coding,noise cancellation, radar, and channel equalisation in mobile telephony,where low delay and fast tracking of time-varying processes andenvironments are important objectives.Figure 7.2 illustrates the configuration of a least square error adaptivefilter.

At each sampling time, an adaptation algorithm adjusts the filtercoefficients to minimise the difference between the filter output and adesired, or target, signal. An adaptive filter starts at some initial state, andthen the filter coefficients are periodically updated, usually on a sample-bysample basis, to minimise the difference between the filter output and adesired or target signal. The adaptation formula has the general recursiveform:next parameter estimate = previous parameter estimate + update(error)where the update term is a function of the error signal. In adaptive filtering anumber of decisions has to be made concerning the filter model and theadaptation algorithm:Recursive Least Square (RLS) Adaptive Filters213(a) Filter type: This can be a finite impulse response (FIR) filter, or aninfinite impulse response (IIR) filter. In this chapter we only considerFIR filters, since they have good stability and convergence propertiesand for this reason are the type most often used in practice.(b) Filter order: Often the correct number of filter taps is unknown.

Thefilter order is either set using a priori knowledge of the input and thedesired signals, or it may be obtained by monitoring the changes in theerror signal as a function of the increasing filter order.(c) Adaptation algorithm: The two most widely used adaptation algorithmsare the recursive least square (RLS) error and the least mean squareerror (LMS) methods. The factors that influence the choice of theadaptation algorithm are the computational complexity, the speed ofconvergence to optimal operating condition, the minimum error atconvergence, the numerical stability and the robustness of the algorithmto initial parameter states.7.3 Recursive Least Square (RLS) Adaptive FiltersThe recursive least square error (RLS) filter is a sample-adaptive, timeupdate, version of the Wiener filter studied in Chapter 6.

For stationarysignals, the RLS filter converges to the same optimal filter coefficients asthe Wiener filter. For non-stationary signals, the RLS filter tracks the timevariations of the process. The RLS filter has a relatively fast rate ofconvergence to the optimal filter coefficients. This is useful in applicationssuch as speech enhancement, channel equalization, echo cancellation andradar where the filter should be able to track relatively fast changes in thesignal process.In the recursive least square algorithm, the adaptation starts with someinitial filter state, and successive samples of the input signals are used toadapt the filter coefficients. Figure 7.2 illustrates the configuration of anadaptive filter where y(m), x(m) and w(m)=[w0(m), w1(m), ..., wP–1(m)]denote the filter input, the desired signal and the filter coefficient vectorrespectively.

The filter output can be expressed asxˆ (m) = w T (m) y (m)(7.49)Adaptive Filters214“Desired” or “target ”signal x(m)Input y(m)y(m–1)z –1w0z –1w1y(m–2)...z –1y(m-P-1)wP–1w2Adaptationalgorithme(m)Transversal filter^x(m)Figure 7.2 Illustration of the configuration of an adaptive filter.where xˆ (m) is an estimate of the desired signal x(m). The filter error signalis defined ase(m) = x(m)− xˆ (m)(7.50)= x ( m )− w T ( m) y ( m)The adaptation process is based on the minimization of the mean squareerror criterion defined as[]2E [e 2 (m)] = E  x(m) − w T (m) y (m) = E[ x 2 (m)] − 2 w T (m)E [ y (m) x(m)] + w T (m)E [ y (m) y T (m)] w (m)= rxx (0) − 2w T (m)r yx (m) + w T (m) R yy (m)w (m)(7.51)The Wiener filter is obtained by minimising the mean square error withrespect to the filter coefficients. For stationary signals, the result of thisminimisation is given in Chapter 6, Equation (6.10), asw = R −yy1 r yx(7.52)Recursive Least Square (RLS) Adaptive Filters215where Ryy is the autocorrelation matrix of the input signal and ryx is thecross-correlation vector of the input and the target signals.

In the following,we formulate a recursive, time-update, adaptive formulation of Equation(7.52). From Section 6.2, for a block of N sample vectors, the correlationmatrix can be written asR yy = Y TY =N −1∑ y ( m) y T ( m )(7.53)m =0where y(m)=[y(m), ..., y(m–P)]T. Now, the sum of vector product inEquation (7.53) can be expressed in recursive fashion asR yy (m) = R yy (m − 1) + y (m) y T (m)(7.54)To introduce adaptability to the time variations of the signal statistics, theautocorrelation estimate in Equation (7.54) can be windowed by anexponentially decaying window:R yy (m) = λ R yy (m − 1) + y (m) y T (m)(7.55)where λ is the so-called adaptation, or forgetting factor, and is in the range0>λ>1. Similarly, the cross-correlation vector is given byryx =N −1∑ y ( m) x ( m)(7.56)m=0The sum of products in Equation (7.56) can be calculated in recursive formas(7.57)r yx (m) = r yx (m − 1) + y(m)x(m)Again this equation can be made adaptive using an exponentially decayingforgetting factor λ:r yx (m) = λ r yx (m − 1) + y (m) x(m)(7.58)For a recursive solution of the least square error Equation (7.58), we need toobtain a recursive time-update formula for the inverse matrix in the formAdaptive Filters216R −yy1 (m)= R −yy1 (m − 1) + Update(m)(7.59)A recursive relation for the matrix inversion is obtained using the followinglemma.The Matrix Inversion Lemma Let A and B be two positive-definiteP × P matrices related by(7.60)A = B −1 + CD −1C Twhere D is a positive-definite N × N matrix and C is a P × N matrix.

Thematrix inversion lemma states that the inverse of the matrix A can beexpressed as(A −1 = B − BC D + C T BC)−1 C T B(7.61)This lemma can be proved by multiplying Equation (7.60) and Equation(7.61). The left and right hand sides of the results of multiplication are theidentity matrix. The matrix inversion lemma can be used to obtain arecursive implementation for the inverse of the correlation matrix R−1yy ( m ).LetR yy (m) = A(7.62)λ−1 R −yy1 (m − 1) = B(7.63)y(m) = CD = identity matrix(7.64)(7.65)Substituting Equations (7.62) and (7.63) in Equation (7.61), we obtainR −yy1 (m)=λ−1R −yy1 (m − 1) −λ−2 R −yy1 (m − 1) y (m) y T (m) R −yy1 (m − 1)1+λ−1 y T (m) R −yy1 (m − 1) y (m)(7.66)Now define the variables Φ(m) and k(m) asΦ yy (m) = R−1yy (m)(7.67)Recursive Least Square (RLS) Adaptive Filters217andλ−1 R −yy1 (m − 1) y (m)k ( m) =1+λ−1 y T (m) R −yy1 (m − 1) y (m)(7.68)orλ−1Φ yy (m − 1) y (m)k ( m) =1+λ−1 y T (m)Φ yy (m − 1) y (m)(7.69)Using Equations (7.67) and (7.69), the recursive equation (7.66) forcomputing the inverse matrix can be written asΦ yy (m)= λ−1Φ yy (m − 1) − λ−1k (m) y T (m)Φ yy (m − 1)(7.70)From Equations (7.69) and (7.70), we have[]k (m) = λ−1Φ yy (m − 1) − λ−1k (m) y T (m)Φ yy (m − 1) y (m)= Φ yy (m) y (m)(7.71)Now Equations (7.70) and (7.71) are used in the following to derive theRLS adaptation algorithm.Recursive Time-update of Filter Coefficients The least square errorfilter coefficients arew (m) = R −yy1 (m) r yx (m)(7.72)= Φ yy (m)r yx (m)Substituting the recursive form of the correlation vector in Equation (7.72)yieldsw(m) = Φ yy (m)[λ r yx (m − 1) + y(m)x(m)]= λΦΦ yy (m) r yx (m − 1) + Φ yy (m) y(m)x(m)(7.73)Now substitution of the recursive form of the matrix Φyy(m) from Equation(7.70) and k(m)=Φ(m)y(m) from Equation (7.71) in the right-hand side ofEquation (7.73) yieldsAdaptive Filters218[]w ( m )= λ −1 Φ yy ( m − 1) − λ −1 k ( m ) y T ( m )Φ yy ( m − 1) λ r yx ( m − 1) + k ( m ) x ( m )(7.74)orw (m)=Φ yy (m − 1) r yx ( m − 1) −k ( m) y T (m)Φ yy (m − 1) r yx ( m − 1) + k ( m) x( m)(7.75)Substitution of w(m–1)=Φ(m–1)ryx(m–1) in Equation (7.75) yields[w (m)= w (m − 1) −k (m) x(m) − y T (m) w (m − 1)](7.76)This equation can be rewritten in the following formw(m)= w(m − 1) − k(m)e(m)(7.77)Equation (7.77) is a recursive time-update implementation of the leastsquare error Wiener filter.RLS Adaptation AlgorithmInput signals: y(m) and x(m)Φ yy (m)= δIInitial values:w ( 0 )= w IFor m = 1,2, ...Filter gain vector:λ−1Φ yy (m − 1) y (m)k ( m) =1+λ−1 y T (m)Φ yy (m − 1) y (m)Error signal equation:e ( m )= x ( m ) − w T ( m − 1) y ( m )Filter coefficients:w(m) = w(m − 1) − k(m)e(m)(7.78)(7.79)(7.80)Inverse correlation matrix update:Φ yy (m)= λ −1 Φ yy (m − 1) − λ −1k(m)yT (m)Φ yy (m − 1)(7.81)The Steepest-Descent Method219E [e2(m)]woptimalw(i) w(i–1)w(i –2)wFigure 7.3 Illustration of gradient search of the mean square error surface for theminimum error point.7.4 The Steepest-Descent MethodThe mean square error surface with respect to the coefficients of an FIRfilter, is a quadratic bowl-shaped curve, with a single global minimum thatcorresponds to the LSE filter coefficients.

Figure 7.3 illustrates the meansquare error curve for a single coefficient filter. This figure also illustratesthe steepest-descent search for the minimum mean square error coefficient.The search is based on taking a number of successive downward steps inthe direction of negative gradient of the error surface. Starting with a set ofinitial values, the filter coefficients are successively updated in thedownward direction, until the minimum point, at which the gradient is zero,is reached.

The steepest-descent adaptation method can be expressed as ∂ E[e 2 (m)] w (m + 1) = w (m) + µ −∂ w ( m) (7.82)where µ is the adaptation step size. From Equation (5.7), the gradient of themean square error function is given byAdaptive Filters220∂ E[e 2 (m)]= − 2r yx + 2 R yy w (m)∂ w ( m)(7.83)Substituting Equation (7.83) in Equation (7.82) yieldsw (m + 1) = w (m) + µ [r yx − R yy w (m)](7.84)where the factor of 2 in Equation (7.83) has been absorbed in the adaptationstep size µ.