Optimal FilteringOptimal filtering is a means of adaptive extraction of a weak desired signalin the presence of noise and interfering signals.Mathematically: Givenx(n) = d(n) + v(n),estimate and extract d(n) from the current and past values of x(n).EE 524, # 10 1Optimal Filtering (cont.)Let the filter coefficients bew =w0w1...wN−1.Filter output:y(n) =N−1Xk=0w∗kx(n − k) = wHx(n) =bd(n),EE 524, # 10 2wherex(n) =x(n)x(n − 1)...x(n − N + 1).Omitting index n, we can writebd = wHx, x =x0x1...xN−1.EE 524, # 10 3Optimal Filtering (cont.)Minimize the Mean Square Error (MSE)MSE = E {|e|2} = E {|d − wHx|2}= E {(d − wHx)(d∗− xHw)}= E {|d|2} − wHE {xd∗} − E {dxH}w + wHE {xxH}w.minwMSE → ∂MSE/∂w = 0 → E {xxH}w − E {xd∗} = 0.R = E {xxH} correlation matrixr = E {xd∗}.Wiener-Hopf equation (see Hayes 7.2):Rw = r −→ wopt= R−1r.EE 524, # 10 4Wiener FilterThree common filters:1. general non-causal:H(z) =∞Xk=−∞hkz−k,2. general causal:H(z) =∞Xk=0hkz−k,3. finite impulse response (FIR):H(z) =N−1Xk=0hkz−k.EE 524, # 10 5Wiener FilterCase 1: Non-causal filter:MSE = E [|e(n)|2] = E {[d(n) −∞Xk=−∞hkx(n − k)][d(n) −∞Xl=−∞hlx(n − l)]∗}= rdd(0) −∞Xl=−∞h∗lrdx(l) −∞Xk=−∞hkrdx(k)∗+∞Xk=−∞∞Xl=−∞rxx(l −k)hkh∗l.Remark: for causal and FIR filte rs, only limits of sums differ.Let hi= αi+ jβi. ∂MSE/∂αi= 0, ∂MSE/∂βi= 0 ∀i =⇒rdx(i) =∞Xk=−∞hkrxx(i − k) ∀i.EE 524, # 10 6In Z-domainPdx(z) = H(z)Pxx(z),which is the optimal non-causal Wiener filter.Example: x(n) = d(n) + e(n),Pdd(z) =0.36(1 − 0.8z−1)(1 − 0.8z),Pee(z) = 1,d(n) and e(n) uncorrelated.EE 524, # 10 7Optimal filter?Pxx(z) = Pdd(z) + Pee(z)=0.36(1 − 0.8z−1)(1 − 0.8z)+ 1= 1.6(1 − 0.5z−1)(1 − 0.5z)(1 − 0.8z−1)(1 − 0.8z),rdx(z) = E [d(n + k)[d(n)∗+ e(n)∗]] = rdd(k)Pdx(z) = Pdd(z),H(z) =Pdx(z)Pxx(z)=0.361.6(1 − 0.5z−1)(1 − 0.5z),h(k) = 0.3(12)|k|.EE 524, # 10 8Case 2: Causal filter (7.3.2 in Hayes):MSE = E [|e(n)|2] = E {[d(n) −∞Xk=0hkx(n − k)][d(n) −∞Xl=0hlx(n − l)]∗}= rdd(0) −∞Xl=0h∗lrdx(l) −∞Xk=0hkrdx(k)∗+∞Xk=0∞Xl=0rxx(l −k)hkh∗l=⇒rdx(i) =∞Xk=0hkrxx(i − k) ∀i.LetB(z)B∗(1z∗) =1Pxx(z).EE 524, # 10 9Pick B(z) to be a stable, causal, minimum- phase system. ThenPdx(z) = H(z)B−1(z)| {z }causalB−∗(1z∗) =⇒H(z)B(z)= [Pdx(z)B∗(1z∗)]+,where[Y (z)]+= [∞Xk=−∞ykz−k]+=∞Xk=0ykz−k.=⇒ H(z) = B(z)[Pdx(z)B∗(1z∗)]+.EE 524, # 10 10Causal Filter: ExampleSame as before: x(n) = d(n) + e(n),Pdd(z) =0.36(1 − 0.8z−1)(1 − 0.8z),Pee(z) = 1,d(n) and e(n) uncorrelated.EE 524, # 10 11Optimal filter?Pdx(z) = Pdd(z),Pxx(z) = Pdd(z) + Pee(z)= 1.6(1 − 0.5z−1)(1 − 0.5z)(1 − 0.8z−1)(1 − 0.8z),B(z) =1√1.61 − 0.8z−11 − 0.5z−1stable and causal,Pdx(z)B∗(1z∗) =0.36(1 − 0.8z−1)(1 − 0.8z)1√1.61 − 0.8z1 − 0.5z=0.36√1.61(1 − 0.8z−1)(1 − 0.5z)=0.36√1.6h531 − 0.8z−1+56z1 − 0.5ziEE 524, # 10 12[Pdx(z)B∗(1z∗)]+=0.36√1.6531 − 0.8z−1H(z) = B(z)[Pdx(z)B∗(1z∗)]+=1√1.61 − 0.8z−11 − 0.5z−10.36√1.6531 − 0.8z−1= 0.37511 − 0.5z−1=⇒ h(k) =38(12)k, k = 0, 1, 2, . . .Case 3: FIR filter (done before):rdx(i) =N−1Xk=0hkrxx(i − k) ∀i.EE 524, # 10 13FIR Wiener Filter - GeneralizationTheorem 1. Assume thatxd∈ NµxµdCxxCxdCdxCdd.Then the posterior pdf of d given x, fd|x(d|x), is also Gaussian, withmoments given byE [d|x] = µd+WHz }| {CdxC−1xx(x − µx)Cd|x= Cdd− CdxC−1xxCxd.EE 524, # 10 14FIR Wiener Filter - GeneralizationConsider d = Aβ + ξ,y = Bβ + η, whereEξη= 0, covξη=V11V12V21V22.Also, assume E [β] = β0and cov ( β) = Γ. We wish to predict d given y.EE 524, # 10 15Theorem 2. Minimum Mean-Square Error (MMSE) Solution:bd = Aβ0+ C(y − Bβ0),where C = (AΓBH+ V12)(BΓBH+ V22)−1.MMSE:AΓAH+V11+C(BΓBH+V22)CH−(AΓBH+V12)CH−C(BΓAH+V21).EE 524, # 10 16Kalman FilterConsider a state-space model:x(t) = Ax(t − 1) + ξ(t),y(t) = Bx(t) + η(t),where• {ξ(t)} and η(t) are independent sequences of zero-mean random vectorswith covariances Σξand Ση, respectively;• ξ(t) and x(u) are independent for t > u and η(t) and x(u) areindependent for t ≥ u.We wish to predict x(t) given y(1), y(2), . . . y(t).EE 524, # 10 17Idea: Theorem 2 can be used to predict x(s) given y(t). We write suchpredictor asbx(s|t) and its (minimum) mean-square error as P (s|t).How to construct a recursive procedure?EE 524, # 10 18Kalman FilterAssume that we knowbx(t + 1|t) and its MMSE P (t + 1|t). We wish to findbx(t + 1|t + 1). Then, we can write the following model:x(t + 1) = βy(t + 1) = Bβ + η,where β0=bx(t + 1|t) and Γ = P (t + 1|t). This impliesbx(t + 1|t + 1) =bx(t + 1|t) + C(t + 1) · [y(t + 1) − Bbx(t + 1|t)],whereC(t + 1) = P (t + 1|t)BH[BP (t + 1|t)BH+ Ση]−1.AlsoP (t + 1|t + 1) = P (t + 1|t) −C(t + 1)[BP (t + 1|t)BH+ Ση]−1C(t + 1)H.EE 524, # 10 19Kalman FilterHow about findingbx(t + 1|t) based onbx(t|t)? Then, we can write thefollowing model:x(t + 1) = Aβ + ξ(t + 1),where β0=bx(t|t) and Γ = P (t|t). This impliesbx(t + 1|t) = Abx(t|t)P (t + 1|t) = AP (t|t)AH+ Σξ.Now we have all the equations for recursion!EE 524, # 10