Adaptive Filters (Vaseghi - Advanced Digital Signal Processing and Noise Reduction)

Advanced Digital Signal Processing and Noise Reduction, Second Edition.Saeed V. VaseghiCopyright © 2000 John Wiley & Sons LtdISBNs: 0-471-62692-9 (Hardback): 0-470-84162-1 (Electronic)7y(m) e(m)µwk(m+1)α w(m)αz –1ADAPTIVE FILTERS7.1 State-Space Kalman Filters7.2 Sample-Adaptive Filters7.3 Recursive Least Square (RLS) Adaptive Filters7.4 The Steepest-Descent Method7.5 The LMS Filter7.6 SummaryAdaptive filters are used for non-stationary signals andenvironments, or in applications where a sample-by-sampleadaptation of a process or a low processing delay is required.Applications of adaptive filters include multichannel noise reduction,radar/sonar signal processing, channel equalization for cellular mobilephones, echo cancellation, and low delay speech coding.

This chapterbegins with a study of the state-space Kalman filter. In Kalman theory astate equation models the dynamics of the signal generation process, and anobservation equation models the channel distortion and additive noise.Then we consider recursive least square (RLS) error adaptive filters.

TheRLS filter is a sample-adaptive formulation of the Wiener filter, and forstationary signals should converge to the same solution as the Wiener filter.In least square error filtering, an alternative to using a Wiener-type closedform solution is an iterative gradient-based search for the optimal filtercoefficients. The steepest-descent search is a gradient-based method forsearching the least square error performance curve for the minimum errorfilter coefficients.

We study the steepest-descent method, and then considerthe computationally inexpensive LMS gradient search method.Adaptive Filters2067.1 State-Space Kalman FiltersThe Kalman filter is a recursive least square error method for estimation ofa signal distorted in transmission through a channel and observed in noise.Kalman filters can be used with time-varying as well as time-invariantprocesses. Kalman filter theory is based on a state-space approach in whicha state equation models the dynamics of the signal process and anobservation equation models the noisy observation signal. For a signal x(m)and noisy observation y(m), the state equation model and the observationmodel are defined asx ( m ) = Φ ( m , m − 1) x ( m − 1) + e ( m )y ( m ) = Η ( m) x ( m) + n( m )(7.1)(7.2)wherex(m) is the P-dimensional signal, or the state parameter, vector at time m,Φ(m, m–1) is a P × P dimensional state transition matrix that relates thestates of the process at times m–1 and m,e(m) is the P-dimensional uncorrelated input excitation vector of the stateequation,Σee(m) is the P × P covariance matrix of e(m),y(m) is the M-dimensional noisy and distorted observation vector,H(m) is the M × P channel distortion matrix,n(m) is the M-dimensional additive noise process,Σnn(m) is the M × M covariance matrix of n(m).The Kalman filter can be derived as a recursive minimum mean squareerror predictor of a signal x(m), given an observation signal y(m).

The filterderivation assumes that the state transition matrix Φ(m, m–1), the channeldistortion matrix H(m), the covariance matrix Σee(m) of the state equationinput and the covariance matrix Σnn(m) of the additive noise are given.In this chapter, we use the notation ŷ(m m − i ) to denote a prediction ofy(m) based on the observation samples up to the time m–i. Now assume thatyˆ (m m − 1) is the least square error prediction of y(m) based on theobservations [y(0), ..., y(m–1)]. Define a so-called innovation, or predictionerror signal asv ( m ) = y ( m ) − yˆ (m m − 1)(7.3)State-Space Kalman Filters207n (m)e (m)x(m)+H(m)Φ (m,m-1)Z+y (m)-1Figure 7.1 Illustration of signal and observation models in Kalman filter theory.The innovation signal vector v(m) contains all that is unpredictable from thepast observations, including both the noise and the unpredictable part of thesignal.

For an optimal linear least mean square error estimate, theinnovation signal must be uncorrelated and orthogonal to the pastobservation vectors; hence we haveE [v ( m ) y T ( m − k ) ]= 0 ,andE [v (m)v T (k )]= 0 ,k>0m≠k(7.4)(7.5)The concept of innovations is central to the derivation of the Kalman filter.The least square error criterion is satisfied if the estimation error isorthogonal to the past samples. In the following derivation of the Kalmanfilter, the orthogonality condition of Equation (7.4) is used as the startingpoint to derive an optimal linear filter whose innovations are orthogonal tothe past observations.Substituting the observation Equation (7.2) in Equation (7.3) and usingthe relationyˆ (m | m − 1)=E [ y (m) xˆ (m m − 1)](7.6)= H (m) xˆ (m m − 1)yieldsv (m) = H (m) x (m) + n(m) − H (m) xˆ (m m − 1)(7.7)= H ( m) ~x ( m) + n ( m)where x˜ (m) is the signal prediction error vector defined as~x (m) = x (m) − xˆ (m m − 1)(7.8)Adaptive Filters208From Equation (7.7) the covariance matrix of the innovation signal is givenbyΣ vv (m) = E v (m)v T (m)(7.9)= H (m) Σ x~~x (m) H T (m) + Σ nn (m)[]where Σ x˜ x˜ (m) is the covariance matrix of the prediction error x˜ (m) .

Letxˆ (m +1 m) denote the least square error prediction of the signal x(m+1).Now, the prediction of x(m+1), based on the samples available up to thetime m, can be expressed recursively as a linear combination of theprediction based on the samples available up to the time m–1 and theinnovation signal at time m asxˆ (m + 1 m ) = xˆ (m + 1 m − 1) + K (m)v (m)(7.10)where the P × M matrix K(m) is the Kalman gain matrix.

Now, fromEquation (7.1), we havexˆ (m + 1 m − 1) = Φ (m + 1, m) xˆ (m m − 1)(7.11)Substituting Equation (7.11) in (7.10) gives a recursive prediction equationasxˆ (m + 1 m ) = Φ (m + 1, m) xˆ (m m − 1) + K (m)v (m)(7.12)To obtain a recursive relation for the computation and update of theKalman gain matrix, we multiply both sides of Equation (7.12) by vT(m)and take the expectation of the results to yieldE [xˆ ( m + 1 m )v T ( m ) ] = E [Φ ( m + 1, m ) xˆ (m m − 1)v T ( m ) ]+ K ( m )E [v ( m ) v T ( m ) ](7.13)Owing to the required orthogonality of the innovation sequence and the pastsamples, we haveE xˆ (m m − 1)v T (m) =0(7.14)[]Hence, from Equations (7.13) and (7.14), the Kalman gain matrix is givenby−1(m)K ( m ) =E xˆ ( m + 1 m )v T ( m ) Σ vv(7.15)[]State-Space Kalman Filters209The first term on the right-hand side of Equation (7.15) can be expressed asE [xˆ (m + 1 m )v T (m)] =E [( x (m + 1) − x~(m + 1 m ))v T (m)][=E x (m + 1)v T (m)[[]]= E (Φ (m + 1, m) x (m)+e (m + 1) )( y (m)− yˆ (m m − 1))T= E [Φ (m + 1, m)( xˆ (m m − 1) + ~x (m m − 1))](H (m) ~x (m m − 1) + n(m) )T[]]= Φ (m + 1, m)E ~x (m m − 1)~x T (m m − 1) H T (m)(7.16)In developing the successive lines of Equation (7.16), we have used thefollowing relations:E ~x ( m + 1 | m )v T ( m ) = 0(7.17)[]E [e ( m + 1) ( y ( m )− yˆ ( m| m − 1))T ]= 0(7.18)x(m) = xˆ(m| m − 1)+ x˜ (m |m − 1)(7.19)E [ xˆ ( m | m − 1) ~x ( m| m − 1)] = 0(7.20)and we have also used the assumption that the signal and the noise areuncorrelated.

Substitution of Equations (7.9) and (7.16) in Equation (7.15)yields the following equation for the Kalman gain matrix:[K (m ) =Φ (m + 1, m)Σ ~x~x (m) H T (m) H (m)Σ x~x~ (m) H T (m) + Σ nn (m)]−1(7.21)where Σ x˜ x˜ (m) is the covariance matrix of the signal prediction errorx˜ (m|m − 1) . To derive a recursive relation for Σ x˜ x˜ (m), we consider~x (m m − 1) = x (m ) − xˆ (m m − 1)(7.22)Substitution of Equation (7.1) and (7.12) in Equation (7.22) andrearrangement of the terms yields~x (m | m − 1) = [Φ ( m , m − 1) x ( m − 1) + e ( m ) ] − [Φ ( m , m − 1) xˆ (m − 1 m − 2 ) + K ( m − 1) v ( m − 1) ]= Φ ( m , m − 1) ~x (m − 1) + e ( m ) − K ( m − 1) H ( m − 1) ~x ( m − 1) + K ( m − 1) n ( m − 1)= [Φ ( m , m − 1) − K ( m − 1) H ( m − 1) ]~x (m − 1) + e ( m ) + K ( m − 1) n ( m − 1)(7.23)Adaptive Filters210From Equation (7.23) we can derive the following recursive relation for thevariance of the signal prediction errorΣ ~x~x (m) = L(m)Σ ~x~x (m − 1) LT (m) + Σ ee (m) + K (m − 1)Σ nn (m − 1) K T (m − 1)(7.24)where the P × P matrix L(m) is defined asL ( m ) = [Φ ( m , m − 1) − K ( m − 1) H ( m − 1) ](7.25)Kalman Filtering AlgorithmInput: observation vectors {y(m)}Output: state or signal vectors { xˆ (m) }Initial conditions:Σ ~x~x (0) = δIxˆ (0 − 1) = 0For m = 0, 1, ...Innovation signal:v(m) = y(m ) − H(m)xˆ (m|m − 1)Kalman gain:[K (m) =Φ (m + 1, m)Σ ~x~x (m) H T (m) H (m)Σ ~x~x (m) H T (m) + Σ nn (m)(7.26)(7.27)(7.28)]−1(7.29)Prediction update:xˆ (m + 1|m) = Φ (m + 1,m) xˆ (m |m − 1) + K(m)v(m)(7.30)Prediction error correlation matrix update:L(m +1) = [Φ (m + 1,m) − K (m) H (m)](7.31)Σ x~x~ (m + 1)= L(m + 1)Σ x~x~ (m) L(m + 1)T + Σ ee (m + 1) + K (m)Σ nn (m) K (m)(7.32)Example 7.1 Consider the Kalman filtering of a first-order AR processx(m) observed in an additive white Gaussian noise n(m).

Assume that thesignal generation and the observation equations are given asx (m)= a(m) x (m − 1) + e(m)(7.33)State-Space Kalman Filters211y(m)= x(m) + n(m)(7.34)Let σ e2 (m) and σ n2 (m) denote the variances of the excitation signal e(m)and the noise n(m) respectively. Substituting Φ(m+1,m)=a(m) and H(m)=1in the Kalman filter equations yields the following Kalman filter algorithm:Initial conditions:σ ~x2 (0) = δxˆ (0 − 1) = 0(7.35)(7.36)For m = 0, 1, ...Kalman gain:a (m + 1)σ ~x2 (m)k ( m) = 2σ ~x (m) + σ n2 (m)Innovation signal:v(m )= y(m)− xˆ (m | m − 1)Prediction signal update:xˆ (m + 1| m)= a(m + 1) xˆ(m|m − 1)+ k(m)v(m)(7.37)(7.38)(7.39)Prediction error update:σ 2˜x (m + 1) = [a(m + 1) − k(m)]2 σ x2˜ (m) + σ e2 (m + 1) + k 2 (m) σ n2 (m) (7.40)where σ 2˜x (m) is the variance of the prediction error signal.Example 7.2 Recursive estimation of a constant signal observed in noise.Consider the estimation of a constant signal observed in a random noise.The state and observation equations for this problem are given byx(m)= x(m − 1) = xy(m) = x + n(m)(7.41)(7.42)Note that Φ(m,m–1)=1, state excitation e(m)=0 and H(m)=1.