(Ut)) = ttx)+ I\M)(U0))M+ Jo Jo
+ f\a'D,dW{e)), Jo Jo
(2.88) (2.88)
which, upon taking expectation and using (2.85), yields (2.89) (2.89)
PttX(4>) ==*{x) PS,x{M)de. {M)d6. Pt,*(0) ( * ) + /+ / Pe, Jo Jo
Differentiating this and recalling the continuity property of the process £ we obtain (2.87) which clearly is the weak form of (2.86). QED We can also define a Markov semigroup of operators {S(t),t sponding to PtiX(.) as follows: (S(t)<j>)(x) Pt}X (),t>>,xxe > >,xn. x (S(t)4>)(x) ==Pt, xCt>),t
en.
> 0} corre-
(2.90)
Since P(£,x,)) is a probability measure, it is obvious that S(t) is a contraction operator on Bb(Rn), the space of bounded Borel measurable functions on Rn. It satisfies the following two properties (t) : 5(0) = / and (it) : S(t + r) = S(t)S(r),t,r > 0. The second property actually follows from uniqueness of solution and hence the Chapman-Kolmogorov equation holds. Thus S(t), t > 0, is a contraction semigroup. The operator valued function S is called a Feller semigroup if it maps Cb(Rn) into Cb{Rn). As it stands, under certain mild assumptions, the semigroup 5 is weakly continuous on Cb(Rn) in the sense that, for each € Cb(Rn), lim (S(tU)(x) t-*o+
= (x), 4>(x), forforeach eachfixed fixedx xG GRnR. n.
For Ito processes, this follows from (b) of theorem 5. In fact, the property (b) implies that this convergence is uniform on compact subsets of Rn. In general this semigroup is not strongly continuous on Cb(Rn). However, it is so on the space of bounded uniformly continuous functions, BUC(Rn), furnished with the topology of uniform convergence. For bounded and continuous parameters {6,cr}, this can be proved easily by use of Lebesgue dominated convergence
Linear and Nonlinear Filtering
45
theorem and Chebyshev inequality. The general case is proved by truncation of the parameters {6,a} given by the sequence {6n,an} which are uniformly bounded and which converge uniformly on compact subsets of fin. For diffusion processes, if (Dl) (see definition 8) holds uniformly with respect to x 6 Rn, then S is strongly continuous on Cb(Rn). If it is only true for each fixed x e Rn, then it is only weakly continuous. Define Ht(E) = Prob{t{t)€E},E€BRn,
(2.91)
where £ is the solution of equation (2.84) corresponding to the initial state £o = x which has the distribution i/0. From the above result we can derive a differential equation for the ( probability) measure valued function {fj.t,t > 0} induced by the solution process {£(£),£ > 0}. Let M(Rn) denote the space of countably additive regular Borel measures on BRn and VM(Rn) C M(Rn) the space of regular probability measures. For each A € M(Rn) and / € Cb(Rn), the action of A on / is defined and denoted by Hf) = /
f(x)X(dx)
= < A, / > = < / , A > .
T h e o r e m 13 The family of probability measures {/j,t,£ > 0} satisfies the following differential equation (d/dt)>*t = A*»t, Mo = fo, t > 0
(2.92) (2.92)
in the weak sense, that is, {d/dt)H(4>)
=nt(M),t>0,
M 0 ) = ^o(
(2.93)
for each 4> 6 ( ^ ( . R " ) . Proof. Proof follows readily from Lemma 12. Using the semigroup S(t), t > 0, we can rewrite (2.89) as S(t)cj> = 4>+ f S{6){A(j>)de. Jo Integrating this with respect to the initial measure vQ and letting S*(t) denote the adjoint semigroup, we have <S*(t)v 0 ,4>>=< v»,4> > + / Jo
< S*{6)vo,A4> >d9.
Stochastic Differential
46
Equations
Setting jjbt = S*(t)i/Q, it follows from this that fit satisfies the evolution equation (2.92) in the weak sense given by (2.93). This ends our formal proof. QED Here we have introduced two semigroups of operators S(£),£ > 0, and S*(t),t > 0, the later being the adjoint of the former. The semigroup S solves the backward Kolmogorov equation in Cb(Rn) and S* solves the forward equa tion on the space of measures M(Rn). Under quite general assumptions they are pointwise continuous but not strongly continuous unless some additional technical conditions are satisfied. If the initial distribution UQ has a density with respect to Lebesgue measure, that is, there exists a po € L\(Rn) such that Po(x)dxVGeBRn,
JG
then the measure valued function fit has a density, p(£, x) such IH(G) = I p{t,x)dx VG e BRn, JG
and it satisfies the Forward Kolmogorov equation x),t>0,xeRn
(d/dt)p(t, x) = A*p(t, p(0,x)=p0(x),xeRn.
H,(G)= [
We have stated often in this section that the proofs are formal. The reason for this is that, in general, neither the Backward nor the Forward Kolmogorov equations have classical solutions, that is, solutions that satisfy the correspond ing equations for all (t,x) e I x Rn. On the other hand weak solutions may exist under very mild assumptions. For many practical applications, weak so lutions are good enough and may be computed using Galerkin approach as discussed in chapter 13. Example 4 For a simple illustration, let us consider the scalar equation d£ = P(0dt + adW where W is one dimensional standard Wiener process and a is a constant and (3 is a continuous real valued function on R. The differential operators A, A* are given by M = P{x){d4>ldx) +
a2(d2(/)/dx2)
A*> = -(d/dx)((3(x)) +
a2(d2/dx2)((t>).
Linear and Nonlinear Filtering
47
Thus the equation for the probability density is given by (d/dt)p(t, x) - a2(d2/dx2)p(t,
x) + (d/dx)(l3(x)p(t,
p(0,x)=po(x).
x)) = 0,
;Ti G B "
This is precisely the heat equation for a rod or some liquid in a thin cylindrical pipe of infinite length with a convective term, where a 2 is the coefficient of heat conduction of the material. 2.6 Change of Drift and Girsanov Theorem In chapter one we discussed briefly the concept of absolute continuity of measures. Two different stochastic differential equations on the same state space, determined by the parameters (b2,o~) and (bi,cr) respectively induce two measures ^2 and fi\ on the path space C = C(I, Rn). The question is how they are related and under what conditions /12 -< Mi or /ii -< /Z2 or both and therefore equivalent. Suppose C is furnished with the Borel sigma field Be, that is the sigma field generated by open sets in C containing all cylinder sets of the form i G C : £(ti) G r i , • • .,£(tk) e Tk
R^U
G J;i = 1, • • •,fc;k G j v j .
As discussed in chapter 1, according to Radon-Nikodym theorem, if |x2 ^< Mi there exists a q G I a ( C , Bc,/J>i) such that M2(A) = / 9(0Mi(d0 VA G ^ c -
(2.96)
Our objective here is to determine conditions for existence of q and an explicit expression for it. This result is used in chapters 13, 15 and 16 dealing with the problems of nonlinear filtering, control and identification respectively. For a clear understanding of this topic we start with an elementary problem on Rn instead of C and use this result to construct q for the infinite dimensional prob lem by taking limits of g m constructed piece by piece for m finite dimensional problems. Let X be a Gaussian random element in the state space Rn with mean m G Rn and covariance C G M+(n x n), and h G Rn a fixed element. Define the random variables Yx = X,
and
Y2 = X + h,
(2.97)
48
Stochastic Differential Equations
and the function g(x,m,C)
= (l/(2
exp{-{l/2){C-\x
- m),x - m))}. (2.98)
Clearly the probability densities of Y\ and I2 are given by Pi(x)=g(x,m,C) p2(x) =g(x,m
) =
+ h,C).
By simple algebraic manipulation of the exponent, it is easy to see that p 2 (x
Pl(x
l
m) - (l/2)(C-lh,h)}.
h,x-
(2.100)
Let [i\ and fi2 be the Gaussian measures corresponding to p\ and P2 respec tively. Then clearly for any E € BRTI l*2(E) = f q(x)vn(dx)
(2.101)
JE
where q is the RND of ^2 with respect to \x\ given by q(x) = exp{(C~lh,x-
m) - (1/2)(C _ 1 /i,h)}.
(2.102)
Clearly q G Li(i2 n ,##n,n{). Now we consider two Ito processes {^1,^2} given by the solutions of the following two SDE's, d& = bi(t, £i)dt + *(t, Zi)dW,
teI=[0,T]
)
exp{(C-
6(0) = 6,o, » = 1,2, which correspond to two different drifts 61 and 62 respectively. Let //^o and /i2,o denote the measures corresponding to the initial states 6,0 and £2,o re spectively. In the following theorem we assume that W is a standard Brownian motion taking values from Rn. Theorem 14 Suppose a : I x Rn —► M(n x n) has bounded inverse for all (£,x) e IxRn and bi : IxRn —► Rn are measurable functions and /i2,o -< A*i,o with RND g0- Then /J,2 -< /ii and the RND is given by (6) = 9o(6 (0)) expij{<j-l(b2
- h),dW)
- (1/2) y l ^ - 1 ^ - 6i| 2 cft|,
where a~l(b2 - h) is evaluated along the path {£i(£),£ G / } .
Linear and Nonlinear Filtering
49
Proof. We prove this result for continuous {bita}. For measurable coefficients the result follows from the limit in probability of the expression for the continuous case. Let the interval / be partitioned into m equal subintervals 7 r - (^-l'*"]>* = l,2....,m where tf = (kT/m). For simplicity of notation we omit the superscript m on tk. Note that for sufficiently large m we can approximate the solutions by «"(«*) « C ( t t - i ) +
(T/mMtk.l,^(tk.l)) +
(2.104)
for t = 1,2 and k = 1,2, ....,m. Clearly given ^ " ( t k - i ) , the difference
A?fc = er(*fe) - Wfc-o »(r/m^^-a^r^-o)
+ ^ n (t fc _ 1 ))(W(t fc )-W(«fe_ 1 )),
(2.105)j '
(
is a Gaussian random element in Rn with mean and covariance matrix given by M™ k.i,^(t k-i)), M# k = = (T/mMh-u&fa-i)),^ (r/m)6<(tf c _i,C(**-i)).Crfc = = (T/m){aa')(t (T/m)(ff<7')(t fc_i,Cr(*fc-i)),
(2.106) (2-106)
respectively. According to (2.96), the RND (Radon-Nikodym derivative) is a functional on the path space and so must be computed along a common path £ e C, say, &. Then (2.106) reduces to M™k =
(T/m)bi(tk-1,tf(tk_1)),
C™k ==(T/m){aa'){t CTfc ( T / m ) ^ k'_UTit ) ^ , !k-i)) , ^ ^ - ! ) ) ==CCf tf t ==CC&&, ,
(2.107) '
(
giving the means and the covariance matrices of the two Gaussian random elements A£ fc and A^ fc respectively. Temporarily, for convenience of notation, we write M2™ = ((TT/ mH) 6^ 2^( taf er_t1 ,UC (- ^i-)i ))) , M 22 EE M£ k fe = Mi = M f t = (T/m)h ( tftc__i,£*(*k-i)) (r/m)6i(t l t er(*fc-i)) /vm
(2.108) (2-108)
/^m
= — °2,A:> = °l,fc °l,fc — °2,fc' and denote by 7£* the following expression 7 ? = {(C-1(M2-M1),A-M1)-(1/2)(C-1(M2-M1),(M2-M1))}.
(2.109)
Then, identifying h = M 2 - M i , x - m = A - M x = < r(t fe _i,er( i fe-i))AW'* evaluated along the path &, it follows from (2.102) that the corresponding RND is given by C ( A )) ==e xe px 7p r7 .r
50
Stochastic Differential Equations
Let {/x™fc,i = 1,2} denote the measures induced by {£™(£fc),i = 1,2}. Given that H™k_1 -< vTk-ii is given by
an(
^ S i v e n ^i7fc-i'
tne
witn res
RND °* ^k
P e c t to V>™k
(ft^MtfctK'^'-
(2uo)
'
for A: = 1,2,..., m. Thus if the two measures are absolutely continuous at time t — 0, that is, //2,o -< Mi,o, then it follows from (2.110) that
(^)«w-(^)«">fi-*r>.
(2.111)
= 9o(6,o)exp(f^7r)\fe=i
'
It follows from the expressions (2.108)-(2.109) that
Ik
= Uk-l,m(hk-l,m
-6l,fc-l,m),AWfc_iJ
- (r/2m)|fffe_
1
1>m (6 2lfc _ 1 , m
(2.112) 2
- 6i, fc _i, m )| .
where Ck-l,m
= c r ( ^ f c - l , C r ( ^ - l ) ) , ^ 2 , f c - l , m = b2(tk-l,
&l,*-l,m =
fcl(tfc-l,fT(tfc-l)),
fi^fe-l))*
A ^ f c - i = W(tfc) -
Wftfc-i).
Hence we have
Letting m —> oo in equation (2.111), we arrive at the result stated in the theorem. This completes the proof. QED In all our applications in chapters 13,15 and 16, we have £i5o = £2,0 and hence q0 = 1. Define f = o~~l (b2 — b\) and
Qt(f) = exp IjT (/, dW) - (1/2) j * \f\2dd\. For /i2 to be a probability measure on C it is necessary that
/*2(c) = / giT(0Mi(de) = iJc
(2.113)
Linear and Nonlinear Filtering
51
Sufficient conditions for this to hold are that / is essentially bounded or more generally, there exists a constant /? > 1 such that
E{exp(p / l / l 2 ^ ) } <
oo.
Under either of these assumptions one can prove that (i) £ { ^ ( / ) } = 1 P - a.s. for 0 < s < t < T, and (ii) E{qt8(f)\T8} = 1 P - a.s. for all 0 < s < t < T. For further details on this topic see Friedman [41], [42]. However, we must mention that the process {
dqh = qt>(f,dW), and that o = l + [ (q9of,dW(6)),t>0. (2.114) Jo It follows readily from Ito formula that the solution of this equation is given by (2.113) with 5 = 0. The formula presented in theorem 14, is known as the Girsanov formula. Similar formula was discovered by Cameroon and Martin in their study of nonlinear transformation of Wiener processes see [41]. We conclude this chapter after we have briefly mentioned two applications. If the drift coefficient b is merely bounded measurable, the existence theory given by theorem 3 does not hold. There is no strong solution either. However Strook and Varadhan [71] showed that weak solutions (martingale solution) exist in the sense that there exists a probability space (O, T, P , Tt T) on which an Tt Brownian motion W is defined such that the pair (£, W) is a solution of the equation df = b(t,£)dt + a(t,0dW,Z(o) = x. (2.115) More specifically, suppose that a satisfies the assumptions of theorem 3. Then it follows from this theorem that equation d£° = 0~(t,€o)dW(t),£o = x, has a unique solution which induces a measure ii° on the measurable space (C, B(C)) where B(C) denotes the Borel sigma algebra on C = C(I,Rn) containing all cylinder sets. Define 9°(0 = expij{a-\
dW) - (1/2) j
l^&fdi}.
If a is nonsingular and a~lb is bounded measurable, then the measure fi given by dpi = q°d\x° is a probability measure on (C,B(C)) giving us the probability
Stochastic Differential Equations
52
space (C, B(C), fi). Then one can show that W{t) = W{t) - f (a-^is^^ds.t Jo
e J,
is a Brownian motion on this probability space. Hence the conclusion follows. For details see Strook-Varadhan [71]. Another application is found in control theory with discontinuous drift. It is well known that an optimal feedback control law for even an elementary time optimal control problem is, in general, discontinuous. For example, the feedback control u(t) = F(£(t)) that drives the system (d2£/dt2) = u,-l< u(t) < + 1 from any given state to the origin (£, £) = (0,0) in minimum time, is discontin uous. If it is perturbed by additive white noise, we obtain an Ito equation and the time optimal feedback control law F for the deterministic system is also optimal for the stochastic problem. In general, consider the control problem d£ = 6(f, u)dt + a(£)dW, f (0) = f0.
(2.116)
The problem is to find a feedback control law that minimizes the functional J(u) = E{[ Jo
£&u)dt}==E{i&u)},
subject to the constraint that u must take values from a compact metric space U. Letting [i (same equation with drift removed) respectively, the problem can be reformulated as : find u that minimizes the functional
J(u)= [ Jc
m^qZiu)}^).
Under quite general assumptions that include bounded measurable drifts, one can prove the existence of optimal feedback controls from a suitable class of control laws. This line of approach is due to Benes, Varaiya, Duncan and Davis see [5] and the references therein. All that is required for existence of optimal controls in this setting is that the set V = {"(£) = £(£, u)qZ(u)(0,
u € Uad}
Linear and Nonlinear Filtering
53
be a weakly sequentially compact subset of Li{C,Bc,Hi) and that u —► gu satisfies certain appropriate convexity condition. This is combined with the idea of measurable selections to complete the proof. The set V is weakly sequentially compact if it is bounded and uniformly integrable, that is,
lim
ft/V(0W(de)=O
uniformly with respect to u € Uad- Further details is beyond the scope and purpose of this book see [1], [5]. Though this is a remarkable generalization, it has also serious limitations. The diffusion parameter a must be invertible (nonsingular square matrix) and must not contain controls, both considered very unrealistic for applications. This is a limitation of the Girsanov approach. It is not clear if Girsanov approach can be extended to overcome these difficulties. This is an interesting research problem.
55
CHAPTER 3 K A L M A N FILTERING FOR LINEAR S Y S T E M S D R I V E N B Y W I E N E R PROCESS-I
3.1 Introduction In all fields of studies including physical and engineering sciences and also economic and social sciences, scientists make measurements and collect data to understand and interpret the underlying phenomenon which is not directly ac cessible or observable. However the fundamental properties of the phenomenon may be sufficiently reflected in the measured or observed data provided they are carefully collected. On the basis of the available data scientists must discover the underlying phenomenon. This is generally known as scientific inference. A phenomenon may be described or characterized, as it evolves with time, by a vector valued function which may be called the state process. The funda mental problem of filtering is to estimate this process at any given time on the basis of available data or information upto that moment of time. This is generally known as filtering. There are two other concepts related to filtering. These are extrapolation (or prediction) and interpolation. In this chapter we consider continuous time Kalman filtering for linear systems driven by Wiener processes. In other words both the underlying (inaccessible) process and the measurement (or observed) process are governed by linear stochastic differen tial equations. Here we derive the original Kalman filter equations based on the approach given by the author and his students in [1],[2] and [11] using basic calculus of variations. We conclude this chapter with an extension of the filter theory to prediction problems. 3.2 System Dynamics The system is assumed to be governed by the following linear stochastic differential equation, dx(t) = A(t)x(t)dt x(0) = x
+
a(t)dW(t)
0,
Kalman Filtering I
56
where xo is a random n-vector and {x(t),t > 0} is the state process. The elements of the matrix A(t) are locally integrable and those of a(t) are locally square integrable functions taking values from the space of matrices M(n x n) and M(nxp) respectively. Let M+(n xn),n € N, denote the space of positive symmetric matrices. The initial state is a Gaussian random vector in Rn with mean E{XQ) = XQ and covariance matrix Po given by
(Pof,0 = £(*o-5:o,0 2 -
(3'2)
The process {W(t), t > 0} is a Brownian motion with covariance matrix Q(t) — tQ, t > 0, for some Q G M+(p x p), given by (QZ,0 = E(W(1)J02.
(3.3)
3.3 Measurement Dynamics The measurement dynamics is given by dy(t) = H(t)x(t)dt
+ a0(t)dV(t),t
2/(0) = 0.
> 0, (3 4)
'
Thus the measurement process is given simply by the integral of the trans formed state process corrupted by measurement noise. Here y takes values y(t) € Rm and the matrix valued functions H(t) and <7o(£) take values from the space of matrices M(m x n) and M(m x m) respectively. The elements of H are locally integrable and those of <7o are locally square integrable. The measurement noise process {V(t),t > 0} is an m-dimensional Brownian motion with covariance R(t) = tR, t > 0, given by (Rr,,V) = E(V(l),r])2),V€Rm,
(3.5)
where R G M+(m x rn). Later, we assume this matrix to be positive definite. Throughout the presentation here we shall also assume that the matrix <Jo(t) is also nonsingular for all t > 0. 3.4 Problem Formulation Given the history of the process {y(s),0 < 5 < £}, we wish to find the best estimate of the state x at time t, that is, x(t). Throughout this book,
Linear and Nonlinear Filtering
57
by best estimate is meant unbiased-minimum-variance (UMV) estimate. Since the observed process y is corrupted by noise, any trace or history observed is a matter of chance. Thus mathematically it is often convenient to denote this history by the smallest sigma algebra T\ with respect to which it is measurable. We may call T\ the information sigma algebra. We show that the best estimate is given by the conditional expectation x(t) EE
E{x(t)\J?}.
Indeed let {rj(t),t > 0} be any other Rn-valued .^-adapted random process having finite second moment so that Er}(t) = Ex(t),Vt
>0,
thereby satisfying the requirement that it is unbiased. Then for every u e Rn, we have j(v)
E^v(t)-x(t),u)2\^
=
= #{(»,(*) - m + m - x(t),u)2\??} - x(t),u)2|JTf|
= E((r,(t) +
+ £?/(£(*) -
x(t),u)2\f?}
2E((r,(t)-x(t),u)(x(t)-x(t),u)\F?\.
Since both rj(t) and x(t) are T^ adapted, it follows from the properties of conditional expectations ( see chapter 1) that
SJMO -x(t),«)2|*?} = (v(t) - x(t),u)2 and similarly Ei(ri(t)-x(t),u)(x(t)-x(t),u)\F?} = (V(t) -x(t),u)EUx(t)
-x(t),u)\J*\
= 0. Thus J(V) = (rj(t) - x(t)^)2
+ El{x(t)
- x(t),u)2\Fyt
J
Kalman Filtering I
58
for all u e Rn and t > 0. The only choice variable here is 77. Since u e Rn is arbitrary, it is clear from this expression that J(rj) attains its minimum for 77 = x. This proves that the best estimate of x(t) is given by its conditional expectation x(t) as stated earlier. Here we merely wish to construct a process z(t),t > 0, which is adapted to T\ satisfying the UMV philosophy. Thus we must have Ex(t) = Ez(t)
Vt>0,
. . . . . . and E \\ x(t) - z(t) ||22—> . Minimum,
w
(3-6)
V_ t >, 0
3.5 Derivation of Optimum Filter
Since we are interested in constructing a linear recursive filter, the filter dynamics must be of the form dz = G(t)z(t)dt + r(t)dy, t > 0, _ _
(3-7)
Hence our problem now is to choose the matrices G and T so that the con ditions (3.6) are satisfied. Henceforth, we shall assume that {xo,W, V} are uncorrelated. Define the error process {e(t),t > 0} by e{t) =x{t)-z{t).
(3.8)
Then subtracting equation (3.7) from equation (3.1), it is easy to verify that the error process satisfies the stochastic differential equation de = {A - TH)edt + (A - G - TH)zdt■+ adW - Ta0dV, ZQ
e(0) = e 0 = x(0) - xo,
=
Xo.
where, for convenience, we have omitted the argument t though all the variables in equation (3.9) are functions of time. Let $r(£> s),0 < s 0. Then using this transition matrix we can express the solution of equation (3.9) by e(t) = *r(*>0)eo+ / $r(t,s)(A(s) - G(s) Jo + M(t),t>0; pt
M{t)=
I $r(t,s)<7(s)dWJo
F(s)H(s))z(s)ds
pt
/ Jo
$r(t,s)r(s)a0(s)dV(s).
(3.10)
Linear and Nonlinear Filtering
59
Note that E{e0} = 0 and E{M(t)} = 0. Therefore, since the process {z(t),t 0} cannot be identically zero, for unbiased estimate we must have G(t) = A(t) - T(t)H(t)
Vt > 0.
>
(3.11)
Thus the filter dynamics given by equation (3.7) must take the form dz(t) = (A(t) - T(t)H(t))z(t)
+ T(t)dy, i > 0,
_ _ ZQ = Xo-
(6.12)
Clearly the process z so determined is adapted to the observed process y. Thus the only remaining unknown to be determined is the matrix valued function r(£), t > 0. As a consequence of this choice, the dynamics of the error process e given by equation (3.9) reduces to de = (A - TH)edt + adW - Ta0dV, (3 13) rt* ' e(0) = e 0 . Now we must exploit this equation to minimize the error variance. The error covariance matrix is defined by (tf(t)£,£) = £ ( e ( t ) , £ ) 2 , £ € i r \
(3.14)
and it is easy to see that TrK(t) = E{\\ e(t) | | 2 } . Let || rj \\ or simply \rj\ denote the standard Euclidean norm in Rn for any finite positive integer n. The problem then is to find a matrix valued function r ° , possibly from the class L^ c ([0, oo), M(n x m)), at which the functional J ( r ) = E [ || e(t) ||2 dt = / TY(K(t))dt, Jo Jo
(3.15)
attains its minimum for every finite T. In general we will find it useful to consider a slightly more general cost functional than that presented by (3.15). This is given by J ( T ) = / TV(ft(t)K(*))dt, (3.16) Jo where Q, G L^I^M^n x n)). Using the transition operator $r> it follows from equation (3.13) that the expression for the error is now given by e(t) = $T(t,0)eo+
[ $r(t,s)a(s)dW(s) Jo
- [ $r(t,s)r(s)ao(s)dV(s),t Jo
> 0. (3.17)
Kalman Filtering I
60
To find the expression for the error covariance we compute E(e(t),£)2 for arbitrary £ € Rn. Since the processes {xo, W(t),V(t),t >} are uncorrelated, all the three components in (3.17) are statistically independent each having zero mean. Thus the cross terms vanish and hence, for any £ € Rn, we have E{(e(t),02
2 0,*'r(t,0)0 }
+ I (Qa (s)$'r(t,s)t,a + / (R*0(s)r Jo
(s)$'r(t,s)£)ds
(s)$r(t,s)Z,aQ(s)r
^ ^
(s)$r(t,s)0ds,
where (') denotes the transpose of a matrix. Using the definition of the matrix valued function K we have (K(t)£,Z) = E{(e0,$'r(t,0)02}
+ f (Qa
(s)$'r(t,s)Z,
Jo
+ / Jo
(Ra'0(s)r'(s)$'r(t,s)Z,a0(s)r\s)$'r(t,s)Ods.
(3.19) Differentiating the expression (3.19) with respect to £, it is easy to verify that
{k{t)t,Z) = (K(t)^ (A - FHU) + (K(t)(A - THU,Z) + ((
(3.20)
n
(ff(0)£,O = (JteO, V teR . For the sake of compactness in notation let us write Q(t) = a{t)Qa{t)
and R{t) =
(3.21)
Since (3.20) holds for all £ € Rn, it follows from (3.20) and (3.21) that K satisfies the following differential equation in M+(n x n) given by K(t) = {A- TH)K(t) + K(t)(A - TH)' +Q + rRf K(0) = K0 = Po-
,t > 0,
}=E{(e
Let r ° denote the optimum filter gain, and K° the unique solution of equation (3.22) corresponding to T". Then clearly, J ( r ° ) < J(V° + e ( r - T°)) V r € L o o ( / , M ( n x m ) )
and V e e R. (3.23)
Linear and Nonlinear Filtering
61
This suggests that the function (e) = J ( r ° 4- e(T - T°)),e € R,
(3.24)
attains its minimum at e = 0 and hence {d/de)(j)\£=Q = 0.
(3.25)
Let K£ denote the solution of equation (3.22) corresponding to Te = r ° + £ ( r T°), that is,
K£(t) = (A-
( r ° + e(F - T°))H)K£{t)
+ K£(t)(A
- (T° + e(T -
T°))H)'
+ Q + (r° + e(r - r°))£(r° + e(r - r°))', t > o, £
K (0) = K 0 = P 0 . (3.26) Define K(t) = lim(l/e) ( x £ ( t ) - K°(tf).
(3.27)
Replacing K by If ° corresponding to Y = T° in equation (3.22) and subtracting equation (3.22), so obtained, from equation (3.26) and dividing by e and letting e —> 0, it is easy to verify that K satisfies the following variational equation
(d/dt)K(t)
= (A-
T°H)k{t) +
+ K(t){A - T°HJ + ( r - r ° ) [R(T°)' - HK°] \r°R-K0H'){T-T°i,*>0,
K(0) = 0. (3.28) Thus K is the directional derivative of K at r ° in the direction T - T 0 . By virtue of (3.15) and (3.24) we can write 0(c) = j
Tr{Sl(t)K£{t))dt,
where K£ is the solution of equation (3.26). Differentiating this with respect to its argument and setting e = 0 and using equation (3.25) we arrive at the following identity
dJ(r°, r - r°) = / Tronic) dt = o,
(3.29)
Kalman Filtering I
62
where d J{T°, T — T°) denotes the directional or the Gateaux derivative of J at T° in the direction r - T°. Since this holds for every finite interval I and every ft e Loo(/,M^"(n x n)), it is necessary that K(t) = 0 for all t e I and for all T G 1/00(7, M(n x ra)). In other words, the solution of the variational equation (3.28) must be identically zero for all admissible T. This is possible if and only if the inhomogeneous terms in equation (3.28) vanish for all t e I. But since T e Loc(I, M(n x ra)) is arbitrary this is possible if and only if the factor T°R-K0H'
=0.
(3.30).
This clearly implies that its transpose given by R(T°) — HK° also vanishes identically for alH > 0. Since R is nonsingular, it follows from this that T° = K°H,R-1.
(3.31)
Substituting this in equation (3.22) corresponding to optimum r ° , as repro duced below,
K°(t) = (A- r°H)K°(t) + K°(t)(A - r°H) + Q + r°£(r°)
(3.32)
K(0) = tfo, we obtain the differential (matrix) Riccati equation K°
= AK°
+ K°A
K°H'R-1HK°,
+Q-
(3.33)
K°(0) = K0. Thus we have proved the following result. T h e o r e m 1 Suppose the elements of the matrices {A(t),H(t),t > 0} are locally integrable, and those of {a(t),cro(t),t > 0} are locally square integrable, W and V are Wiener processes having incremental covariances Q G M+(n x n)andR € M+(m x m) respectively with R being nonsingular. Fur ther, suppose that the initial state has finite second moment, E \\ x$ || 2 < oo, and that {XQ,W, V} are uncorrelated. Then the best (UMV) linear filter is given by the following set of equations: dz(t) = A(t)z(t)dt
+ K°HR-1{dy{t)
-
H(t)z(t)dt) (j.u4J
z(0).= x 0 ,
where the error covariance matrix K° is given by the solution of the matrix Riccati differential equation K°
= AK°
K°(0) = K0.
+ K°A
+ Q -
K°H'R-1HK°,
(3.35)}
K
Linear and Nonlinear Filtering
63
Proof. It follows from equations (3.31) and (3.32) that the optimum error covariance matrix K° is given by the solution of equation (3.33). Using the expression for T° from equation (3.31) into equation (3.12) we obtain equation (3.34). QED Remark In case xo is Gaussian with mean XQ and covariance PQ, it is known that the Kalman filter is given by exactly the equation (3.34). Hence by unique ness of solutions of stochastic differential equations we have
z{t) = E{x(t)\J?}. In a later chapter we shall see that the procedure used here also applies to stochastic differential equations driven by martingales and not just by Wiener martingales. Stationary Case: In case the matrices {A, a, H, CTQ] are all constant, a sta tionary filter can be designed using the solution of the algebraic Riccati equa tion given by AK° + K°Af + Q - K°HfR-lHK° = 0. (3.36) Suppose Q can be written as Q = (3/3 . Then Q = (a(3)(a/3) . Now assume that (A, H) is observable and (A, a(3) is controllable. Then the algebraic Riccati equation (3.36) has a unique positive definite solution K°. This problem is dual to the classical infinite horizon linear quadratic regulator problem (see [1]). Defining
r° =
K°H'{R)-\
it follows from the above equation that A0K° + K°A0 = - E
(3.37)
where A0 = (A-T°H) and E = (5-^-^ 0 J R(^ 0 ) , . This is the celebrated Lyapunov equation. If E > 0, it follows from Lyapunov theory that A0 and hence AQ is stable in the sense that all its eigenvalues have negative real parts. Thus, the stationary filter given by dz = A0zdt + T°dy is stable. Given the equation (3.35) with the information, Q € M+(n x n),R € M+(m x m) and R > 0, one may question if it has a unique solution satisfying the natural positivity property. The answer to this question is given in the following theorem.
Kalman Filtering I
64
Theorem 2 Under the assumptions of theorem 1, the matrix Riccati equation (3.35) has a unique absolutely continuous solution K e C(I,M+(n x n)). Proof. Since integrable functions can be approximated by a sequence of con tinuous functions, without loss of generality we assume that all the matrices {A, cr, H, ao} are continuous functions of time. Further, recall that CFQ is always assumed to be nonsingular. Write equation (3.35) in the form K = F(t,K) where F denotes the expression on the right hand side of the same equation. Notice that on the space of square matrices denoted by M(n x n), F is locally Lipschitz in the sense that for every finite positive number r, there exists a function hr G L* (I) D C(I) such that || F(t,K)
- F(t,L)
||< hr(t) \\K-L
||, Vt € /
and V K,L 6 Ms(n x n) satisfying || K ||, || L \\< r. The function hr is given by
M*) = 2(||A(t)||+r||/r(t)ll 2 IIW*))- 1 ll)Thus it follows from a classical existence theorem for solutions of differential equations with continuous (right hand side) F, that equation (3.35) has a unique absolutely continuous solution on the maximal interval of existence say, [0,r), T T || K(t) ||= +00. The question is, can the solution be continued beyond r and till the given time T. We show that blow up does not occur. First note that if equation (3.35) has a solution then it is necessarily positive. Indeed, let L denote this solution and define G = LH'R~l. Then the equation for L can be written also as L = (A - GH)L + L(A - GHJ + Q + L(0) = K0.
L{HR-lH)L, (3 38)
'
Let ^AitjS) and ^G(t,s) denote the transition matrices corresponding to the matrix valued functions A and A - GH respectively. Then the solution L must satisfy the integral equation L(«) = *G(t,0)ifo*G(*,0)
+ / ^G(^ 5 ){Q(s) + L( 5 )(^ , ( 5 )^- 1 (5)^( 5 ))L( s )}^ G (t,s)d S . J0
(3.39)
Clearly the expression appearing within the curly brackets is symmetric and positive semidefinite, independently of whether L is positive or not. Since
Linear and Nonlinear Filtering
65
KQ > 0 and tyc(t,s) is nonsingular, this implies that L > 0. This proves the positivity. Further, it follows from the following expression L(t) = 9A(t,0)K09'A(t,0)+
I
*A(t,s)Q(s)*A(t,s)
Jo
-
r^(t, 5 )L( 5 ){if , ( 5 )^- 1 ( 5 )^( 5 )}L( 5 )^(t,s)d 5 ,
Jo
<*A(t,0)K0*'A(t,0)
+ / Jo
*A(t,8)Q(s)*'A(t,s),
that L is bounded above by a positive matrix valued function. Using these lower and upper bounds we conclude that blow up cannot occur. Hence the solution can be continued indefinitely. For integrable functions {A, Q,H, R}, one uses the approximating sequence {An,Qn,Hn,Rn} which is continuous and the Lebesgue dominated convergence theorem (theorem 8, chapter 1) to complete the proof. This gives an outline of the proof. For further details see [1, Theorem 6.3.11]. QED 3.6 S o m e E x a m p l e s E x a m p l e 1 Here we present a simple practical example from aerospace. In the absence of noise, a spin stabilized spherical satellite in geo-synchronous orbit can be approximately described by the following set of equations, Ip + LJ0Ir = Ti Iq = T2
(3.40)
If -u>oIp = T 3 , where I is the mass moment of inertia, UQ is the spin rate of the earth, {p, q, r} are the angular velocities of the satellite and {Ti,T2,Ts} are the external torques acting on the satellite. Hence the angular positions or the attitude angles of the satellite, denoted by {#i, 62l #3}, are given by 0 1 = p , 02 = q, 03=r
.
(3.41)
These equations are valid in the absence of any disturbance. However in reality the satellite is subjected to various random forces generated by solar pressure, random movement of micro meteorites, geomagnetic forces etc. In this situa tion the system is more precisely described by a stochastic differential equation as follows:
66
Kalman Filtering I dp = -u0r
dt + {TilI) dt + (1/J) d i ^ ,
d? = (T2/I) dt + (1/7) dw2l
(3.42)
dr = o;0p dt + (T 3 /7) dt + (1/7) dw 3 , where {A = (Tx//), / 2
2 //),
/ 3 = (T 3 //)}
are the mean forces. Introducing measurement noise, equation (3.41) takes the form d0\ — p dt + dv\, d02 = qdt+
dv2,
d03 = r dt+
dv 3 .
(3.43)
Finally equations (3.42) and (3.43) can be written in the following compact form dx = Ax dt + f dt + a dW, x(0) = x 0 (3.44) dy = Hxdt + a0 dV, y(0) = 0 , where the matrices {A, a, H, cr0} are easily identified from equations (3.42) and (3.43). In this case the filter equation is given by dz = Azdt + f(t)dt + T°(dy - Hz dt), z0 = x0,
(3.45)
where T 0 is the optimum gain matrix determined by the equations (3.31) and (3.33). Note that the presence of the deterministic force / in the system equation does not change the Riccati equation (3.33); it appears only in the filter equation given above. E x a m p l e 2 Here we present a problem arising in digital communication. A binary signal s(t) which takes on the values + V or — V is a modulating signal for a Phase Shift Keying (PSK) system. The PSK wave form is given by sP(t)
= D cos[u0t + (t)\
(3.46)
in which D is a fixed amplitude, U)Q is the carrier frequency, and the phase 0 = 0 for s(t) = +V and 0(t) = IT for s(t) = — V. Then equation (3.46) can be written in the alternative form sP(t)
= (s(t)/V)D
= 7(0/(0,
cosujot
= (T
Linear and Nonlinear Filtering
67
where f(t) = D cosc^ot and ^(t) takes on one of the values -hi or — 1 during each bit period, say, T. This is the signal that is transmitted over a Gaussian channel. The received signal (at the receiver) y is given by dy = l(t)f{t)dt
+ aodv, 2/(0) = 0,
(3.48)
for t € [0,T] or any interval of the form [fcT, (fc + l)T],fc e N. Here v i s a standard Brownian motion and &% is the noise power density. The problem is to design a receiver that gives the best estimate of 7 at the end of each bit period on the basis of the received signal y over that period. This is a filtering problem. Since 7, over any bit period, is a constant, -hi or — 1, for the state equation we can take dx(t) = 0, t G [0, T], x(0) = x0.
(3.49)
Here everything is scalar, with A = 0,cr = 0 and H = f. Using (3.35) and (3.34) one can easily write the equations for error covariance fc and the esti mator 7 as follows k = -(f2(t)/*i)k2,
*(0) = fc0,
2
d7(t) = -{h(t)f {t)/ol)Kt)dt+
{k{t)f{t)/al)dy.
(3.50)
Solving for k we have k(t) =
r-^
■
(3-51)
(l + fco/oVW/^W) Defining g(t) = k(t)(^-J^-), the solution for 7 is given by
7(t) = 7o exp{- J
g(e)d0)} + j
exp-
{J
g(6)de}
(k(s)f{s)/a^jdy{a).
This is the best estimator. Define d
, , / ^ = \
+ 1 , for 7] > 0 -l,for„<0.
The optimum receiver is then given by the estimator followed by the de cision function d giving s(t) = d(7(T)). Note that at the end of each sampling
Kalman Filtering I
68
period, the estimation error is given by k(T) = n+kom2T/2a'>)i indicating re duction in error with increased signal to noise ratio, a fact well known to communication engineers. 3.7 Prediction Problem Here we consider the prediction problem: find the best estimate of the state at time t + a, a > 0, given the information sigma algebra T^ upto time t. Clearly, according to the basic theory developed here this should be given by xa(t) = E{x(t + a)\7?}. (3.52) By the properties of the conditional expectation operator this can be evaluated as follows: E{x(t + a ) | * ? } = E^E{x(t
+ a)|^t+a
}|*i}
= E{x(t + a)\f?}. It follows from equation (3.34) and the comment following this equation, that x(t) satisfies the differential equation dx(t) = A{t)x(t)dt + K°H'R-l{dy(t)
-
H(t)x(t)dt)
x(0) = x 0 .
(3.54)
Using the innovation process H)
=J
H(s)x(s)ds\
which is an T± Brownian motion having the same covariance as that of V, we can rewrite equation (3.54) as dx(t) = A(t)x(t)dt
+
K°H'R-l<Jo{t)dV(t),
x (0) = x0. Integrating this equation and using (3.52) and (3.53) we have xa(t) = $A(t + a, t)x(t), t > 0,
(3.55)
(3.56)
where $A denotes the transition operator corresponding to A(t),t > 0. Thus the optimum predictor is just the extrapolation of the optimum estimator. In other words, the optimum prediction operator is the composition of two operators, the estimator followed by the transition operator. We leave it as an exercise for the reader to compute the prediction error as a function of the system matrices.
69
CHAPTER 4 K A L M A N FILTERING FOR L I N E A R SYSTEMS D R I V E N B Y W I E N E R PROCESS-II
4.1 Introduction In this chapter we again consider continuous time Kalman filtering for lin ear systems driven by Wiener processes. However in contrast with the preced ing chapter, here the measurement dynamics is governed by a genuine stochas tic differential equation. We consider two situations: (A) and (B). In (A) the system dynamics is independent of the observed process but the measurement dynamics is governed by a genuine stochastic differential equation unlike in chapter 3. In (B) both the systems are fully dynamically coupled. 4.2 System and Measurement Dynamics (A) The unobserved process {x(t),t > 0} is again governed by the same linear stochastic differential equation, dx(t) = A(t)x(t)dt
+
a(t)dW(t)
(4.1)
x(0) = x 0 ,
as in the preceding chapter. However the measurement or the observed process is governed by the following stochastic differential equation dylt) = C(t)y(t)dt
+ H(t)x(t)dt
+ a0(t)dV(t),
t>0, (4.2)
1/(0) = 0 .
System (4.2) is a genuine stochastic differential equation whereas in chapter 3, C = 0 and hence the observed process y was merely the integral of the state process modulated by H. Thus the measurement process here is truly dynamic in contrast with the integral observation used in basic Kalman filtering. Here, the same basic assumptions as given in the preceding chapter apply. For the
70
Kalman Filtering II
matrix valued function C, it suffices if the entries are locally integrable. 4.3 Problem Formulation Given the history of the process {y(s), 0 < s < i) up to time £, we wish to find the best estimate of the state x at time t. Again we demand the (UMV) estimate. 4.4 Structure of The Filter Since we are interested in constructing a linear recursive filter, the filter dynamics must be of the form dz = G(t)z(t)dt + B(t)ydt + T(t)dy, t > 0, =
XQ
- x
Hence our problem now is to choose the matrices G,B and T so that the estimate z for the state x is unbiased and has minimum variance. 4.5 Solution of the Problem Define the error vector e = {x - z)
(4.4)
as before. Subtracting equation (4.3) from equation (4.1) and using the mea surement dynamics (4.2), we obtain the following stochastic differential equa tion
de = (A - VH)edt + (A-THe(0) = e 0
G)zdt - (B + TC)ydt - Ta0dV + odW,
0.
(4.5) Since the estimated process z and the observed process y are arbitrary, for unbiased estimate it is necessary that the corresponding coefficients vanish, that is, A-TH-G = 0Wt>0, (4.6) K J B + TC = 0 V t > 0. From equation (4.6) it follows immediately that the matrices G and B of the proposed filter equation (4.3) must be chosen as
Linear and Nonlinear Filtering
71
G = A - TH,
(4.7)
B = -TC. Using this in the error dynamics (4.5) we obtain de = (A - TH)edt + adW - T
(t)R(To(t)''.
Interestingly this equation coincides with the error equation (3.13) of the pre ceding chapter. Thus the error covariance matrix K° is given by the solution of the same matrix Riccati differential equation as reproduced below: K° = AK° + K°A
K°H'R-lHK°,
+Q-
0<jQ
K°(0) = Xo, and the optimum gain is given by r° = K°H'R-\
(4.10)
where Q(t) =
a(t)Qa(t)\
R(t) = a0 Using the expressions (4.7), (4.10) and the solution of equation (4.9) into the filter equation (4.3) we obtain the equation for optimum filter dz = (A - T°H)zdt - T°Cy dt + r ° dy, = Azdt + T°(dy -Cy
dt - Hzdt),
(4.11)
z(0) = xoIntroducing the innovation process we can describe the filter equation (4.11) by an equivalent stochastic differential equation as follows dz = Azdt + T°(j o
= Azdt + Y a0dV,
l
{dy - Cy dt -
Hzdt) (
'
'
where we can show that {V(t),t > 0} is va Wiener process with the same incremental covariance as {V(t),t > 0}. Collecting all this information in the form of a theorem we have the following result.
Kalman Filtering II
72
Theorem 1 Suppose the elements of the matrices {A(t), H(t), C(t),t > 0} are locally integrable and those of {cr(t),cro(t),t > 0} are locally square integrable, the processes {xo, W, V} are uncorrelated, XQ has finite second moment, {W, V} are Brownian motions with {
(4.13)
z(0) = x 0 , where F" is given by T°(t) = K°(t)H'(t)R-1(t)
(4.14)
and K° is given by the solution of the differential Riccati equation
K° = A(t)K° + K°A(t)
+ Q(t) -
K°H\t)R{t)-lH(t)K°,
K°(0) = K0.
(4.15)
Comment 1 We have seen that the optimum filter equation (4.13) can be written as a stochastic differential equation driven by the innovation process as follows dz = Azdt + r°a0dV, (4.16) V J *(0) = x0. This equation can be used to study sensitivity and stability of the filter. 4.6 System and Measurement Dynamics (B) Here we consider a more general model in which the signal and the mea surement processes are governed by a coupled system of stochastic differential equations. The signal (unobserved) process {x(t),t > 0} is governed by the linear stochastic Differential equation, x(0) = x
0,
and the measurement or the observed process is governed by the equation dy{t) = C(t)y(t)dt -I- H(t)x{t)dt
y
+ a0(t)dV(t),t
> 0,
"
(4 18)
-
Linear and Nonlinear Filtering
73
Thus the state and the measurement processes are truly dynamically coupled. Here the same basic assumptions as given in the preceding chapter apply. For the matrix valued function D, it suffices if the entries are locally integrable. Choosing the structure of the filter as given by equation (4.3), our problem is to find the matrices {G, B, T} so that we have an unbiased minimum variance filter. Proceeding as in the previous sections, one can show that for an unbiased estimate we must have G = A - TH (4.19) K J B = D - YC. Again defining the error process e = x — z it is easy to verify that e satisfies the SDE: de = (A- TH)edt + adW - Ta0dV, (4 20) rti\ ' e(0) = x 0 - zo, which, in fact, is the same equation as (4.8). Thus the equation for error covariance remains unchanged. This is given by the solution of equation (4.15). The optimum gain matrix T° is then computed by the expression (4.14). Thus it follows from (4.19) that G0 = 0
B =
(A-T°H), (D-F°C).
The dynamics of the optimum filter is given by dz = Azdt + Dydt + z{0) = z0
T°(dy-Cydt-Hzdt),
0.
=x
Again introducing the innovation process dV = <jQl{dy - Cydt -
Hzdi)
we can rewrite the filter equation driven by the innovation process as follows: dz = Azdt + Dydt + T°<70dV, (4.22) 2(0) =
ZQ
= x0.
Using martingale theory one can verify that V is a Brownian motion having the same incremental covariance as that of V. Thus we have the following result for the most general linear system given by the equations (4.17) and (4.18).
Kalman Filtering II
74
Theorem 2 Suppose the elements of the matrices {A(£), H(t), £>(£), C(t),t > 0} are locally integrable and those of {crit), cro(t), t > 0} are locally square inte g r a t e , the processes {x 0 , W, V} are uncorrelated, #o has finite second moment, {W, V} are Brownian motions with {Q, R} being the corresponding incremen tal covariance matrices respectively. Then, the best (UMV) linear filter for the systems (4.17) and (4.18) is given by the following set of equations dz = (A-
T°H)zdt + Dydt + T°(dy - Cydt)
2(0) = x 0 ,
(4.23)
where r ° is given by r°(t) = K°(t)H'(t)R-1(t)
(4.24)
and K° is given by the solution of equation
K° = A(t)K° + K°A'(t)
+ Q(t) -
K°Hf(t)R(t)-1H(t)K°,
(4.25)
K°(0) = K0. Comment 2 There is only a minor change in the above theory if the sys tem dynamics given by (4.17) is modified by adding an arbitrary T\ adapted process {f(t),t > 0} on its right hand side giving dx(t) = A{t)x{t)dt + D(t)ydt + f(t)dt +
a(t)dW(t)
x(0) = x 0 .
(4.26)
In this case the estimator dynamics given by (4.23) turns into dz = (A-
T°H)zdt + Dydt + f{i)dt + T°(dy - Cydt)
z(0) = x0.
(4.27)
The covariance equation given by (4.25) remains unchanged. This shows that the estimation error can not be improved by any .T7^-adapted additive control However the estimated state process z can be controlled as evidenced by (4.27). Note that f(t) can be any linear or nonlinear Volterra functional of the process y in the sense that f(t) =
F(t,irty),t>0
where irty stands for the history of the process y upto and including time t.
Linear and Nonlinear Filtering
75
C o m m e n t 3 By augmenting the state space and denning £(<) = (x®
) as
the new state, one can reduce the dynamic models (4.17) and (4.18) into the standard form (3.1) and (3.4) of chapter 3. This is given by df = A£dt + ZdW, dy = HZdt H£dt + a0dV, where the matrices A, H, £ and the Wiener process W are given by
* - ( 2 S).«-<»«>-=-(S £)■*■(?)■ However, there is no real advantage in this reduction. In fact, it increases the dimension of the differential Riccati equation. Further, it also introduces correlated noise since W is correlated with the measurement noise V. 4.7 Discussion and Examples We present here a simple prototype example from the field of ecology. The Lotka-Volterra prey-predator model for two species sharing the same habitat is governed by a pair of nonlinear differential equations like: + a2XY
+ a3X2
(d/dt)X
= -aiX -aiX
(d/dt)Y
= piY faY - IhXY (32XY + /?Y2,
/?Y2,
(4.28) (4 28) .
where X(t) and Y(t) denote the predator and prey population at time t. For example, X may represent fox population and Y the population of rabbits. If #2/?2 + otsfc ¥= 0 the system has a unique nontrivial equilibrium {Xe,Ye}. Linearizing the system around the equilibrium, one obtains a linear system describing the population excursion, (x = X - Xe,y = Y - Ye), ffom the equilibrium. This is given by the system (d/dt)x = -ax + py j3y w (4.29) ' (4.29) {d/dt)y = 7J/ - Sx, (d/dt)y = -yy-6x, where a,/?,7 and 6 are constants dependent on the original parameters and the equilibrium. Including migration, parametric uncertainties and fluctuation due to epidemic or other natural phenomenon, one may modify this model to a stochastic system of the form + 0y py + eiiVi (d/dt)x = -ax + w My ' (d/dt)y = jy-Sx + e2N2, {d/dt)y = 72/ - Sx + e2N2,
, _ (4.30) (4.30)
Kalman Filtering II
76
where e\ and e\ denote the intensity of fluctuation while N\ and N2 are two independent standard white noise processes. Letting {w(t),v(t),t > 0} denote the corresponding scalar Brownian motions, model (4.30) can be interpreted as standard Ito equations dx = (ax + (3y)dt -f e\dw
2dv.
dy — (iV — 6x)dt.+ e
The predator population X is evasive and difficult to observe while the prey population Y is easily observable. The problem is to estimate x(t) from the historical data of the observable population {y(s), 0 < s < t}. Thus we can apply the result of theorem 2. Identifying A = —a, D = (3, a = e\ C = j,H
= -6,(70 = e 2 ,
it follows from (4.23)-(4.25) that the equation for the estimate z, defined by the expression z(t) = E{x(t)\Jrf}, is given by
dz = -(a + {6/e2)2k)zdt
+ (/? + (67/fel)k)ydt
- (8/e22)kdy.
(4.32)
The estimation error k is given by the solution of the Riccati equation, k = -2ak - (S/e2)2k2
+ e\.
(4.33)
On the basis of this result one may determine an approximate estimate of the population X(t) by X(t) w Xe(t) + z(t),t > 0. This is approximate since a linearized version of a nonlinear system has been used for filtering. Similar results can be derived for problems involving binary reactions in chemical kinetics [1].
77
CHAPTER 5 D I S C R E T E K A L M A N FILTERING
5.1 Introduction In this chapter we present the basic equations for discrete time Kalman Filtering and conclude with a complete simulation procedure. We follow the derivation given in [83] which is fundamentally similar to that of chapters 3 and 4. 5.2 System Dynamics Let iV = {0,1,2, 3, • • •} denote the index set for the time of events. The system dynamics is governed by x 5 + i = $sxs + Ws,se
N
^0 = so>
where £o is a random n-vector and {xSJ s e N} is the state process, {3>s, s € N} is the state transition operator and {Ws, s £ N} is a sequence of independent Gaussian random vectors with values in Rn. The sequence {Ws,s € N} is assumed to satisfy the following properties: EWS = E(WaWr)
0,seN, (5.A1)
=
Qa6atr,8,reN,
where the covariance matrix Qs e M+(n x n) that is, (Q s £,£) > 0,Vs £ N. The initial state satisfies the following assumptions £
!°
= £f
E(x0x0)
°=°'
(5.A2)
= P0.
Further, it is assumed that the initial state is independent of the dynamic noise sequence {Ws, s G N}, and hence E(x(hWs)=01
VseN.
(5.43)
78
Discrete Kalman Filtering
5.3 Measurement D y n a m i c s Let {zs,s G N} denote the observed process or the measured data which is governed by the following linear system zs = Hsxs + ZQ zo
Vs,seN
(5.2) (5.2)
= 0. = 0.
The matrix Hs G M{m x n), and {Vs,s G N} is a sequence of independent Gaussian m-vectors with known statistical data: £Vss = , , V,,VseN seIV EV £(V Rs6,,r,s,r€N. £(V5V € N. 5Vr) r) = R,6,,r,8,r
(5.44). (5.44).
This is the measurement noise or measurement uncertainty. The covariance matrix Rs G M+(m x m),Vs G N and it is assumed to be positive dehnite, that is, Rs > 0. Further, it is also assumed that the state noise, measurement noise and the initial state are all uncorrelated. Since {Ws} and {V^} have zero mean, this implies that E(V E(V3Wl)=0, Vs,reN, SWI)=0, Vs,reAT, E(Vsx'0o))=0\/5GN. = 0V5GN.
(5.A5) ' '
[
5.4 Problem Formulation Given the apriori estimate (before measurement) of the state at time 5, denoted by £ , ( - ) , we seek an update estimate xs(+) based on the current measurement data zs. To avoid any estimator requiring growing storage of data, one uses a recursive expression that employs the most current data and the preceding estimate to obtain the update. This is realized by requiring the estimator to have the following structure: x5(+) = Bsxs(-)
+ Ksza,s€N, Ksza,seN,
(5.3)
where the matrices {Bs,Ks,sGN,} are time varying weighting matrices to be determined. These are to be determined so as to obtain an unbiased minimum variance estimate (UMV).
Linear and Nonlinear Filtering
79
C o m m e n t 1 If {Ws, Vs, XQ, s € N} are all Gaussian then the linear filter is globally optimal in the sense that, by admitting linear as well as nonlinear estimators, the estimate can not be improved over that given by the linear estimator. Define the estimation errors before and after the measurement as follows xs(—) = xs(—) — xSJ s € TV", before measurement x s (-h) = x s (-f) — xsi s € TV, after measurement.
(5.4)
Substituting these in equation (5.3) we obtain xa{+) = (Bs
SH S
- I)xs + Bsxs(-)
+ KsV31s e N.
(5.5)
By assumption, EVS = 0,5 <E N and hence, if Exs{-)
= 0,
that is, Exs(~)
= Exs,
then we can have an unbiased estimate if and only if BS = (I-KSHS).
(5.6)
Substituting (5.6) into (5.5) and using (5.4) we have x a (+) = (J - KsHs)xs{-)
= x3(-) + K s (z s -
+ K5ys
H3xs(-)).
(5.7)
From this we can now determine the error covariance update as discussed in the following section. 5.5 Error Covariance U p d a t e Define the error covariances before measurement, called time update, and after measurement as follows Ps(—) = E{xs{—)XS(—)')
before measurement
P3(+) = E(xs(+)xs(+y)
after measurement .
4- K
80
Discrete Kalman Filtering
Substituting (5.7) into (5.8) we have, P . ( + ) = E{[(I - KsHs)xs(-) = (I- K.H.)P,{-)(I
+ KSVS][(I ~ KsHs)xs(-) - KSHS)'
+
+ K,V.]'}
(+))
KSRSKS.
where we have used the fact that the state error xs(—) is statistically indepen dent of the measurement noise Vs giving E{Vs(xs(-))'} E{xa(-)Vi}
= E{Vs)E(xs{-)j = 0,
=0
VseN.
Optimum Gain Now we must choose Ks, the so called Kalman gain, so that we have minimum variance estimate. This can be done by minimizing the functional J{KS) = Tr(Ps = Tr((I
- K,H.)P.(-)(I
= Trfpa(-)
- K.H.A
- PS(-)H'X + TT
~ K3HaPs(-)
+TT(KSRSK'S)
+
K.H,P.(-)H'.K'.\
(KSRSK'\
(5.10) Define (e) = J(KS + e r ) , T € M+(n x n).
(5.11)
It is clear that if Ks is optimal then the function 4> attains its minimum at e = 0 and hence its first derivative with respect to e must vanish there. Taking the derivative of (e) =
J{Ks+eT)
= T r { P s ( - ) - Ps(-)H's(Ks+eT)' + (K. + eT)HaPa(-)H'a(Ks
- (Ks +
eT)HsPs(-)+
+ eT)' + {K. + eT)Rs(Ks
+ eT)'}, (5.12)
and setting e = 0 we find that (d4>/de)\e=0 = 2Tr(-Ps(-)H'sT'
+ (KsHsPs(-)H's+KsRs\f\
= 0. (5.13)
Linear and Nonlinear Filtering
81
Since this holds for all T e M+(n x n), it follows from equation (5.13) that PS(-)H'S
= KS(HSPS(-)H'S)
+ KSRS,
Vs G AT,
(5.14)
and since Rs > 0 (that is, Rs is positive definite), it follows from the above expression that Ks = PS(-)H'S (HSPS(-)H3
+ R3\
.
(5.15)
Thus we have the expression for the optimum gain matrix for each time index s e N. Substituting the expression (5.15) into (5.9) we obtain the equation for error covariance update after measurement Ps(+) = (I - KSHS)PS(-)(I = (I-
- KSHS)'
+ KSRSK'S
KSH3)PS(-)
- PS(-)HS'K'S
+ Ks
(HSPS(-)H'3
= (I - KSHS)PS(-)
- PS{-)HS'K'S
+
PS(-)H'X
= (I -
+
R,\K',
KSHS)P3(-),
(5.16) with Ks as given by (5.15). Thus the error covariance update after measure ment is given by PS(+) = (I-KSHS)PS(-). (5.17) 5.6 State Estimate Time Update Since measurement is taken at discrete points of time, it is necessary to make as good an estimate as possible using the system dynamics and the previous best estimate after measurement. The best estimate that one can expect in this situation (that is, in the absence of any measurement data during this period) is given by x5+1(-) = $5x5(+). (5.18) This estimate should be unbiased. Prom the system dynamics we have x s +i = $sxs -{-Ws,se
N.
Subtracting (5.19) from (5.18) we have x s + i ( - ) - xs+i = $ s ( x 5 ( + ) - xs) - Ws,
(5.19).
Discrete Kalman Filtering
82
which is equivalent to x,+i(-) = $sxs(+)-Ws.
(5.20)
Since the estimate xs(+) is unbiased, E x s ( + ) = 0 and, since EWS = 0, it follows from (5.20) that £?xs+i(-)=0, (5.21) that is, {xs(—),s e N} are also unbiased. Thus, in the absence of measure ment, the time update given by (5.18) is a good estimate obtained from the previous best estimate (after measurement). 5.7 Error Covariance Time Update We use (5.20) to compute the error covariance time update. P,+iR =
E(XJ+I(-)X5+I(-)')
Since x
Here we have used the fact that Efx.i+W',} =0.
(5.23)
This follows from the following observation. Let Tl — a{zr,r < s} denote the smallest sigma algebra with respect to which the observation process {zr,r < s} is measurable. Then £{^(+)W:} = E|£?|X.(+)W,'|J7}}. s(-\-)
is Tl measurable, we have
s ji5 |X.(+)W;IJ7}} = £?|x.(+)£?|w:i^;}}. But the sequence {Wk, k > s} is statistically independent of the measurement process {zr,r < s} and hence of the sigma algebra Tzs. Thus
EUVS\?*\=E(WS)
= O.
Linear and Nonlinear Filtering
83
Hence follows (5.23). 5.8 Necessary Equations For Simulation Time update Given the estimates (after measurement) at the previous time index s e TV, we can obtain the time updates from equations (5.18) and (5.22) as given below: £ s + i ( - ) = $sXs(+),
State time update
P s + i ( - ) = $>SPS(+)$S -\-Qs,s e N
covariance time up date .
(5.24)
Optimal Gain: The optimal gain is then computed using equation (5.15) as follows Ks + X = ( p ; + i ( - ) i £ + i ) ( f f , + i P . + i ( - ) i £ + i + * * + i )
•
( 5 - 25 )
Measurement U p d a t e Using equations (5.3),(5.6),(5.16) and the time up dates given above, we obtain the updates after measurement as follows: x8+i(+) = x s + i ( - ) + i i : 5 + i ( v i - # s + i x s + i ( - ) ) P a +i(+) = ( I - K8+iH8+i)P8+i(-),
State
Covariance.
(5.26).
In summary, we have a complete set of equations,(5.24)-(5.26), which can be used to compute all the necessary estimates. This gives us the optimum filter. Comment 2 One should expect improved estimate after each measurement update. This can be verified by comparing the error covariance matrices before and after measurements. From equation (5.26) we have P . + i ( - ) - P.+i(+) = X 5 + i F 5 + 1 P s + 1 ( - ) =
(5.27)
Ps+l(-)#s+l-fr7+l#s+lPs+l(-)>
where Rs+1
= (HS+1PS+1(-)H'S+1
+ Rs+1).
(5.28)
Since .R s+ i > 0, and the term Hs+iP3+i(-)H's+1 > 0, it is evident from (5.28) that Rs+i > 0 and hence it follows from (5.27) that Ps+1(-)
- Ps+1(+)
> 0.
Discrete Kalman Filtering
84
This means that the error covariance can only diminish after measurement update thus reducing uncertainty in the estimate. C o m m e n t 3 Any continuous time model can be approximated by a discrete time model of the form given by equation (5.1). Indeed, consider the system dx = A(t)xdt + dy = H(t)x(t)dt
a(t)dW(t), + a0{t)dV(£), t > 0,
by
and let $(£,s),0 < s < t < oo, denote the transition operator corresponding to the system matrix A(t). Let 0 = to < ti < £2 < • • • < £s < ^+1 • " D e a sequence of points (time instants) at which measurements are taken. Define $ s = $(£5+i>*s)> xs = x(ts) and Ws Ws=
/
*(i a+1> 0)cr(0JdW(0).
Jts
Then equation (5.29a) can be approximated by the discrete time model x s + i = $sxs + Ws,seN,
(5.30)
which is precisely the model equation (5.1). Similarly, one can approximate the measurement equation as follows. Define zs = y(£ s +i) — y(ts), Hs = / / ; + 1 H{9)dQ and Vs = / / ; + 1
+ Vs,8€N.
(5.31)
It is easy to verify that {TVs,s G AT}, is a sequence of independent Gaussian random vectors with mean zero and covariance
QS= [s+1
^{ts+1,e)a(e)Qa\e)^(ts+ue)de.
Similarly, {Vs,s e N}, is also a sequence of independent Gaussian random elements with covariance fts+l rzs+i
Rs =
ao(r)Ra0(r)dr. Jts Frequency of measurements determines the order of accuracy. In engineering practice, measurement is costly and error can be fatal and hence a balance must be sought. For rapidly varying parameters, {^4,
85
CHAPTER 6 L I N E A R FILTERING W I T H CORRELATED NOISE-I
6.1 Introduction In this chapter once again we consider continuous time Kalman filtering for linear systems driven by Wiener processes. However in contrast with the preceding chapters, here the system and measurement noises are correlated. In particular the system noise affects the measurement dynamics. We consider two situations: (A) and (B). In (A) the system (state) dynamics is independent of the observed process and the observed process is only integrally (not differentially) coupled with the state process. In (B) both the system and Measurement dynamics are fully coupled. 6.2 System and Measurement Dynamics (A) The inaccessible or unobserved process {x(t),t a linear stochastic differential equation, dx(t) = A(t)x{t)dt A(t)x(t)dt
+ +
> 0} is again governed by
a!(t)dW{t) a^dWit)
(6.1)
x(0) = xo, x0,
as in the preceding chapter. However the measurement or the observed process is governed by the following stochastic differential equation dy(t) = H(t)x(t)dt 2/(0) = 0. »(0)
+ a3(t)dW(t)
(t)dV(t),t + a4(t)dV{t),t
> 0,
(6.2) (6 2) '
Thus the system noise affects the measurement dynamics. This model reduces to the classical case if 03 = 0. Here the same basic assumptions as given in the preceding chapters apply. For the matrix valued function 03, it suffices if the
86
Linear Filtering: Correlated Noise I
entries are locally square integrable. 6.3 Problem Formulation Given the history of the process {2/(5), 0 < s < t} upto time t, we wish to find the best linear estimate of the state x at time t. Again we demand the (UMV) estimate. 6.4 Structure of The Filter Since we are interested in constructing a linear recursive filter, the filter dynamics must be of the form dz = G(t)z(t)dt + Y(t)dy,t
> 0, (6.3)
Hence our problem now is to choose the matrices G and T so that the estimate z for the state x is unbiased and has minimum variance. 6.5 Solution of The Problem Define the error vector e = (x - z)
(6.4)
as before. Subtracting equation (6.3) from equation (6.1) and using the mea surement dynamics (6.2), we obtain the following stochastic differential equa tion de = {A - TH)edt + (A-TH-
G)zdt + (ax - Ta3)dW - TaAdV ZQ
=
£0.
e(0) = eo = x0 - x 0 Since the estimated process z is arbitrary, for an unbiased estimate it is nec essary that the corresponding coefficients vanish, that is, A-rH-G
= 0Vt>0.
(6.6)
From equation (6.6) it follows immediately that the matrix G of the proposed filter equation (6.3) must be chosen as G = A - TH.
(6.7)
Linear and Nonlinear Filtering
87
Using this in the error dynamics (6.5) we obtain de = (A- TH)edt + (
(6.8)
Let $r(t, s), - o o < s < t < oo denote the transition operator corresponding to the matrix valued function {A{t)-T{t)H). As usual, using this operator we can express the error vector by the following equation e(t) = = *r(*,0)co * r (*,0)co + / * r ( M ) ( * i ( « ) - r(s)
(6.9) (6.9)
Define the error covariance matrix K as before 2 2 (K(t)Z,t) = . (K(t)^,0 = E(e(t),£) E(e(t),0
(6.10)
Using equations (6.9) and (6.10), and the basic properties of the transition operator $ r one can easily show that K satisfies the following differential equation K(t) = (A- YH)K TH)K + + K(A - TH)' + fo + T{c fa - Ta^Qia, Ta3)Q((r1 - Ya Va33j)' + T{a44R*' Ra'44)T )T', ,
(6.11) (6.11)
K(0) = K0 = P0. For convenience of notation let us define the following matrices Q11=<TiQ
= a3Qa[,R44 = a4aRa 4. 4. 4Ra
(6.12) (6 12) '
Note that Q13 = Q31. Using these notations one can rewrite equation (6.11) as K{t) = (A - YH)K + K(A - TH)' + Qn K{t) = (A- YH)K + K(A - TH)' + Qu (6.13) -- Q Q13TT -- TQ' TQ'13 + + r(Q r(Q33 + + RR)f, 44)f, (6.13) 13 13 33 44 K(0) = K . K(0) = K0. 0
Thus following our general philosophy, the problem is to find a T € Loo(/,M(nxm)) T€LooiltMinxm))
88
Linear Filtering: Correlated Noise I
that minimizes the cost functional J(T) = [Tr (QK)dt,
(6.14)
for every bounded interval I and Q G Li{I, M+(n x n)). If r ° G 1,^(1, M(n x m) is optimal, it is clear that J(T°) < J(T° + e(T - r°))
(6.15)
for all e G R and for T G LOQ(I, M(n x m)). Since there are no constraints, this implies that the directional derivative of J at T° in any direction T — T° must vanish, that is, d J ( r ° , r - r o ) = 0 V r e £«>(/,M(nxm)).
(6.16)
Let (j) denote the function 4>{e) = J(Y° + e{Y -T°)),e
e R.
Thus (6.16) is equivalent to {d/d£)(t>{e)\£=o = 0 V r G L o o ( / , M ( n x m ) ) .
(6.17)
Let K£ denote the solution of equation (6.11) corresponding to T = T£ = ( r ° + e(T — r ° ) and K° that corresponding to r ° . Then we have the following pair of differential Riccati equations K£ =(A - Y£H)K£ + K£(A-
T£H)
+ Qn
- QizV)' - (r)Q'l3 + r*(Qs3 + Ru)(r£)\
(6-18)
£
K (0) =K0; and K° =(A - Y°H)K°
+ K°(A - T°H)
+ Qn
- Q i 3 ( r ° ) ' - (r°)Q13 + r°(Q 3 3 + K°{0)
R4A){T°)\
(6.IS)
=K0.
It follows from continuous dependence of solutions on parameters that the following limits exist lim K£ = K° £ "° ~ (6.20) x
\im(l/e)(K£-K°)=K,
Linear and Nonlinear Filtering
89
where K satisfies the following differential Riccati equation
R =(A - Y°H)K + K(A -
r°H)
- (r - T°){HK° + Q'13 - (Q33 + #44) (r 0 )'} 1
J
(6.21)
- \K°H' + Q13 - r°(Q33 + ^44)}(r - r°)\ K(0) = 0. Computing the derivative of 0(e) and using the necessary condition (6.17), we obtain 0 = (d/cte)0(c)U=o = [Tr
{SIK) dt V T e L^I.Mfji
x m)).
(6.22)
Since this holds for arbitrary ft € Li(i", M+(n x n)) and any finite interval 7, we conclude that K = 0. This requires that the solution of equation (6.21) be identically zero, that is, for alH € I. But, for arbitrary T, this is possible if and only if the multiplier of T — T° is identically zero. Since a matrix is zero simultaneously with its adjoint, it follows from equation (6.21) that the expression, IK°H'
+ Q 1 3 - r ° ( Q 3 3 + #44)} = 0,
must hold. Since Q33 > 0 and R44 > 0, Q33 + R44 is nonsingular and hence the optimal gain is given by T° = (Q13 +
K°H')(Q33
+ i? 4 4 )
•
(6.23).
Substituting the expression (6.23) in equation (6.19) we obtain K° =(A - Q13(Q33 + R44)-lH)K°
+ K°(A - Q13(Q33 +
+ (Q11 - Qi3(Q 33 + i ^ r V i s ) " K°H\Q33 K°(0)
+
RAA)'XH)
Ru)-lHK°,
=K0.
(6.24) This is the differential Riccati equation giving the optimum covariance operator K° which when substituted in (6.23) gives the optimum filter gain T°. Thus we have proved the following result.
90
Linear Filtering: Correlated Noise I
Theorem 1 Consider the system dynamics (6.1) and the measurement dy namics (6.2) and suppose the elements of the matrix valued functions {A, H} are locally integrable and those of {cri, 03,04} are locally square integrable with 04 being nonsingular, and further { x 0 , W , F } are statistically indepen dent. Then, the optimum (UMV) linear filter is given by dz = {A-r°H)zdt ft*
-
+ r°{t)dy (2b>
-
z(0) - z0 = x 0 , where T° = (Q13 + K°H)(o33
+ R44)
•
(6.26)
and K° is given by the solution of the differential Riccati equation K° =(A - Q13(Q33 + Ru)-lH)K°
+ K°(A - Q13(Q33 +
+ (Q11 - Qi3(Qs3 + ^44)- 1 Q 1 3 ) - K0H{Q33 K°(0)
+
R^^H) RAA)-lHK°
=K0. (6.27)
Uncorrelated Case The results for the uncorrelated case can be readily derived from the above result. Recall that for the uncorrelated case, 0 - 3 = 0 . Hence the matrices {Qi3>Q3i>Q33} are all zero. In this case equation (6.26) reduces to T0 = {K0H,)(Ruy\
(6.28)
and equation (6.27) reduces to K° =AK° + K°A' + Q n K°(0)
K°H'R£HK°
=K0.
, x (6.29)
These are precisely the equations for Kalman-Bucy filter as given by equations (3.9) and (3.10) of chapter 3. 6.6 System and Measurement Dynamics (B) Here we consider a more general model in which the signal and the mea surement processes are governed by a coupled system of stochastic diflFerential
Linear and Nonlinear Filtering
91
equations. The signal (unobserved) process {x(£),£ > 0} is governed by the linear stochastic differential equation, dx(t) = A(t)x(t)dt , x(0) = x 0
+ D(t)ydt +
a^dWit), ^ '
'
and the measurement or the observed process is governed by equation dy(t) = C(t)y(t)dt
+ H(t)x(t)dt
+ a3(t)dW(t)
+
y(0)-0.
> 0, "
{6 31)
'
Thus the state and the measurement processes are truly dynamically coupled. Here the same basic assumptions as given in the preceding section apply. For the matrix valued functions {A, D, C, H}, it suffices if their entries are locally integrable. Choosing the structure of the filter as: dz = Mzdt + Nydt + Tdy, z(0) = z0 = x 0 ,
(6.32)
our problem is to find the matrices {M,N,T} so that we have an unbiased minimum variance filter. Proceeding as in the previous sections, one can show that for an unbiased estimate we must have M = A - TH N = D - TC.
(6.33)
Again defining the error process e = x — z it is easy to verify that e satisfies the SDE: de = (A - TH)edt + (
(6.34)
e(0) = x 0 - x 0 , which, in fact, is the same equation as (6.8). Thus the equation for error covariance remains unchanged. This is given by the solution of equation (6.19). The optimum gain matrix T° is then computed by the expression (6.28). Then from (6.33) we have M° = {A-T°H), N° = (D-
T°C).
Linear Filtering: Correlated Noise I
92
The dynamics of the optimum filter is given by dz = (A - V°H)zdt + (D - Y°C)ydt + T°dy, z(0) = z0
/
x
(6.35)
0.
Thus we have the following result. T h e o r e m 2 Suppose the elements of the matrices {A(t), H(t), D(t), C(t), t > 0} are locally integrable and those of {cri(£),cr3(£),cr4(£),£ > 0} are locally square integrable with cr^ being nonsingular. The processes {xo,W, V} are uncorrelated, xo has finite second moment, {W, V} are Brownian motions with {Q, R} being their corresponding incremental covariance matrices with R being positive definite. Then the best (UMV) linear filter for the systems (6.30) and (6.31) is given by the following set of equations dz = (A-
T°H)zdt + (D-
T°C)ydt + T°dy,
z(0) = xo,
(6.36)
where T° is given by r° = (Qi3 + K°H')(Q33
+ R44}
,
(6.37),
and K° is given by the solution of the differential Riccati equation
K° =(A - Q13(Q33 + Ri^H)^
+ K°(A - Q13(Qss +
Ri^H)'
1
R^y'HK"
+ ( O H - Qi3(Q 3 3 + R44)- Q'13) - K°H'(Q33 K°(0)
+
=K0. (6.38)
C o m m e n t 1 The filter equation (6.36) can be rewritten with the innovation process as its input, dz = (Az + Dy)dt +
T°^2(t)dW,
z(0) = Zo,
=
where W is an m-dimensional F? measurable standard Wiener process and E ( t ) = (Q33(t)
+
R44(t)\
x
Linear and Nonlinear Filtering
93
This is verified as follows. Define the process V as given by V(t) = y(t) - / C(s)y{s)ds - / H(s)z(s)ds, Jo Jo
t > 0.
(6.40)
Clearly it follows from (6.31) and (6.40) that dV = (dy - Cydt -
Hzdt)
= (H{x - z)dt + a3dW + a4dV).
(6.41)
Using conditional expectations relative to the sigma algebra T\ and Ito formula for stochastic diflFerentials one can verify that {V'(t), t > 0} is a Wiener process with covariance operator given by E as defined above. Then define W by dW = ^-1/2\t)dV.
(6.42)
Clearly W, as defined, is a standard m-dimensional Wiener process. Again, by setting appropriate matrices equal to zero one obtains the clas sical filter equations of chapter 3.
95
CHAPTER 7 L I N E A R FILTERING W I T H CORRELATED NOISE-II
7.1 Introduction In this chapter again we consider continuous time filtering for linear systems driven by Wiener processes. The system and measurement noise are correlated as in the preceding chapter. In the previous chapter, system noise adds to (affects) the measurement noise. However in contrast with the preceding chapter, here the measurement noise affects the system dynamics. We consider two situations: (A) and (B). In (A) the system (state) dynamics is independent of the observed process and the observed process is only integrally (not differentially) coupled with the state process. In (B) both the system and measurement dynamics are fully coupled. 7.2 S y s t e m and Measurement Dynamics (A) The unobserved process {x(t),t differential equation,
> 0} is governed by the linear stochastic
dx(t) = A{t)x{t)dt A(t)x(t)dt + a^dWit)
+
x(0) = x0, x{0) x0,
(7.1)
while the measurement or the observed process is governed by the following stocha-stic system dy(t) = H(t)x(t)dt y(0) = = 0.
+ a4(t)dV(t),t
> 0, >
(7.2)
Comparing with the problem considered in the preceding chapter, the situation here is reversed. Here the measurement noise affects the system noise and hence its dynamics. This model reduces to the classical case if 02 = 0. Clearly the dimension of the matrices must be compatible. For x{t) € Rn, y(t) G Rm,
Linear Filtering: Correlated Noise II
96
W(t) e Rp and V(t) € Rm we must have A(t) e M(n x n), a^t) G M(n x p), (72(t) G M(n x m), J?(t) € M ( m x n) and cr4(t) € M(m x m). Here the same basic assumptions as given in the preceding chapters apply. 7.3 Problem Formulation Given the history of the process {y(s), 0 < s < i) up to time t, we wish to find the best linear (UMV) estimate of the state x at time t. 7.4 Structure of the Filter As usual, we are interested in constructing a linear recursive filter. Thus the filter dynamics must be of the form dz = G{t)z{t)dt + T(t)dy,t > 0, _ _ z0
(7-3)
Hence our problem now is to choose the matrices G and T so that the estimate z for the state x is unbiased and has minimum variance. 7.5 Solution of the Problem Define the error vector e = (x-z)
(7.4)
as before. Subtracting equation (7.3) from equation (7.1) and using the mea surement dynamics (7.2), we obtain the following stochastic differential equa tion
de = (A-
TH)edt + (A-TH-
e(0) = eo = xo — xo-
G)zdt + oxdW + (<72 -
Ta4)dV
= Xo-
Since the estimated process z is arbitrary and cannot be identically zero, for an unbiased estimate it is necessary that the corresponding coefficients vanish, that is, A - TH - G = 0, V t > 0. (7.6) From equation (7.6) it follows immediately that the matrix G of the proposed filter equation (7.3) must be chosen as
Linear and Nonlinear Filtering
97
G = A - TH. TH.
(7.7) (7.7)
Using this in the error dynamics (7.5) we obtain de = (A- TH)edt <jxxdW dW ++ (<J (a22 -- Ta )dV de=(ATH)edt + <j To44)dV e(0) = e0 = x0 - x0.
(7.8)
Let $ r ( ^ s ) , , - c o < 5 < t < 00 denote the transition operator corresponding to the matrix valued function (A(t) - T(t)H(t)). As usual, using this operator we can express the error vector by the following equation 3(i) = = **r(t,0)e r ( t , 0 ) e 00 + f/ (t,s)
(7.9) (7.9)
Define the error covariance matrix K as before 2 (K(t)t,Q = E(e(t),0 E(e(t),tf. (K(t)^0 = -
(7.10)
Using equations (7.9) and (7.10), and the basic properties of the transition operator $ r one can easily deduce that K satisfies the following differential equation K(t) Qo'x + (a (
(7.11)
For convenience of notation let us define the following matrices Qn=(T a2Q(72, Qn = XaQo-' x,R22 1Qo-' 1,R22 = (T R24 = ao22Ra' Ro-' R42= =a4aRa ,R 4, 4,R42 4Ra' 2, 2R 4444= = ao 4Ra' 4Ro' 4. 4.
(7.12)
Note that R24 = R42. Using these notations one can rewrite equation (7.11) as
K(t) K{t) = (A{A- TH)K + K{A K(A - TH)' + Qnxx + R22 - R24 f 24T K(0) = K0. K(0)
- TR24 TR24 ++ ri? TR4 44 f, 4 r', (7.13)
98
Linear Filtering: Correlated Noise II
Thus following our general philosophy, the problem is to find an element Y € L 00 (7, M(n x m)) that minimizes the cost functional J(T)=
fTr(QK)
dt,
(7.14)
for any bounded interval I and Q, € Li(I, M + ( n x n)). Following similar arguments as repeated in the preceding chapters, since there are no constraints the necessary condition for T° £ I>oo(-J\ M(n x m) to be optimal is that the directional derivative of J at T° in any direction T — T° must vanish, that is, dJ(r°,r-r°)=0
V r€Loo(/,M(nxra)).
(7.15)
Let (f> denote the function
cP(e) = j(r° + £ ( r - r ° ) ) , £ e # . Thus (7.15) is equivalent to (d/de)(l>{e)\£=o = 0 V T G £,«>(/, M{n x m)).
(7.16)
Let K£ denote the solution of equation (7.11) corresponding to T = Te = T° + e(T - T°) and K° that corresponding to T°. Then we have the following pair of matrix differential equations K£ =(A - TeH)K£ + K£(A-
T£H) + ( Q n + R22)
- R24(r£)' - (r£)R24 + r £ #44(n'
(7.17)
e
K (0) =K0. K° =(A - T°H)K° + K°(A- T°H) 4- (Qn + R22) - #24(r°)' - ( r ° ) ^ 4 + ^ ^ ( r 0 ) ' K°(0)
(7-18)
=K0.
It follows from continuous dependence of solutions on parameters that the following limits exist lim K€ = K° ~° , (7.19) x V ; \im(l/e)(K£ - K°) =K,
Linear and Nonlinear Filtering
99
where K satisfies the following matrix differential equation
k =(A - Y°H)K
+ K(A - r°H)
-
(K°H
- (r - T°)(HK°
+ R2A -
RA^T°)'\
+ #24 - r 0 ^ ) (r - r°)',
k(o) = o. (7.20) Computing the derivative of (j)(e) and using the necessary condition (7.15), we obtain 0 = (d/de)(e)\€=0 = f Tr (SIK) dt V T e Loo(7,M(n x m)).
(7.21)
Since this holds for arbitrary Ct e Li(I, M+(n x n)) and any finite interval 7, we conclude that K = 0. This requires that, for any T e Lco(I,M(n x m)), the solution of equation (7.20) be identically zero, that is, for all t e I. But this is possible if and only if the multiplier of T — T° is identically zero. Since a matrix is zero simultaneously with its adjoint, it follows from equation (7.20) that the expression K°H + R2A - r°#44 = 0. (7.22) Since #44 > 0, the optimal gain is given by T0 = (R2i + K°H)Rtl.
(7.23)
Substituting the expression (7.23) in equation (7.18) we obtain K° =(A - R24R^H)K°
+ K°(A -
R24R^H)
+ (Q11 + R22 ~ R24R4IR42) ~ K°H\RA4)-lHK° K°(0)
(7.24)
=K0.
Note that #24 #44 #42 = #22 R24R44
=
^2^4
•
Substituting these in equation (7.24), we obtain K° =(A - oialxH)K° K°(0)
+ K°(A - a2a^H)
- K°HR^HK°
+ Qn
=K0. (7.24)'
Linear Filtering: Correlated Noise II
100
This is the differential Riccati equation giving the optimum covariance operator K° which when substituted in (7.23) gives the optimum filter gain r ° . Thus we have proved the following result. Theorem 1 Consider the system dynamics (7.1) and the measurement dy namics (7.2) and suppose the elements of the matrix valued functions {^4, H} are locally integrable and those of {01,02,04} a r e locally square integrable with 04 being nonsingular, and further {xo^W,V} are statistically indepen dent. Then the optimum (UMV) linear filter is given by dz = (A - T°H)zdt + T°(t)dy z{0) = z0
0,
= x
where T° = (R2A + K°H)R^,
(7.26)
and K° is given by the solution of the differential Riccati equation K° =(A K°{0)
<J2<J11H)K°
+ K°(A - <J2(J41H)' -
K°H'R£HK°
+ Qn
=K0. (7.27)
Uncorrelated Case The results for the uncorrelated case can be readily derived from the above result. Recall that for the uncorrelated case, 02 = 0. Hence the matrices {02,^24} are all zero. In this case equation (7.26) reduces to T0 = {K°H'){R4A)'\
(7.28)
and equation (7.27) reduces to K° =AK° + K°A K°(0)
+ Qn -
=K0.
K°HR^HK°,
(7.29)
These are precisely the equations for the Kalman-Bucy filter as given by equa tions (1.9) and (1.10) of chapter 1. 7.6 System and Measurement Dynamics (B) Here we consider a more general model in which the signal and the mea surement processes are governed by a coupled system of stochastic differential
Linear and Nonlinear Filtering
101
equations. The signal (unobserved) process {x(£),£ > 0} is governed by the linear stochastic differential equation. dx{t) = A(t)x(t)dt
+ D{t)y{t)dt +
x(0) = x 00,
(7.30) (7 30) '
and the measurement or the observed process is governed by equation dy(t) = C(t)y(t)dt
+ H(t)x(t)dt H(t)x{t)dt
+ + a4(t)dV(t),t
> 0,
2/(0) y(0) = 0.
(7.31) (7 31) '
Thus the state and the measurement processes are truly dynamically coupled. Here the same basic assumptions as given in the preceding sections apply. For the matrix valued functions {A, D, C, H}, it suffices if their entries are locally integrable. Choosing the structure of the filter as: dz = Mzdt + Nydt + Ydy, Tdy,
(7.32) (7.32)
z(0) z(0) = zo z0 = xx00,
our problem is to find the matrices {M,N,T} so that we have an unbiased minimum variance filter. Proceeding as in the previous sections, one can show that for unbiased estimate we must have M = VA-TH M'A- H N D-TC. N = = D-TC.
(7.33)
Again defining the error process e = x - z ii ii easy to verify that e satisfies the SDE: de = (A - TH)edt + axdW + (
Ya^dV,
(7.34)
which, in fact, is the same equation as (7.8). Thus the equation for error covariance remains unchanged. This is given by the solution of equations (7.18) and (7.23) or equivalently equation (7.24). The optimum gain matrix T° is then computed by the expression (7.23). Then from (7.33) we have M° = N° = (D-
{A-T°H), {A-Y°H), T°C).
Linear Filtering: Correlated Noise II
102
The dynamics of the optimum filter is given by dz = {A- T°H)zdt + {D(D-
T°C)ydt + V°dy, T°dy,
2(0) = = 20 z0 = = x 0.
(7.35)
Thus we have the following result. Theorem 2 Suppose the elements of the matrices {A(t), H(t), D(t), C(t), t > 0} are locally integrable and those of {(n(t),a2(t),a4(t),t > 0} are locally square integrable with 04 being nonsingular. The processes {xo,W,V} are uncorrelated, x0 has finite second moment, {W, V) are Brownian motions with {Q, R} being their corresponding incremental covariance matrices with R being positive definite. Then the best (UMV) linear filter for the systems (7.30) and (7.31) is given by the following set of equations dz = {A(A- T°H)zdt + (DV V ' z(0) = x0, z(0) = xo,
T°C)ydt + + T°dy, >y
y
(7.36) (7.36)
where T° is given by T° K°H')Rr° = {R2 (R24i + K°H')R; 4\ Al,
(7.37),
and K° is given by the solution of the differential Riccati equation a2alxH)K° K° =(A -
+ K°(A - a2a^H)'
K°H R^HK" - K°H'R^HK°
+ Q„ Qu
=K0. (7.38)
Comment 1 The filter equation (7.35) can be rewritten with the innovation process as its input, dz = {Az (Az + Dy)dt + T°o-4(t)dW,
(7.39) (7.39)
w
s(0) = 20,
s(0) = zb,
where W is an m-dimensional J* measurable Wiener process with the same covariance as that of V. This is verified using the same procedure as in the previous chapter. Define the process V as given by V{t) V(t) = y(t) - f C{s)y{s)ds C{s)y(s)ds - f H(s)z(s)ds, Jo Jo Jo Jo
t > 0. ~
(7.40)
K
Linear and Nonlinear Filtering
103
Clearly it follows from (7.31) and (7.40) that dV = = (dy - Cydt -
Hzdt)
= H(x - z)dt + o-idV. a4dV.
(7.41)
Using the conditional expectations relative to the sigma algebra JF* and Ito formula for stochastic differentials, one can verify that {V{t), t > 0} is a Wiener process with the covariance operator given by #44. Then define W by 1 l {t)dV. dW = oi-al (t)dV.
(7.42)
Clearly W, as defined, is an m-dimensional Wiener process with the same covariance operator as that of V. 7.7 Discussions and E x a m p l e s Here we present an example from electrical engineering. For lack of accessibility of terminals, induction coil devices are used to measure currents on overhead electrical lines. The current induced in the induction coil is related to that carried by the primary line. The coupled system is governed by the following pair of equations Li(d/dt)h Li (d/dt)h
+ M(d/dt)I2
+ Rih RJi = Vi,
L2(d/dt)I2
M{d/dt)h + M(d/dt)h
+ + R2I2 = 0,
(7.43)
where h denotes the current in the main line and I2 is the current induced in the induction coil. The source voltage Vt is noisy given by V0 + N0 where V0 is deterministic and represents the original source voltage and N0 is the component induced by other nearby cables. The parameters LUL2 and M are the self and mutual inductances and Rx and R2 are the resistances of the primary and the secondary (induction) cables respectively. The problem is to estimate h from the measurement data on I2- In the absence of perfect coupling LXL2 - M2 ^ 0 and therefore the inductance matrix is invertible and the system (7.43) reduces to the standard form {d/dt)h (d/dt)h
= o n J i + aa1122 / 2 + 6nV0 + buN buN0l
{d/dt)I22 = anii a2ih + (d/dt)I + a22I2 + b21V0 + ^21^0,
(7.44)
where the parameters { a y , 6 y } are easily determined by matrix inversion. Letting 7f and 7 | denote the currents in the absence of noise, defining the varrables
104
Linear Filtering: Correlated Noise II
x = I\ - 1°, y = 72 - I2 and considering N0 to be the standard white noise with v denoting the associated Brownian motion, it is easy to see that the pair {x, y} is governed by the pair of linear stochastic differential equations dx = (anx + a12y)dt + bndv, dy = (a2
22y)dt
ix + a
+ b2idv.
This is a special case of the system given by (7.30) and (7.31). Identifying the parameters A = a n , D = ai2,ai = 0,<J 2 = 611, C = a22,H
= 0.21,0-4 — 621,
and following the equations (7.36)-(7.38) we obtain the estimator equation dz = ( a n - j°a2i)zdt
+ (ai2 - l°Q>22)ydt + j°dy
where the optimum gain 7 0 is given by the solutions of the following equations: k° = 2 ( a n - a 2 1 ( 6 n / & 2 i ) V - ( a 2 i / 6 2 i ) V ) 2 , 7 ° = (611621+a 2 ifc 0 )(l/bl 1 ). The best estimate of I\ is then given by h(t) = Ja°(t) + E{x(t)\F*}
= mt)
+ z(t),t > 0.
For study of electromagnetic interference experienced in high density multilayered printed circuit boards or multicored cables, the dynamics is far more complex requiring partial differential equations of hyperbolic type [6]. How ever, by use of modal approximation one obtains a system of equations of the same form as (7.43). Thus, as illustrated above, one may still apply the results of this chapter to the approximate finite dimensional model.
105
CHAPTER 8 L I N E A R FILTERING W I T H CORRELATED NOISE-III
8.1 Introduction In this chapter once again we consider continuous time filtering for linear systems driven by Wiener processes. Here we treat a fully coupled system in the sense that the state dynamics is coupled with measurement dynamics even in the absence of noise. Further, the state and the measurement noises are also fully coupled. 8.2 System and Measurement Dynamics The process {#(£), t > 0} to be estimated is governed by the linear stochas tic differential equation, dx{t) = A(t)x(t)dt
+ D(t)y(t)dt
+ ai(t)dW(t)
+ a2(t)dV,
x(0) = xo,
(8.1)
while the measurement or the observed process is governed by the following stochastic system dy(t) = H(t)x(t)dt
+ C(t)y(t)dt
+ a3(t)dW(t)
+ a4(t)dV(t),t
> 0, (8.2)
y(0) = o. Comparing with the problems considered in the preceding chapters, the sit uation here is most general. The observable and the unobservable are fully coupled both dynamically and stochastically. This model reduces to all the previous cases if appropriate matrices are set equal to zero. Clearly the di mension of the matrices must be compatible. For x(t) G Rn, y(t) G R™, W(t) e Rp and V(t) G Rm we must have A(t) e M(n x n), a^t) e M(n x p), a2(t) G M(nxm), H(t) G M ( r a x n ) ,
106
Linear Filtering: Correlated Noise III
Here the same basic assumptions as given in the preceding chapters apply. 8.3 Problem Formulation Given the history of the process {y(s),0 < s < t} up to time t, we wish to find the best (UMV) estimate of the state x at time t. 8.4 Structure of the Filter Following the same basic philosophy, the filter dynamics must be of the form dz = M(t)z(t)dt + N(t)y(t)dt + T(t)dy, t>0, _ _ (8-3) ZQ
=
XQ.
Hence our problem now is to choose the matrices M, N and Y so that the estimate z for the state x is unbiased and has minimum variance. 8.5 Solution of the Problem Define the error vector e = (x-z)
(8.4)
as before. Subtracting equation (8.3) from equation (8.1) and using the mea surement dynamics (8.2), we obtain the following stochastic differential equa tion
de = (A - TH)edt + (A-YH
- M)zdt + (D-TC-
+ (d - Ta3)dW + (a2 - r
N)ydt (8.5)
-x0.
Since the estimated process z and the observed process y are arbitrary and cannot be identically zero, for an unbiased estimate it is necessary that the corresponding coefficients vanish, that is,
A-rH-M
=
0Vt>0,
D-rc-N
= ovt>o.
^8'6^
From equation (8.6) it follows immediately that the matrices M and N of the proposed filter equation (8.3) must be chosen as
Linear and Nonlinear Filtering
107
M = A - TH,
J K(8.7)
N = D - YC. Using this in the error dynamics (8.5) we obtain de = (A-
TH)edt + (
e(0) = e0
= xo -
Let $r(£>s),— oo < s < t < oo denote the transition operator corre sponding to the matrix valued function (A(t) - F(t)H(t)). As usual, using this operator we can express the error vector by the following equation 3(*) = * r M ) e 0 + / Jo - [ Jo
9r(tJs)(a1(3)^r(s)a3(s))dW(s) (8.9) $r(t,8){a2(8)-r(s)
Define the error covariance matrix K as before (K(t)t,0
= E(e(t),02,
£€i?n-
(8.10)
Using equations (8.9) and (8.10) and the basic properties of transition operator $ r one can easily derive that K satisfies the following differential equation K(t) = (A-
TH)K + K(A - TH)' + (
- IV3)'
+ (a2 - Ta4)R{a2 - I V 4 ) \
(8.11)
K(0) = K0 = P0. For convenience of notation let us define the following matrices Qn = 0"iQ0"i,Qi3 = criQa3,Q3i = o-3Qo"i,Q33 = cr3Qa3,
(8.12)
R22 = a2Qa2, R24 = a2Ra4l R42 = cr4R<J2, R44 = cr4Ra4. Note that Q\3 = Q31 and R2i = R42- Using these notations one can rewrite equation (8.11) as K(t) = (A - TH)K + K(A - TH)' + (Qn + R22) + T(Q33 + - r ( Q 3 i +R42)K(0) = K0.
(Q13 + Ru)T',
i W (8- 13 )
XQ.
108
Linear Filtering: Correlated Noise III
Thus following our general philosophy, the problem is to find an element T € Loo(I,M(n x m)) that minimizes the cost functional J(T)=
(8.14)
[Tr(nK)dt.
for any bounded interval I and 12 € Zq(J, M+(n x n)). Following similar arguments as in the preceding chapters, the optimality condition is given by dJ(r°,r-r°)=0
V r €£«>(/, M ( n x m ) ) .
(8.15)
Let <j> denote the function 4>(e) = J(T° + e(r - T°)), e € R. Thus (8.15) is equivalent to (d/de)4>{e)\e=0 = 0 V r 6 L 0 0 ( 7 , M ( n x m ) ) .
(8.16)
Let Ke denote the solution of equation (8.11) corresponding to T = T£ = T° + e(r - r°) and K° that corresponding to T°. Then we have the following pair of matrix differential equations, Ke =(A - T€H)K£ + Ke(A-
T£H)' + (Qu + R22)
- (i? 24 + Qi 3 )(r £ )' - (Te)(R24 +
Q13)'
+ r £ (Q 3 3 +
RA4)(T£)',
(8.17) and K° =(A - T°H)K° + K°(A - r°H)
+ (Qu + R22)
- (Q13 + fl24)(r°)' - (r°)(Q13 + R2ij + r°(Q 33 + ^ X r 0 ) ' , K°(0)
=K0.
(8.18) It follows from continuous dependence of solutions on parameters that the following limits exist lira K£ = K° lim(l/e)(K£-K°)=K,
(8 19)
'
Linear and Nonlinear Filtering
109
where K satisfies the following differential equation on the space M(n x n)
k=(A-
T°H)K
+ K(A - T°H)
- (r - n (HK° + Q 3 I + i*42 - (Q33 + #44)(r°)')
- (K°H + Q13 + R24 - r°(Q33 + Ru))(r - n ' , K(0) = 0. (8.20) Computing the derivative of 4>(e) and using the necessary condition (8.16), we obtain
0 = (d/cfe)0(c)|e=sO = [TT (QK) rft V T € Loo(J,Af(n x m)).
(8.21)
Since this holds for arbitrary Q e Li(I, M+(n x n)) and any finite interval J, we conclude that K = 0. This requires that, for any V e L^^I, M(n x m)) the solution of equation (8.20) be identically zero, that is, for all t € I. But this is possible if and only if the multiplier of T — T° is identically zero. Thus it follows from equation (8.20) that the expression K°H
+ (Q 1 3 + #24) - r ° ( Q 3 3 + #44) = 0.
(8.22)
Since R44 > 0 and Q33 > 0, the optimal gain is given by T° = (QIS + #24 + K°H'\
(Q33 4- #44) _ 1 .
(8.23)
Substituting the expression (8.23) in equation (8.18) we obtain the differential Riccati equation
K°=[A-
(Q13 + i*24)(Q33 + + K°[A-
Rur'H]^
(Q13 + # 24 )(Q33 +
-K°H\Q33
Ru)~lH]
+ Ru)-lHK°
+ (QH + R22 - (Q13 + R24XQ33 + R^'HQsi K°(0)
=K0.
(8>24)
+
Ru)),
Linear Filtering: Correlated Noise III
110
This is the differential Riccati equation giving the optimum covariance operator K° which when substituted in (8.23) gives the optimum filter gain T°. Thus we have proved the following result. Theorem 1 Suppose the elements of the matrices {A(t), H(t), D(t), C(t),t > 0} are locally integrable and those of {cri(t), 0} are locally square integrable with o± being nonsingular. The processes {x$,W, V} are uncorrelated, xo has finite second moment, {W, V} are Brownian motions with {Q, R} being their corresponding incremental covariance matrices with R being positive definite. Then the best (UMV) linear filter for the systems (8.1) and (8.2) is given by the following set of equations dz = (A - T°H)zdt + (D-
T°C)ydt + T°dy,
(8.25)
z(0) = XQ,
where F° is given by T° = (QIS + #24 + K°H'\QM
+ Ru)~\
(8.26)
and K° is given by the solution of the differential Riccati equation K° ={A - (Q13 + R24)(Qs3 +
R44)-1H)K°
+ K°(A - (Q13 + R24)(Q33 +
Ru)-lH)
-K°H\Q33^R44)-1HK° + (Qll
(8.27)
+ R22 - (Ql3 + R24)(Q33 + # 4 4 ) _ 1 ( Q 3 1 + R42)) ,
#°(0) =K0.
8.6 Special Cases (a) Uncorrelated Case The results for the uncorrelated case can be readily derived from the above result. Recall that for the uncorrelated case, a2 = 0, a 3 = 0. Hence the only matrices of equation (8.12) which are nonzero are {Qn,R44}. In this case equation (8.26) reduces to r° = K°H'(Ru)-\
(8.28)
11 1 111
Linear and Nonlinear Filtering and equation (8.27) reduces to K° =AK° + K°A' + + Qn -
K°H'R-jHK° K'H'R^HK" 44
(8.29) (8.29) { K°(0) =K =K0.0. ' These are precisely the equations for Kalman-Bucy filter as given by equations (3.9) and (3.10) of chapter 3.
(b) System noise affecting Measurement noise. In case the system noise affects the measurement noise but not the converse, we have <j2 = 0. In this case the matrices {R22# #24, R42} are all zero. Thus it follows from equation (8.23) that the optimum gain is given by 1 +R T° = (Q13 + K°H){Q tf0#')(Q33 + i*44)33 44)-K .
(8.30)
(c) Measurement noise affecting System noise In case the measurement noise affects the System noise but not the converse, we have 03 = 0. In this case the matrices {Qi3,Q3i-Q33} are all zero. Thus again it follows from equation (8.23) that the optimum gain is given by 1 T° = 24 T°=(# (#24 + K°H')(R K°H'){R 44)- . 44)-\
(8.31)
Comment 1 The filter equation (8.25) can be written with the innovation process as its input, dz = {Az + Dy)dt + r°(Q33 + 2 (0) z(0)
R^f^dW, R44 )1/2dW,
= z0, z0,
(8.32) (8.32)
where W is an m-dimensional ^-measurable standard Wiener process. This is verified as follows. Define the process V as given by V(t) = yy(t) - { C(s)y(s)ds - f H(s)z(s)ds, t > 0. w W y w w 7o Jo 7o Jo Clearly it follows from (8.2) and (8.33) that dV dV = = (dy (dy -- Cydt Cydt -- Hzdt) Hzdt) = H(x z)dt + a 4dV. = H(x - z)dt + a3(t)dW (t)dW + + <J a dV. 3
(8.33)
(8.34)
4
Again using conditional expectations relative to the sigma algebra JF* and Ito formula for stochastic differentials one can verify that {V(t),t > 0} is a Wiener process with covariance operator given by (Q33 + R*t)- Then define W by (8.35) dW = (Q33 + R44)-V R44)-21dV. '2dV. Clearly W, as defined, is an m-dimensional standard Wiener process.
112
Linear Filtering: Correlated Noise III
8.7 Discussions and Examples When dealing with precision measurement at the microscopic levels, the measurement noise and the system noise may equally affect each other. The impact of the measurement dynamics and its internal noise on the system dynamics can be very significant. This is certainly true at the molecular and atomic levels. The model presented in this section is the correct mathematical set up to deal with such problems.
113
CHAPTER 9 L I N E A R FILTERING FOR J U M P PROCESSES
9.1 Introduction In this chapter we consider filtering for linear systems driven by both Wiener and Poisson processes. Thus the trajectories of the state process have discontinuities of at most the first kind. Here we consider two cases: one in which the state has discontinuous jumps but the observation is a continuous process and the second, both the state and the observation have discontinuous trajectories. We must emphasize and remind the reader that we are looking for the best (UMV) linear filter, not the best filter. 9.2 Poisson Noise Let / = [0, oo), denote the time index and ( f i , ^ * , ^ T»-P) denote the probability space with a filtration Tt | C T. Let Z C fln\{0} and {p(t),t G 1} denote a Poisson random process on this probability space. For every pair of Borel sets J C I and E C Z let v( J x E) denote the number of jumps of the process p on the interval J of sizes {Ap(t) = p(t+) — p(t—),t € J} G E. Thus i/( J x E) is a Poisson random variable taking values from the set of positive integers N. In other words v is a counting random measure. The properties of this measure are discussed in section 1.4 of chapter 1. We shall freely use the notations given there. In particular, we use the centered Poisson random measure as defined by equation (1.35) of chapter 1. 9.3 System and Measurement Dynamics (A) We use the centered Poisson process q and the Wiener process W as the fundamental sources of noise affecting the system dynamics. Thus the state of the process {x(£),£ > 0} to be estimated is governed by the linear stochastic
114
Linear Filtering: Jump Processes
differential equation, = A(t)x{t)dt A{t)x(t)dt + <J *i(t)dW(t) dx(t) = / ( t , 0 q{dt q(dt x d£) xd£) X (t)dW(t) ++ f f f(t,0 Jz x(0) = = xo, xo, x(0)
(9.1) (9.1)
while the measurement or the observed process is governed by the following stochastic system dy{t) = H(t)x(t)dt H{t)x(t)dt
+ <x a4(t)dV(t),t > 0, 4(t)dV(t),t >
y(0) 2/(0) = 0.
(9.2)
For a practical example where this model fits well, we mention the global integrated navigation system [27]-[28]. Here the position of ships or helicopters is determined by processing radio signals received from transmitters located at different positions around the globe. Thus, x may represent the vector of signals transmitted which is corrupted by channel noise continuously and also through "cycle hops" by jumps. Clearly the dimension of the matrices must be compatible. For x(t) G Rn, y(t) G #m, W(t) G Rp and V(t) G Rm we must have A(t) G M(n x n),
(9.3) (9.3)
In other words Jz |/(t, f)| 2 n(df) < oo for almost all t G / and that this function is locally integrable on ". 9.4 Problem Formulation Given the history of the process {y(s), 0 < s < t} up to time t, we wish to find the best linear (UMV) estimate of the state trajectory x at time t. 9.5 Structure of the Filter Following the same basic philosophy, the filter dynamics must be of the form dz = M(t)z(t)dt + T(t)dy,t T(t)dy,t>0, > 0, (9.4) zo = x0.
Linear and Nonlinear Filtering
115
Hence our problem now is to choose the matrices M and T so that the estimate z for the state x is unbiased and has minimum variance. 9.6 Solution of the Problem Define the error vector e = (x-z)
(9.5)
as before. Subtracting equation (9.4) from equation (9.1) and using the mea surement dynamics (9.2), we obtain the following stochastic differential equa tion de = {A - YH)edt + (A-TH-
M)zdt + oxdW
+ / / ( * , 0 q(dt x d£) - Ta4dV
(9.6)
e(0) = eo = xo — £oAgain for an unbiased estimate we must have M = A - TH V t > 0.
(9.7)
Hence the error process is governed by the following equation de = (A - TH)edt + axdW + / /(*, £) q(dt x d£) - TaAdV e(0) = eo = xo —
(9.8)
XQ.
From this equation we can easily derive the differential equation for the error covariance matrix K(t),t > 0, as K = (A - YH)K + K(A - TH)' + TRu?' K(0) = K0 where #44 =
G^RG'^
+ O n + Sv(t)
= P
0,
Qn =
GIQG[
and S^ is given by
(s„(t)v,v) = [ (/(*,0^)2n(de).
(9.10)
Jz Following the optimization principle as developed and applied several times in the preceding chapters, we obtain the expression for the optimal gain T° as given below T° = K°HRll, (9.11)
Linear Filtering: Jump Processes
116
where K° is given by the solution of the differential Riccati equation K° = A(t)K° + K°A(t)
- K°H'R^HK°
+ ( Q n + SJ
/
K(0) = K0.
|/(t,77)|
Thus, we arrive at the following result for optimum linear filtering. T h e o r e m 1 Suppose the elements of the system matrices {^4(t), H(t), t > 0} are locally integrable and those of {o-i(t),o~4(t),t > 0} are locally square inte grable with cr4 being nonsingular. The processes {#o, W, V, q) are uncorrelated, XQ has finite second moment, {W, V} are Brownian motions with {Q, R} be ing their corresponding incremental covariance matrices with R being positive definite and / G Ll2oc(I1L2(Z,U))1 that is, 2
n(d77)
a.e and locally integrable on I. Then the best (UMV) linear filter for the systems (9.1) and (9.2) is given by the following set of equations dz = (A-
T°H)zdt + T°dy
(9.13)
z{0) = x 0 , where r ° is given by T° = K°H'R^.
(9.14)
and K° is given by the solution of the differential Riccati equation
K° =A(t)K° K°(0)
+ K°A(t)
- K°H'(t)R^{t)H{t)K°
+ (Qu{t)
+ 5„(t))
=K0. (9.15)
Comparing this result with that of Kalman-Bucy filter, it is apparent that the covariance equation is modified by the additional term 5^(2). Thus the ad ditional perturbation of the state process caused by the presence of the Poisson noise makes the error covariance larger and hence the required optimum gain given by the expression (9.14) also larger in the sense of norm. If one ignores this noise and constructs a Kalman filter using the classical covariance equation obtained by deleting the last term in equation (9.15), one would underestimate the error and the state estimate will be poorer.
Linear and Nonlinear Filtering
117
Another interesting point that should be borne in mind is that the covari ance Sn of the Poisson process given by
(Sw(t)r,,r,) = J (f(t^),v)2mO,ve
Rn
depends on the support of the measure II. For example, if f(t, £) = £ a n d larger jumps are more probable than smaller ones, then 5^ would be larger leading to large variance of the estimate. The same conclusion holds if / is a monotone map in the sense that there exists a 7 > 0 such that
(/(*,£) - f(t,vU
-v) > 7 H - v II2 vt,v G Rn.
9.7 System and Measurement Dynamics (B) Here we consider a system model in which both the state and the observed processes are perturbed not only by the continuous martingales (Wiener pro cesses) but also by two independent centered Poisson processes {g, q] with the corresponding compensating measures denoted by II, II. Thus the state process {x(t),t > 0} to be estimated is governed by the linear stochastic differential equation, dx(t) = A(t)x(t)dt
+ <7i(t)dW(t) + / /(*,£) q(dt x d£) Jz
(y.lo)
x(0) = £0, while the measurement or the observed process is governed by the following stochastic system dy(t) = H(t)x(t)dt
+
xdrj),t>Q,
(y-i 7 )
2/(0) = 0,
where Y C Rm \ {0}. Following the same basic principle we can obtain the optimum filter equa tions. For this purpose we need the error covariance of the jump process perturbing the measurement dynamics. This is defined as S^ by (5,(t)7,7) = / (9(t, 0 , 7 ) 2 n ( d $ ) , 7 € Rm.
(9-18)
Linear Filtering: Jump Processes
118
Thus we have arrived at the following result. Theorem 2 Suppose the elements of the system matrices {A(t), H(t),t > 0} are locally integrable and those of {cri(t),o~4(t),t > 0} are locally square integrable with (74 being nonsingular. The processes {xo,W, V, q, q} are inde pendent, xo has finite second moment, {W, V} are Brownian motions with {<2, R} being their corresponding incremental covariance matrices with R be ing positive definite and / G Ll2oc(I, L2(Z, II)), and g G Ll2oc(I, L2(Y, ft)). Then the best (UMV) linear filter for the systems (9.16) and (9.17) is given by the following set of equations dz = (A - T°H)zdt + T°dy
(9.19)
z(0) = x 0 , where r ° is given by r°(«) = K°H'(R44(t)
+ S«(t))~\
(9.20)
and K° is given by the solution of the differential Riccati equation
K° =A(t)K° + K°A'{t) - K°H'(t)(R44
+ S*) - 1 #(<)ff°
+ (Qn(t) + 5 , ( 0 )
(9-21)
0.
9.8 System and Measurement Dynamics (C) In this case the system and the measurement dynamics are given by dx = (A(t)x + D(t)y)dt + ai(t)dW
+ f f(t,$)
q{dt x d£),
K°{0)
x(0) = x 0 , and
dy = (H(t)x + C(t)y)dt + a4(t)dV + / g(t, £) q{dt x d£), JY 2/(0) = 0,
respectively.
(9.23)
=K
Linear and Nonlinear Filtering
119
As in the preceding chapters we have the following result for optimum filter. Theorem 3 Suppose the elements of the matrices {A(t), D(t)H(t), C(t),t > 0} are locally integrable and those of {o~i(t),a4(t)yt > 0} are locally square integrable with 04 being nonsingular. The processes {x 0 , W, V,q,q} are in dependent, #o has finite second moment, {W, V} are Brownian motions with {Q, R} being their corresponding incremental covariance matrices with R be ing positive definite and / € Ll£°(I, L2(Z, II)), and g e Ll£c(I, L2(Y, fl)). Then the best (UMV) linear filter for the systems (9.22) and (9.23) is given by the following set of equations dz = (A- T°H)zdt + (D - T°C)ydt + T°dy (9'24)
,nN
«(0) = x , where T° is given by
0
r°(t) = K°H'(R44(t)
+ 5*(«)) - 1 ,
(9.25)
and if ° is given by the solution of the differential Riccati equation
K° =A(t)K° + K°A(t)
- K°H(t)(R44
+ (QnW + ^ W )
+
S*)~lH(t)K° (9.26)
K °(0) =if 0 . C o m m e n t 1 Comparing theorem 2 and theorem 3, it is clear that the error covariance equation remains unchanged as expected and hence the filter gain remains unchanged. Comment 2 Filter equations for correlated noise can be developed along the same principle as those of chapters 6,7,8. The reader is encouraged to try this. 9.9 Examples and Discussion We consider a factory having m distinct production lines. The number of machines in operation on the 2-th production line, measured in terms of capacity, at time t is denoted by yi{t) each with capacity c». Let x(t) denote the cumulative revenue of the firm at time t. The availability dynamics of the
Linear Filtering: Jump Processes
120
vector of machines and the growth dynamics of revenue may be described by the following set of stochastic differential equations m
dx — y^PiCiyi(t)dt i=i
— cox(t)dt +
a\dW(t), (9.27)
dy = Hxdt + Cydt + / £q(dt x d£). Here pi denotes the unit price of the z-th commodity, Co consumption rate, the martingale term represents market uncertainty. In the second equation, H denotes the capital augmentation matrix including cost of repairs and main tenance, and C denotes the capital depreciation matrix which is a diagonal matrix with entries all negative. The last term represents random failure or repair intensity with Y C R™ \ {0} denoting the set of all possible scenar ios. Our objective is to find the best linear estimate of the company revenue E{x(t)\J^} at time t given the operation history up to time t. The result of theorem 3 applies in this case with A = —CQ, / = 0, and o± = 0,g(t, £) = £. C o m m e n t 3 For application to navigation problems see [28] and the refer ences therein. C o m m e n t 4 Another general model is given by dx = A(t)xdt + a! (t)dW + C(t)dM(t)
(9.28)
where M is a martingale with incremental covariance given by £{(dM(t),r/) 2 } = (QMw)dl3(t)yri
€ Rk
where QM € Ms(k x k) and (3 is an increasing function of time with /?(0) = 0. Wiener martingale is a special case with (3(t) — t. In this general situation the differential Riccati equation (9.15) takes the form dK = {AK + KA' - KHR^HK
+ Qn}dt + CQNC'd0(t).
(9.29)
Here, it suffices to assume that (3 is a function of bounded variation on bounded intervals of time and that
JTv (C(t)QMC) d/3(t) < CO. Under this additional assumption all the results of this chapter remain valid with the appropriate modification of the differential Riccati equations as sug gested above. For control applications see [73].
121
C H A P T E R 10 L I N E A R FILTERING WITH GAIN CONSTRAINTS
10.1 Introduction In this chapter we continue with continuous time filtering for linear systems driven by Wiener processes but subject to filter gain constraints. This was first treated in several papers of the author and his students [2], [11]. Our derivation is based on the approach given there. An algorithm for computation of the optimum filter gain is given in section 5. In section 6, we consider robust filtering where the system parameters are uncertain. We treat this as a games problem, games against nature. The problem is to find the best filter in the face of the uncertainty. We develop the basic theory and conclude with an algorithm whereby one can determine the best filter which is robust against parametric uncertainty. 10.2 System and Measurement Dynamics The system is governed by the following linear stochastic differential equation. A(t)x(t)dt + a1(t)dW(t) dx(t) = A{t)x(t)dt a^dWit) (10.1) x(0) = = xo, xo, x(0) and the measurement dynamics is given by dy(t) = H(t)x(t)dt y(0) = 0. 2/(0)
+ > 0, + a4(t)dV(t),t a4(t)dV{t),t>0,
(10.2)
10.3 Problem Formulation Given the history of the process {y(s), 0<s
Linear Filtering: Gain constraints
122
or the estimator must be linear of the form dz = M{t)zdt + T{t)dy
(10.3)
with the filter gain T satisfying some boundedness constraints. First we recall that for unbiased estimate, M must be given by M(t) = A(t)-T(t)H{t).
(10.4)
Thus for unbiased estimate we must allow this freedom before we place any constraints. Hence we are now free to put any constraints on the filter gain T without compromising the unbiasedness. Thus we can state the problem as follows. Let I = [0,T] be a finite interval and Q C £ ^ ( 7 , M(n x m)) a subset of the space of essentially bounded measurable functions taking values from the space o f n x m matrices denoted by M(n x m). Thus the problem can be stated as follows: Find F G Q that minimizes the functional J ( r ) = / T r (Q(t)K(t))
dt
(10.5)
where K denotes the error covariance which is governed by the matrix differ ential equation, K(t) = (A-
TH)K(t)
+ K(t)(A - TH)' + Qn + TRur',t
> 0,
K(0) = K0
= Po,
and ft is any positive definite matrix valued function on I. 10.4 Solution of the Filtering Problem The first question that arises is the question of existence of a solution of the optimization problem (10.5) and (10.6). This is a serious question since even a simple problem as stated below does not have a solution. Consider the interval T = [0,1] and the set A={xe
C{T) : x(0) = 0,x(l) = 1 and |x(t)| < 1}.
The problem is to find an x° G A that minimizes the functional
J(x) = f \x(t)\2dt.
Linear and Nonlinear Filtering
123
Clearly J(x) > 0 and xn(t) = tn,t G T, is a minimizing sequence and lim J(xn) = 0.
n—»oo
But the limit of the sequence is not in A and hence the infimum is not attained in the class. It fails because though the set is closed, bounded and convex, it is not compact. Thus the question of existence is important since otherwise one may search for an entity that does not exist in the first place. For this reason we are always required to verify if an optimization problem has a solution or not. First let us consider the case in which Q is bounded and suppose it is also closed and convex. Since it is a closed bounded convex subset of L^I, M(n x m)), Q is weak star compact. Let Loo(J,M+(n x n)) denote the class of real symmetric positive definite matrix valued functions on / . As K§ is positive, it is easy to verify from equation (10.6) that for any T G Loo(J, M(n x m)) the solution K G L^I, M+(n x n)) and, further, it is also absolutely continuous. Thus, since Q G Loo(^» M+ (n x n)), the functional J(T) is positive. Therefore if we show that J is weak star lower semicontinuous in the sense that J(T°) n
for any sequence T e G that converges to T° in the weak star topology on Loo(7, M(n x m)), then we can prove that J attains its minimum on Q. Indeed suppose that J is weak star lower semicontinuous and that
inf{j(r),r es} = /?. Clearly /3 > 0. Let { r n } G Q be a minimizing sequence. Sine Q is weak star compact ( weak star closed), there exists a subsequence of this sequence, relabeled as such, and a r ° G Q such that T n —► T° in the weak star topology. Then by virtue of weak star lower semi continuity we have J(T°) < liminf J ( r n ) < lim J(Tn) = /?. n—>oo
n—»oo
But since T° G G, it is clear that (3 < J(T°). Hence we have proved that J ( r ° ) = /? which means that the infimum is attained on G- Now it remains to show that J is weak star lower semicontinuous. Let $n(t,s),Q < s < t < T denote the transition operator corresponding to the matrix A(t) — Tn(t)H(t) and $ o ( t , s ) , 0 < s < t < T, that corresponding to the matrix A(t) - T°(t)H(t). By use of Gronwall inequality, one can verify that if Fn
124
Linear Filtering: Gain constraints
converges to r ° in the weak star sense, then the transition operator $n(t,s) converges to ®0(t, s) uniformly on the triangle 0 < s
f Tr{ftK°)dt = J(Tn) + / TT{Q(K° Jo Jo < j ( r n ) + F n + Gn,
Kn)dt
-
(1°-7)
where
Fn= f dsf dt ii/n(t){(*„(«,*)ro(«) -
$n(t,s)rn(s)).
.Ru(s)($0(t,s)r°(s))'} Gn=
f
ds f
dt Tr(n(t){($0(t,s)r0(s)R44(s)
•
•
($0(t,s)r°(s)-$n(t,s)rn(s))}).
Since 04 G 1,2(1, M(m x m)), it is clear that R44 £ L\(I, M(m x m)). Thus by virtue of weak star convergence of Tn to T° and uniform convergence of 3>n to $ 0 , it follows from the above expressions that lim Fn = 0, lim Gn = 0.
71—KX)
n—XX)
Hence for every e > 0, there exists a number n€ € N such that |Fn|,|Gn|<(l/2)c for all n>n€.
Thus we have J{T°) < J ( T n ) + e , V n > n £ .
(10.8)
Since e > 0, but it is otherwise arbitrary, it follows from this that J(r°)
proving weak star lower semicontinuity of J.
(10.9)
Linear and Nonlinear Filtering
125
Now consider Q to be unbounded. Since Q e L 0 0 (7,M s + (n x n)) and #44 > 0 for all t e / , it is easy to verify from equation (10.6) that || K ||—> +oo as || T ||—> +oo. Hence J(T) is radially unbounded, that is lim J(T) —> +oo. liriHoo One can verify this by integrating equation (10.6) and using the facts that Qn(t) is nonnegative and Ru(t) is positive definite on the interval I. From this and nonnegativity of J and the fact that J ^ oo (is not identically infin ity) we conclude that J has a minimum. Thus we have proved the following fundamental existence result which is presented as a theorem. T h e o r e m 1 Let Q C L^I, M(n x m)) be a closed convex, possibly, bounded subset and Q a real symmetric positive definite matrix valued function with values in M(nxn). Then the optimization problem (10.5), (10.6) has a solution. C o m m e n t 1 It is interesting to note that for Q bounded, it is not essential to assume the strict positivity of the observation noise covariance R44{i) = a4(t)Ra4(t) . However, we will see later that the Kalman-Bucy filter can be derived only if this matrix is positive definite for all t £ I. Next we prove the following result which is required to develop necessary conditions for optimality. In other words this will allow us to write a set of necessary conditions that a T € Q must satisfy if it is to be optimal. L e m m a 2 For every T e G, equation (10.6) has a unique solution
KeAC{I,M(nxn)), the space of absolutely continuous functions with values in M(n x n). The mapping T —> K is continuous and continuously Gateaux differentiable and its Gateaux derivative at T° in the direction T - T° is given by the solution of the following equation:
k = (A - T°H)K + K(A - T°HJ - (T - T°)(HK° - i ^ r 0 ) ' ) - (K°H - r°R44)(T - r°)',
( 10 - 10 )
K(0) = 0, where K° is the solution of equation (10.6) corresponding to T = T°. Proof. The first part is already known. We prove the last part. Let T°, V e Q and s e [0,1]. By convexity Fe = r ° + £ ( r - r ° ) e Q. Let K£ and K° denote the
Linear Filtering: Gain constraints
126
solutions of equation (10.6) corresponding to T£ and T° respectively. It is easy to verify that as e —> 0, K£ —> K° uniformly on I. Hence by using equation (10.6) for K£ and K° and subtracting one from the other and dividing by e and letting e —> 0 one obtains equation (10.10). QED Now we are prepared to develop the necessary conditions of optimality. Let r ° G G be the optimal gain, and T e G any other element. Then by virtue of convexity and closedness of the admissible set G, T° -f e(T — F°) G G for all e G [0,1]. Clearly by optimality of T°, J(T° + e(T - T°)) > J(T°) Ve G [0,1], WeG-
(10.11)
This is equivalent to [TT(QK£)
dt > [TI(QK°)
dt.
(10.12)
Wee [ 0 , 1 ] , V T G £ .
(10.13)
Hence £
-K°))dt>0,
Dividing through by e and letting e —> 0 we obtain [Tr(n(K)\dt
> 0, VT G £,
(10.14)
where K is the solution of equation (10.10). Our objective now is to write this inequality in terms of T , r o and K°. Towards this goal, we introduce an auxiliary equation which we call the adjoint equation given by L + L(A-
T°H) + (A - T°H)'L = fi(t)f
L(T) = 0.
[Tr(n(K "
Since ft G Loo(7,M+(n x n)), it is clear that this equation has a unique absolutely continuous solution L° G AC(I,M(n x n)). Replacing Q in the inequality (10.14) by the expression on the left hand side of equation (10.15) and integrating by parts and using the boundary conditions K(0) = 0 , L ° ( T ) = 0 one arrives at the following expression /
Tr(SlK)dt = f
T V | L ° f-K
+(A-
T°H)K + K(A - F°HA
\dt > 0.
Linear and Nonlinear Filtering
127
Recalling that for any matrix D, Tr(D) = TY(D'), and using the variational equation (10.10) it follows from the previous inequality that j
-r^R44)(r-ro)'jcft>0, VTeS.
TrU°(K°H
(10.16)
Collecting all these information together we have the following necessary conditions for optimality. Theorem 3 Suppose the assumptions of Theorem 1 hold. Then in order that r ° G Q be the optimum gain for the constrained filter, it is necessary that the following equations and inequalities hold: L° + L°(A - r°H) J + v(A - T°H)'L° = nm, ; w L°(T) = 0, K°(t) = (A-
T°H)K{t)
+ K(t)(A - T°HJ + Qn + (r°)Ru(r°)\t
(10.17) V ; > 0,
K°(0) = Xo, (10.18) and
0
0
fTrlL (K H'
- r°R44\
(T - r°)'\
eft > 0, VT G S- (10.19)
Unconstrained Filter Here in this subsection we wish to derive, from the very general result given above, the classical results of Kalman-Bucy. We lift the constraint by choosing Q = Lpo(I, M(n x m)). Then it follows from the inequality (10.19) that L° \K°H
- r°#44 ) = 0, V t G / .
(10.20)
If Cl G £,«,(/, Af+(n x n)) and Q(t) > 0 for all t G / , then equation (10.17) has a real symmetric strictly negative definite solution L°. One can easily verify this as follows. First note that equation (10.17) has a unique solution given by L°(t) = - f
* B ( t , 8)Sl(8)*'B(t, s)ds,
(10.21)
where \£s(£, s),0 < s < t < T, is the transition operator corresponding to the matrix function
B(t) =
-(A(t)-r°(t)H(t))'.
Linear Filtering: Gain constraints
128
We show that L° is negative definite by establishing a contradiction. It is obvious from (10.21) that it is symmetric and negative semidefinite. We must show that it is strictly negative. Suppose there is a £ ( ^ 0) e Rn such that (L°(*)£, 0 = 0 for some t G I. Then f
(Sl(s)9B(t,*)£,
9s(t, s)Qd8 = 0.
Since Q(t) is symmetric and positive definite we can write this as
|| (QCs^vMMK II2 ds.
0=J This implies that n(s))1/2VB(t,s)£
= 0 for almost all s € [*,T].
Hence, by the positivity of Q, and nonsingularity of the transition operator \I>£, it follows that £ = 0. This contradiction proves the claim. Thus L°(t) is negative definite for all t G [0, T) and hence it follows from (10.20) that K°(t)H{t)
- T°(t)R44(t)
= 0 V t e [0,T).
(10.22)
Thus we have proved the following result. Corollary 4 Suppose the assumptions of Theorem 3 hold with Q = Loo(7, M(n x m)) and Q(t) a real symmetric positive definite bounded matrix valued function. Then the necessary conditions of optimality given by Theorem 3 are equivalent to the following necessary conditions: for the filter gain T° to be optimum, it must satisfy the equations (10.18) and (10.22) simultaneously. This means that the optimum filter gain T° has to be determined by solving the differential equation K(t) = F(K(t), T(t)), K(0) = K0,t€(0,
T]
(10.23)
subject to the algebraic constraints G(K,T) = 0,
(10.24)
Linear and Nonlinear Filtering
129
where F{K, T) = (A - TH)K + K{A - THJ + Qn + G{K,T) =
TR
TR44-KH\
In any case once T° is found, the optimal filter is given by the stochastic differential equation dz = (A - T°H)zdt + T°(t)dy
(10.25)
which follows from equations (10.3) and (10.4). This problem reduces to a much simpler one if the measurement noise covariance #44 is invertible. This requires that R > 0 and a4(t) nonsingular for all t e I. In this case equation (10.22) yields an explicit expression for the optimum gain as given below Y° = K°HR^.
(10.26)
Substituting this in equation (10.18) one obtains the differential Riccati equa tion K°(t) = A(t)K(t)
+ K(t)A{tj
+ Q n - K°H'{R^)~lHK°,t
K°(0) = Ko.
> 0,
44(r)'
Thus we see that the Kalman-Bucy filter follows from a corollary to a more general result on filtering with constraints on filter gain. 10.5 Dynamically Coupled Systems In this section we assume that the process dynamics and the measurement dynamics are fully coupled in the absence of noise. Thus the system is given by dx{t) = A(t)x{t)dt + B(t)y{t)dt + ai(t)dW(t) (10.28) x(0) = x 0 , and the measurement dynamics is given by dy{t) = H(t)x(t)dt
»(o) = o,
+ C(t)y(t)dt + 0, (10 29)
'
where the matrices {A, S , i J , C} are locally integrable. As we have seen in the preceding chapters with uncorrelated noise, the error covariance does not
Linear Filtering: Gain constraints
130
change. It is still given by equation (10.27) though the optimum filter dynamics is different. For unbiased estimation, demanding a filter structure of the form dz = Mzdt + Nydt + Tdy, one arrives at the conclusion that M and N must be given by M = A - FH and N = B - TC. This leads to the estimation error equation given by de = (A - TH)edt + axdW - Ta4 Hence the error covariance dynamics remains unaffected by these generaliza tions. Thus for optimum constrained filter, theorem 3 remains in force. This is stated in the following theorem. T h e o r e m 5 Suppose the system matrices {A(t), B(t), H(t), C(t), t > 0, } have locally integrable entries and the matrices {<Ji{t),(j£(t),t > 0,} have entries which are locally square integrable. Further, the processes {xo,W, V} satisfy standard hypotheses. Then the optimum linear filter is given dz = (A-
T°H)zdt 4- (B - T°C)ydt + T°dy,
z(0) = x 0 ,
dV.
where the optimum gain r ° satisfies the necessary conditions of optimality given by equations (10.17)-(10.19). 10.6. Algorithm for Computation I Here we present briefly an algorithm for computing the optimum filter gain subject to the constraints. This we do by using the result of theorem 3. Suppose the nth stage of iteration has been reached. Then, by setting n = 0, one has initialized the algorithm. s t e p 1 Suppose at the nth stage, T = Tn e Q. Setting T = Tn solve equation (10.17) to obtain Ln. S t e p 2 Use T = Tn to solve for Kn using equation (10.18). S t e p 3 Use {Tn,Ln,Kn} and the inequality (10.19) to compute the direction of search Gn = Ln(KnH - TnRu). (10.31) S t e p 4 Choose a positive number an and update Tn by T n + 1 given by rn+l
^ pn _
anGn^
(1Q 3 2 )
Linear and Nonlinear Filtering
131
so that T n + 1 lies in the admissible set Q. Step 5 Repeat step 1 with T n + 1 till a stopping criterion is met. Note that corresponding to the updated T n + 1 , the cost is given by
j(r n+1 ) = j(rn) + dj(r n ,r n + 1 - r n ) + o(an) = J(Tn) - andJ{Tn, Gn) + o(an) = J ( r n ) - an [TT (Gn{Gnj) n
)-anj
dt + o(an)
(10.33)
\\Gn\\2dt + o(an).
Here we have used dJ(T, A) to denote the Gateaux differential of J at T in the direction A. Choice of the step size an is very critical. Prom the last equation it is clear that for sufficiently small an the algorithm will converge. If at the n-th stage Tn e dQ and the direction denoted by Gn is outward, one must stop the iteration. If however Gn is inwardly directed, then an can be chosen positive and the iteration continued. This gives us a time varying filter gain I\ For easy implementation, often in engineering practice it is desirable to have a time invariant filter gain. For this one may choose a closed, possibly, bounded convex set E C M(n x m), and consider this as the set of admissible gains. In this case one can modify the previous algorithm as follows. For the direction Gn we define Gn = f{Ln(KnH
- TnR44)}
dt
(10.34)
and replace (10.32) by r n + l =Tn
_
anQU
(10.35)
starting with r ° e S. 10.7 Robust Filtering In this section we want to introduce the concept of robustness for lin ear filtering. This question arises when the system matrices are not precisely known or they are dependent on some parameters whose values are not pre cisely known. We assume however that the parameters lie in some bounded set in RN for some integer N < oo. We denote this set by V. The system model is given by dx = A(t,q)xdt 4-
= J(T
132
Linear Filtering: Gain constraints
for t 6 I and q £ V. Our basic problem is to give the best linear estimate (UMV) of x(t) relative to the filtration T^ in the face of the uncertainty about q e V. In view of the preceding chapters, we know that, given the parameter g e P , the best filter must have the form dz = (Ait, q) - T(t)H(t, q))zdt + T(t)dy, z(0) = x 0 ,
(10.37)
where the optimum filter gain T is determined by minimizing J(T)=
f Tr(Sl(t)K(t))dt= Jo
f Tr (to(t)K{t,q,T)) Jo
dt,
(10.38)
subject to the dynamic constraint K = (A{t, q) - T(t)H(t, q))K + K(A(t, q) - T(t)H(t, q)) + v(t, q)Q* (t, q) + r ( * 0 ( i , 9)Ari(*, «))r',
(10-39)
X(0)=^o='PoIf there are no constraints on the filter gain this will give us the Kalman-Bucy filter and if there are constraints we obtain the result stated in Theorem 3. The problem here is that q is unknown and therefore J is not uniquely defined by r alone. In fact it is a well defined function of the two parameters V and q. To emphasize this dependence we write J(q,T) for the expression (10.38). Now suppose that there are also gain constraints as in sections 10.3 and 10.4 of this chapter. The admissible set is again denoted by Q C Loo(I, M(n x m)). In the face of the uncertainty, the correct formulation of the problem should be as follows. Find a P G 5 that minimizes the functional J0(r)=sup{J(g,r),g6P}. This is a min-max problem or a games problem, games against nature. The op timal strategy, or equivalently, the saddle point of the game is a pair (g°, T°) G V x G that satisfies the following chain of inequalities J(q,r°)
< J(q°,T°) < J(q°,T),
V (q,T) € V x Q.
(10.40)
We assume that an optimal strategy exists. Our main interest here is to develop necessary conditions of optimality. In order to prove the necessary conditions for optimality we need several intermediate results. Let (g°,r°) € V x Q be
Linear and Nonlinear Filtering
133
the saddle point and let K° denote the corresponding solution of the following matrix differential equation K = (A(t, q°) - r°(t)H(t,
q°))K + K(A(t, q°) - T°(t)H(t,
+ 0 ( t , q°)R*o(t,
q°))' q°)')(T°)',
K(0) = K0 = P0. (10.41) The associated value of the game is then given by J{q°,T°) = ITr(Sl(t)K0(t))dt.
(10.42)
For convenience of presentation we introduce the following notations. Corre sponding to the pair (q°, T°) 6 P x g, we define B0(t) =
A(t,q°)-r°(t)H(t,q°)
Co(t,0
= dqA(t,q°,0
-r°(t)dqH(t,q°;0,Z
Do(t,0
= dqa(t,q°;Z)Qa'(t,q°),te
E0(t,$
= r°(t)dqa0(t,q°;Z)RcT'o(t,q0)(r°)',$
€
RN,
€
RN,
RN,
(10.43)
where, for any function F(t,q), dqF(t,q°,£) denotes the Gateaux differential of F(t, q) with respect to q at q° in the direction £. These are all n x n ma trix valued functions. The map £ —» dqF(t,q°,£) from RN to M(n x n) is homogeneous. Later we may assume that it is also linear. Fix T = r ° in (10.39) and let q free. Let Ke denote the solution of equation (10.39) corresponding to T = T° and qe = q° + e{q - q°). L e m m a 6 Suppose all the matrices are measurable in t € / and continuous and continuously once Gateaux differentiable with respect to the parameter q on V. Then K£ —► K° uniformly on I. (10.44) Further, there exists a K € C(I, M(n x n)) such that as e —> 0 (1/e) (K£ -K°)^K
(10.45)
uniformly in t on V" and it satisfies the matrix differential equation (d/dt)K
= B0{t)K + KB0(t) + G(t, q°, T°, K°;
K(0) = 0,
q-q°),
(10.46)
Linear Filtering: Gain constraints
134
where G(t, q°, T°, K°; q-q°)
= C0(t, q - q°)K° + K°C'0(t, q - q°) + A>(*, 9 " 9°) + D0(t, q-q°)
+ E0(t, q - q°) + £ > , - q°). (10.47)
Proof. The proof is essentially simple but long. We present only an outline. Subtract the differential equation (10.41) corresponding to the pair {q°,T°) from that corresponding to the pair (q£, T°) and arrange terms in a suitable way and apply Gronwall inequality and Lebesgue dominated convergence theorem to prove (10.44). This part requires the continuity of the matrices with respect to the parameter q. Similarly one can prove (10.45) and (10.46) using the assumptions on Gateaux differentiability of these matrices with respect to the parameter q. This completes the outline of our proof. QED The reader is encouraged to carry out all the details. Using the first half of the inequality (10.40), we can now prove the first half of the necessary conditions of optimality stated in theorem 10. L e m m a 7 Suppose that the admissible set V x Q is convex and closed and that an optimal strategy pair exists. In order that the pair (q°, T°) £ V x Q be the optimal strategy it is necessary that there exists an L° £ C(I, M(n x n)) such that /
Tv|-Lo(t)G(t,^o(t),ro(t),^;go-9)|^<0,
\fqeV,
(10.48)
where L° is the solution of the adjoint equation (d/dt)L + LB0(t) 4- B0(i)L = Q(t),t e [0,T],L(T) = 0.
(10.49)
Proof. Given that the pair (^°,r°) G *P x Q is the optimal strategy, it is evident that J(g £ , r ° ) - J(q°,T°) < 0, We G (0,1]. (10.50) Thus (l/e)(J(q^r°)
- J(q°,r°))
= [
Tr(Q(t)(K£
- K°)/e)dt.
(10.51)
Jo
Letting e [ 0 it follows from (10.50) and (10.51) that dq J(q°, r ° ; q-q°)=
[ Tr(Q(t)K(t))dt Jo
< 0, \/q G V,
(10.52)
Linear and Nonlinear Filtering
135
where K is the solution of equation (10.46) corresponding to q e V. We intro duce the adjoint system, (d/dt)L + LB0(t) + B0(t)L = Sl(t), L(T) = 0.
(10.53)
It is clear that for every Cl e L i ( i , M+(n x n ) ) , this equation has an absolutely continuous solution L°(t),t e I. Substituting this in (10.52) one can easily verify that
dqJ{q0,T0-q-q°)
=j
TriL°{-{d/dt)K
+ B0K +
kB0)\dt,
= f Trl-LoG(t,qo,ro,Ko'iq-qo)\dt<0,
VgGP.
(10.54) Using the facts that for any pair of square matrices K, L, Tr(KL) = Tr(LK) and Tr(K) = TY(iO, it follows from (10.47) and (10.54) that
dqJ{q°, P>; q-q°) = J = J^ Tri-L°
i J - L°G(t, q°, P \ K°; q - q°) \dt\c
(co(t, q - q°)K° + A)(*, q ~ q°) + E0(t, q - q°)\ \dt < 0, (10.55)
Vg € V. This completes the proof. QED Now we consider the second half of the games problem (10.40), that is,
j(q°, r°) < j(q°, r), vr e g.
(io.56)
Proof of the following Lemma is very similar to that of lemma 6. Lemma 8 Suppose the assumptions of Lemma 6 hold and further the set Q is convex and weakly (weakstar) closed as a subset of Loo(7, M ( n x ra)). For e e (0,1], define T£ = r ° + ^ ( r ~ r ° ) and let K€ denote the solution of equation K* = (A(t,q0) - r£(t)H(t,q°))K*
+ K*(A(t,q°)
-
Y*(t)H(t,q°)j
+ v(t, q°)Q* (t, q°) + r (erofr q°)Rtr'0(t, q°)) (I*)', £
K (0) = K 0 , (10.57) corresponding to the pair (q0,Te) and K° the solution of equation (10.41) corresponding to the pair {q°,Y°). Then, as e | 0, we have : i ^ —> tf°, (l/e)(/ir e - tf°) — if,
uniformly on / .
(10.58)
136
Linear Filtering: Gain constraints
Further, K satisfies the matrix differential equation (d/dt)K
= B0(t)K
+ KB0{t) + ( r - T0)(R0(r0)
+ ( P ' f l o f r O - K°H\t,q°))(T
-
H{t,q°)K°)
- r°)\
(10.59)
K(0) = 0, where Ro(t,q°) =
a0(t,qo)R<j'Q(t,qo).
Using Lemma 8, we prove the second half of the necessary conditions of optimality. Lemma 9 Suppose the admissible set V x Q is convex and closed and that an optimal strategy exists. In order that the pair (q°, T°) £ V x Q be the optimal strategy, it is necessary that there exists an L° £ C(I, M(n x n)) such that /
T r \ L ° ( r ° R o - K°{t)H
(t,q0))(T°
- T)'left > 0,
(10.60)
for all T € Q where L° is the solution of the adjoint equation (d/dt)L + LB0(t) + B0{t)L = Sl(t), L(T) = 0.
(10.61)
Proof. From (10.56) it is clear that J(q0,T°)
< J{q°,T£)
We e (0,1], T G g.
(10.62)
By definition J(q°,r£)
= J(q°, r° + e(T-r°))=
I
Tr
(Sl(t)Ke(t)) dt,
Jo
J(q°,T°)=
f Tr (il(t)K°(t)) Jo
(10.63)
dt,
where K€ is the solution of equation (10.57) and K° is the solution of equation (10.41) respectively. Hence by virtue of Lemma 8, it follows from (10.62) and (10.63) that
dTj{q°, r° ; r - r°) = / TY (SIK) dt>o vr e g, Jo
(io.64)
Linear and Nonlinear Filtering
137
where K is the solution of equation (10.59). Using the adjoint equation (10.61) and integration by parts, it follows from (10.64) that dT J(q°, r ° ; T-r°)=
f
T T | L ° (-(d/dt)K
+ B0K + KB'0\ \dt.
(10.65)
Using the facts that TV(AB) = Tr(BA), Tr(A + B) = Tr(A) + Tr(£), Tr(A) = Tr(A'), it follows from (10.59) and (10.65) that
d r (
T r j - L ^ r 0 ^ ^ , ^ ) - K°rf(t,q0)\(r
- T°)'\dt
> 0, (10.66)
for all TeG.
This completes the proof. QED
Prom Lemma 7 and Lemma 9, we obtain the necessary conditions that an optimal strategy pair (g°,r o ) must satisfy. T h e o r e m 10 Suppose the hypotheses of Lemma 7 and Lemma 9 hold. Then, in order that the pair {q°, T°) € V x Q be the optimal strategy, it is necessary that there exists an L° £ C(I, M(n x n)) such that f
Trf-L°(co(t,q
- q°)K° + D0(t,q-
q°) + E0(t,q-
q°)\ \dt < 0,
VgeP, and /
Trl{-L0(^r0R0{t1q0)-K0H\t,q0)\r-r0),\dt>
(10.67) where K° and L° are the solutions of the following system of matrix differential equations: K = (A(t,q°)-r0(t)H(t,q°))K + a(t,q°)Qc
+
K(A(t,q°)-r°(t)H(t,q0))'
(t,q°) + r°R<,(t,q°)(T°)',
(10-68)
K(0) = K0 = P0.
(d/dt)L + L(A(t,q°)
- r°(t)H(t,q°))
+ (A(t,q°) - T°(t)H(t,q°))
L = J2(t),
L(T) = 0. (10.69)
Linear Filtering: Gain constraints
138
Proof. The proof follows from Lemma 7 and Lemma 9. QED Comment 2 The results of Theorem 10 also hold for time varying param eters {q = q(t),t G I.} In this case V is a closed bounded convex subset of LOQ{I, RN). See also comment 5. 10.8 Algorithm for Computation II We can use this result to develop an algorithm for computing the optimal strategy pair (q°, T°). Since this is necessarily sequential we may use the nota tions of (10.43) corresponding to the sequence (qn,Tn) G V x Q generated at the nth stage of iteration. We define A(t,qn)-Tn(t)H(t,qn)
Bn(t) =
C„(«,0 = dqA(t,qn,0 Dn(t,0 En(t,0
-Tn(t)dqH(t,qn;0,Z
M = dqa(t,qn;0Qa (t,qn),£ 6 RN, = rn(t)dqa0(t,qn;ORa'0(t,qn)(rn)',Z
€ RN, (10.70) 6 RN.
Assuming that all the Gateaux differentials are linear and that {e^, 1 < i < N} is the canonical basis for RN, we can express the first inequality of (10.67) denoted by (10.67a) as jf
Tr{-Ln(cn(t,q
= l > i - q?) fo =
- qn)Kn + Dn(t,qT V J - L " (cn(t,ei)Kn
qn) + En(t,q-
+ Dn(t, a) + En(t,
e<))
\dt, \dt
J2^-^9i(Ln,Kn,qn,rn)
= («-?",s>
(10.72)
except for the factor 2. This expression is very convenient for writing the algorithm. Similarly for (10.67b), at the nth stage of iteration, we have Fn(t) = -Ln(t)(rn(t)a0(t,qn)R<70(t,qn)
- Kn{t)H\t,qn)\
(10.73)
Linear and Nonlinear Filtering
139
Thus the expression (10.67b) can be written as
f iv|-L n ^r n ^ 0 (t,o-^ n ^ , (^o)(r-r n ) , |^ (10.74)
= / T>(Fn(r-rn)')d*. Jo The gradient here is given by
«dTJ(qn,rn),A»=
[ Tr(Fn(t)A'(t))dt,
A e £«,(/, M(n x m)).
Jo
(10.75) Using the gradients (10.72) and (10.75) we can now write an algorithm. Step 1 Let (qn,Tn) e V x Q, n > 0, denote the approximations at the nth stage of iteration. Step 2 Solve equations (10.68) and (10.69) replacing (g°,r°) by the pair (qn,Tn) and obtain (Kn,Ln). n n Step 3 Use {q ,T , Kn,Ln) to compute the gradients given by (10.72) and (10.73) giving {gn,Fn}. Step 4 Define g n + 1 = qn + egn, and T n + 1 = Tn - eFn, by choosing e sufficiently small so that ( ^ n + 1 , r n + 1 ) € V x Q. If the gradients are zero or outwardly directed the saddle point is ( g n , r n ) and stop and print the results. If not go to step 5. Step 5 Compute J{qn+\Vn)
= J(qn,Tn)+e
|| g» fRN
J(qn, Tn+1) = J(qn, r " ) - ejo
= J(qn,Tn)-ef
Jo
+o(e)
TV (Fn(Fn)')
dt + o(e)
\\Fn(t)fdt
+ o(e).
(1Q ? 6 )
and go to step 1 with ( g n + 1 , r n + 1 ) and continue unless a stopping criterion is met. Comment 3 Note that according to the expression (10.76), new selection of g n + 1 pulls up the cost and r n + 1 pulls it down. This tug of war continues till the saddle point (g°,r°) has been found. For numerical results on constrained filtering based on algorithm 1 of section 10.6, see [11].
Linear Filtering: Gain constraints
140
Comment 4 The question of robustness in filtering problems have been considered in [45] and [68] using different techniques. Here we have presented a rigorous technique based on games theory. Comment 5 In the case of uncertain time varying parameters (see comment 2), the algorithm for computation given above requires only minor modifica tion. With reference to equation (10.71), define g?(t) = TVJ -Ln (cn(t,
ei)Kn(t)
+ Dn(t, a) + En(t, a)
for 1 < i < N and replace the scalar product in RN by the duality pairing associated with L 00 (7,-R^) and Li(I,RN). Thus the scalar product in the inequality (10.71) takes the meaning, (q ~ Qn,9n) = [ (q(t) - qn«,gn(t))RNdt Jo
<0VqeV.
(10.71)'
For convenience of notation we write F(q°) for F(t,g°). As a corollary of theorem 10 we have the following result for the unconstrained case. Corollary 11 Suppose all the assumptions of theorem 10 hold and that Q = LQO(7, M ( n x r a ) ) . Then the necessary condition for optimal strategy is given by the inequality (10.67a) where K° and L° must satisfy the differential equations K = A(q°)K + KA{q°) + a(q°)Qa (q°) - KH'tq^Rotfr^WK,
(10.77)
K(0) = K0. and -L = LA{q°) + A'(q°)L - LK(H
(q°)R;Hq°)H(
- {H{q°)k;\q°)H{q0))KL L(T) = 0.
-
fi
(10.78)
141
C H A P T E R 11 FILTERING FOR LINEAR S Y S T E M S D R I V E N B Y S E C O N D O R D E R R A N D O M PROCESSES
11.1 Introduction In this chapter we consider continuous time filtering for linear systems driven by Wiener processes and an additional second order random process. We shall see below that in this situation we are required to solve integrodifferential Riccati equations. Within the knowledge of the author, this is the first time that this problem has been addressed and solved. Our derivation is based on the same general principle as used in the preceding chapters. 11.2 S y s t e m and Measurement Dynamics The system is governed by the following linear stochastic differential equation, dx(t) = A(t)x(t)dt + f(t)dt +
+ cr t>0, a4(t)dV(t), 0, 4(t)dV(t), t >
2/(0) = 0.
(11.2)
Here W and V are the Brownian motions and the process {/(*),£ > 0} is an arbitrary second order random process with known mean or known conditional mean relative to the history of the observed process . This is given by either
m/(t) = E{f(t)}, E{f(t)},
(11.3)
mf(t) m = Etf(t)\7?\. Etf(t)\7?\. f(t) =
(11.4)
or
142
Filtering for Second Order Processes
In many engineering problems the noise process / is an essentially bounded random process and hence certainly not Gaussian. It may be Lipschitz, contin uous, or discontinuous but measurable. So it cannot be modeled as a Wiener process. Its probability law is not known. The only information one has about this process is its mean given by (11.3) or (11.4) and its covariance operator C given by s,t € R,£,r, € Rn.
(C(t,8)t,ri)=EUf(t)-mf(t),t)(f(s)-mf{s)),Ti)y
(11.5) Clearly it follows from the above expression that C(t,s) = C'(s,t).
(11.6)
Since the process is assumed to be second order, it is clear that
f || C(t,t) \\dt = J E\\ f(t) - mf(t) ||2 dt < oo,
(11.7)
for any finite interval I. Thus the solution of the SDE (11.1) is a well defined second order random process and is given by x(*) = *(*,0)x o + / * ( * , s ) / ( s ) d * + / ^(t1s)a1(s)dW(s),t>0. Jo Jo
(11.8)
Clearly this process is not Gaussian. C o m m e n t 1 In fact the process / need not be a second order process. We can also admit generalized random processes like an independent white noise. In that case C(t,t) is a Dirac measure concentrated at 0, and equation (11.7) is not necessary. 11.3 P r o b l e m F o r m u l a t i o n Given the history of the process {2/(5), 0 < s < £}, the process {ra/(s), 0 < s < t}, and the covariance C, we wish to find the best (UMV) estimate of the state x at time t, under the constraints that the filter or the estimator must be linear of the form dz = M(t)zdt -f mf(t)dt
+ V(t)dy.
(11.9)
First we recall that for unbiased estimate, M must be given by M(t) = A(t)-T(t)H(t).
(11.10)
Linear and Nonlinear Filtering
143
Thus we can state the problem as follows. Let I — [0, T] be any finite interval and Q = L^I, M(n x m)), the space of essentially bounded measurable func tions taking values from the space M ( n x m), as the admissible class of filter gains. Thus the problem can be stated as follows: Find T € Q that minimizes the functional J(T) = f Tr(Sl(t)K(t))dt where ft € L^I,
Mf{n
(11.11)
x n)) and K is given by
{K{t)a,Z) = E{{x{t)-z{t),Z?}.,teI,
V£efT.
(11.12)
Throughout this chapter we use the following assumption. Assumption A: The random processes {xo, f(t), W(t), V(t),t > 0} are inde pendent with Po being the covariance of Xo, C(t, s) the covariance of / and Q, R are the incremental covariances of the Wiener processes {W, V} respectively with Q being positive semidefinite and R positive definite. Define the error process by e(t) =x(t)-z(t).
(11.13)
Subtracting (11.9) from (11.1) and using (11.2) one obtains the stochastic differential equation for the error process de = (A-
TH)e + (A-TH-
e(0) = e 0 = (x0
M)zdt + ( / - mf)dt + axdW - Ta4dV
-XQ).
(11.14) Again for an unbiased filter we must choose M = A-TH.
(11.15)
This reduces equation (11.14) into the following equation de = (A - YH)e + ( / - mf)dt +
(11.16)
e(0) = e 0 = (x 0 - x 0 ) , and the filter equation (11.9) takes the form dz = (A-
TH)zdt + mf{t)dt
+ T(t)dy.
(H-17)
Letting $r(t,s),s < t, denote the transition operator corresponding to the matrix (A(t) - r(t)H(t)), the solution of equation (11.16) is given by
Filtering for Second Order Processes
144
e(t) = *r(t,0)e 0 + / *r(M)(/(«) - ™f(s)) ds Jo l
[r Qr(t,s)<Ti(s)dW(s)- [ $r(t,s)r{s)a4(s)dV(s),t Jo Jo
e I. (11.18)
For convenience we write this as e(t) = e^t) + e2(t) + e3(t) + e4(t),
(11.19)
where e* denotes the i-th term of equation (11.18). Note that these processes are statistically independent with zero mean. Thus the covariance operator K is given by (K(t)t,0
= E{(e(t),02} = E{(ei (t), 0 2 } + E{(e2(t), 02} + E{(e3(t), £)2} +
E{(e4(t),tf}
= ( # i (*)£,£) + (K2(t)Z,0 + (K3(t)£,0 + (KA{t)t,Z)(11.20) Using these we wish to write, as usual in this book, the differential for K. We do this term by term. By definition these are given by (ffi(i)&0 =< K0$'T{t,0)£, *r(*.0)4 >, (K2(t)£,0 = I
j < C(r, 9)*'r(t,e)£, *r(«,r)€ > d9dr,
(11-21) (11.22)
where C(r,0), given by (C(r,0)£)J?) = £?|(/(r) - ro/(r),0(/(fi) - m/W.T?)},
(11.23)
for 4,77 € Rn, denotes the autocovariance of the process /. Similarly the third and the fourth terms are given by (K3(t)t,t)= {Ki{t)Z, 0=
r* Jo
[ d0, Jo
.
< T(0)Ru(9)r (0)* r (i, 9)£, * r ( t , 9)£ > M,
(11.24) (11.25)
where Quit) =
(11.26)
145
Linear and Nonlinear Filtering
Now we differentiate each of these terms to obtain a differential equation for K. For this purpose we use one of the fundamental properties of the transition operator: (d/dt)$T(t,
s) = (A(t) - r(t)H(t))$T(t,
s), V 0 < s < t < oo.
(11.27).
For convenience of notation we shall suppress the time variable without any undue risk of confusion. We simply keep in mind that A — TH is a func tion of time. Differentiating (11.21),(11.22),(11.24) and (11.25), we obtain the following equations, ( / f o O = < (A - rH)K!(t)U (K2U)
=< (A - TH)K2{t)d,Z>
> + < Ki(t)(A
- rH)'£,Z >
+ < K2(t)(A - TH)'t,Z
(11.28)
>
f <», Jo (11.29) > + < K3(t)(A-VH)'t,t > +Qn(t), (11.30)
+ f <*r{t,e)C(e,t)t,Z>dB+ Jo (K3(t)£,0
=< (A-rH)K3(t)t,t
and finally (*4(*)e, 0 = < (A - TH)Kt(t)t,
£> +
TH)'t, £ >
44(t)r't,z>.
+
Adding the equations (11.28)-(11.31) we obtain the following equation for K {KZ, 0 = < (A - TH)K(t)t,
£ > + < K(t)(A - TH)'e, £> + < Qu£, £ >
+ + f <*r(t,e)c(o,t)t,s>de Jo
+ [ de. Jo
(11.32) Hence it follows from (11.32) that K satisfies the following integro-differential equation: K = (A-
TH)K(t) + K(t)(A - FH)' + Qu(t) + f $r(t,0)C{6,t)d6+ Jo
f Jo
+
T(t)Ru(t)r'(t)
C{t,0)$'r{t,9)d6,
K{0) = K0. (11.334)
Filtering for Second Order Processes
146
For compactness of notation we shall write this functional equation as follows K(t) = K{t) = K(0) =
(K,r), Fl Fl{K,n
(11.33)
K0,t>0,
where Fi denotes the functional expression appearing on the right hand side of equation (11.33A). As usual in this book, we consider equation (11.33) as a controlled system on the state space M(n x n) with filter gains T as controls. Thus according to our basic principle we have proved the following result. Lemma 1 The basic filtering problem (11.11)-(11.12) is equivalent to the following control problem: find r £ Q that minimizes the functional J(T) = f[ Tr(Sl{t)K{t)) Tr{n(t)K{t))
dt
(11.34)
subject to the dynamic constraint (11.33). 11.4 Solution of The Filtering Problem and Some Special Cases Again the first question that arises is the question of existence of a solution of the optimization problem (11.33)-(11.34). We shall not go into this question any further except pointing out that similar question has been addressed in theorem 1 of chapter 10 on constrained filtering. Due to the presence of the integral term, however, some modification in the proof is required. We leave it to the serious reader for a detailed proof. We assume here that the optimization problem has a solution. Here we shall mainly concentrate on the question of necessary conditions of optimality and derive the equations for optimal filtering. Comment 2 It is interesting to note that for Q bounded, it is not essential to assume the strict positivity of the observation noise covariance Ru{t) = at(t)Rat(t)'. Here we ehall lnly yerive ehe eilter rquationn without tny yain constraints, that is, we assume that Q = Loo{I,M(n x m)). Again we invite the reader to derive the filter equations for the general case. Next we prove the following result which is required to develop the necessary conditions for optimality. In other words this will allow us to write a set of necessary conditions that a T e G must satisfy if it is to be optimal.
Linear and Nonlinear Filtering
147
L e m m a 2 For every r G G, equation (11.33) has a unique solution K G AC(I,M{n x n)). The mapping T —► K is continuous and continuously Gateaux differentiate and its Gateaux derivative at T° in the direction T - T° is given by the solution of the following equation:
K = (A-
T°H)K
+ K(A - rQH)' + (r - r°)(#44(r°)' -
+ (Y°Ru-K°H)(Y-T°)
- / $0(t,r)(T
HK°)
-r°)(r)H(r)M0(r,t)dr
Jo
- f M'0{r,t)H (r){T -T°) Jo
{r)$0(t,r)dr,
K(0) = 0, (11.35) where K° is the solution of equation (11.33) corresponding to Y = T°, $ 0 is the transition operator corresponding to the matrix function A(t) — r°(£)ff(£), and the kernel M0 is given by M0{r,t)=
[
$0(r,6)C{e,t)de.
(11.36)
Proof. Let T°,T e G and e€ [0,1]. By convexity Te = r ° H - e ( r - r ° ) 6 G- Let Ke and K° denote the solutions of equation (11.33) corresponding to T£ and T° respectively. It is easy to verify that as e —► 0, Ke —► K° uniformly on I. Hence by using equation (11.33) for K£ and K° and subtracting one from the other and dividing by e and letting e —► 0 one obtains equation (11.35). This involves a bit of algebra, though it may appear to be somewhat laborious. QED Now we are prepared to develop the necessary conditions of optimality. Let r ° e G be the optimal gain, and F e G any other element. Then by virtue of convexity and closedness of the admissible set G, T° 4- e(F — F°) G G for all e G [0,1]. Clearly by optimality of T°,
j(r° + e(r - r°)) > J(r°), \/s G [o, i], vr G g. This is equivalent to [TT(QK€)
dt >
[TI(Q,K°)
dt.
(11.37)
Filtering for Second Order Processes
148
Hence f Tr(n(K£
- K°) Jdt > 0, \fe e [O,1],VT€0.
(11.38)
Dividing through by e and letting £ - > 0 w e obtain fTr(n(t)K(t)Jdt
> 0, VT e 0,
(11.39)
where K is the solution of equation (11.35). Since, here we are only interested in the free problem, that is Q = Loo(/,M(n x m)), the necessary condition (11.39) reduces to [Tr(n(t)K(t)\dt
= 0, VT e Q.
(11.40)
Since, for £l{t) > 0, this is true for all T £ Q and all finite intervals / , this is possible if and only if K = 0 for all T € Q. This means that, for optimality of T°, equation (11.35) must have trivial solution for all V e Q. This is possible if and only if for alH > 0,
( r - T0)(Ri4(T°)'
- HK°)(t)
- f *„(t,r)(r -
T°)(r)H{r)M0(r,t)dr
Jo
+ (r°R44-K°H')(r-r°)'(t)-
f M'0(r,t)H
(r)(T
-V)\r)*'0(t,r)dr
Jo
= o v reg. (11.41) Again, since this is true for all T e Q and Q is the whole space, this must also hold for T(t) = T°(t) + X0(t)D for all D e M{n x m), where X0(t) is related to Q0(t,s) = XotyX-1^)^^ t. Then (11.41) is equivalent to X0(t)D(Ru{T°j
- HK°){t) - [
$0{t,r)X0(r)DH(r)M0{r,t)dr
Jo
(T°R4, - K°H)DX0{t)
- f M,0(r1t)H\r)DX,0(r)^0(tJr)dr
{UA2)
Jo
= 0, \/D e M(n x m). For compactness of notation, define G(t) = (R44{r°)' - HK°)(t).
(11.43)
Linear and Nonlinear Filtering
149
Then, it is clear from (11.42) that the trace must vanish, that is, Tri (X Trj(X 0DG)(t) 0DG)(t)
+ {X0DG)'{t) DG)'{t)- -
f
$0{t,r)X0(r)DH(r)M0(r,t)dr
t - ff M'0(r,t)H'(r)DX' (r,t)H\r)DX'00(r)K(t,r)dr\ (r)$'0(t,r)dr\ (r)*'
(11.44) (H.44) =0
for all D G M(n x m) and t > 0. Since within the parenthesis the second term is the transpose of the first and the fourth is the transpose of the third, this is equivalent to 2Trlxo0(t)DG(t) t)dr\ 2TriX (t)DG(t) - f * 0 ( t , r)X j*0(r)DH(r)M (t,r)X0(r)DH(r)M 0(r, 0(r,t)dr\ ( J o J = 0, Vt > 0, V D e M(n x m),
, , (11.45) (11.45)
which, in turn, is equivalent to Tr|x (t)Z>rG(t) Ttix0(t)D(G(t)
- f/ H(r)M0(r,t)dr\ (r,t)dr\\
\ = 0, Vt > 0, V D 6e M(n x m).
(11.46) Since X0{t) is always nonsingular and (11.46) holds for all t > 0, and all D € M{n x m), we must have t > 0.
(11.47)
d0, M00(r,t)= (r, t) = r* r 0(r,9)C(6,t) * 0 (r, «)C(«, t) < W,
(11.48)
G(t) G(t)= W = /f H(r)M0(r,t)dr,
Jo
But recalling that
it follows from (11.43)'and (11.47) that de( [f iRu(t){T°(t))' ? 4 4 ( t ) ( r 0 ( t ) )= ' = FH(t)K°{t) ( t ) / C 0 ( t ) ++ / M(
Jo
\Je
(r,e)dr)c(9,t). H(r)$o0(r,0)dr)c(6,t).
)
By transposing this we have T0(t)R44 r°(t)R 44(t)
K°(t)H\t) + f[ MC(t,0)( d0 C(t,6)( = K°(t)H'(t)+ °
> 0. f[ $'A_roH(r,e)H'(r)dr),t *'A-roH(r,0)H'(r)dr\t>0. V
(11 (11.49) 49)
150
Filtering for Second Order Processes
Since Ru{t) is nonsingular, equation (11.49) is equivalent to r°(t)=(K°(t)H'(t) =
+J
deC(t,9)(J
$A-roH(r,e)H\r)dr\^R^(t)
F2(K°,ro),t>0.
(11.50). The foregoing analysis shows that the optimal filter gain T° and hence the pair {T0,K°} must satisfy the pair of functional equations (11.33) and (11.50) simultaneously. Thus we have proved the following necessary conditions of optimality. Theorem 3 Suppose the assumption (A) holds and that #44 (0 is invertible for all t > 0. Then, in order that the pair {r°, K°} be optimal for the control problem as stated in Lemma 1, or equivalently for the filtering problem (11.11)(11.12), it is necessary that they satisfy the functional equations (11.33) and (11.50) written compactly as K(t) = F1(K,r),K(0)
r(t) =
=
Ko,t>0,
F2(K,r),t>o.
(11.51)
Further, the optimum filter is given by dz = (Awhere {T°,K0}
T°H)zdt + mf(t)dt
+ T°dy,
(11.52)
is the pair satisfying equation (11.51).
Some Special Cases The first two examples are the extreme cases. The rest are intermediate ones. (a): Let {/(£),£ > 0} be an n-dimensional white noise process with zero mean ray = 0 and C(t, s) = S(t — s)Q0 where Q 0 is the incremental covariance. In this situation
I I
rt
*r(t,9)C(9,t)M
=
(l/2)Q0,
C(t,0)$'r(t,0)dB
=
(l/2)Q0.
0t
/o
(11.53)
Thus equation (11.50) reduces to T0(t) = K°(t)H,(t)R^(t)
(11.54)
Linear and Nonlinear Filtering
151
and the functional differential equation (11.33A) reduces to a differential equa tion given by K = (A-
TH)K(t)
+ K{t){A - TH)' + {Qn(t)
+ Q0) + T(t)R44{t)f
(t),
K(0) = K0, (11.55) with K° being its solution corresponding to T = T°. Thus we have obtained the classical matrix Riccati differential equation with extra noise covariance Qo added to the equation. This is precisely what is expected. Note that if / is an n-dimensional white noise, equation (11.1), can be rewritten as dx = Axdt + dW(t) +
ai(t)dW(t)
where W and W are independent Brownian motions and / is the generalized derivative of W. Clearly this is not a second order random process. But we may note that our result is also valid for a class of generalized random processes including white noise. (b) In case / is purely deterministic and is known to the observer, m / = / and C(£, s) = 0. Again we obtain the classical filter without any additional uncertainty, that is, Qo = 0. (c) Let W be an Rq valued Brownian motion independent of {#o, W, V} with incremental covariance denoted by Q and let f(t) = FW(t),F G M(nxq). Then clearly m/(t) = 0, (11.56) C(t,s) = (tAs)FF. Then one can compute M0(r,t)= G(t)=
[ Jo
[ Jo
(sAt)Q0(r,s)(FF')ds (11.57) H{r)M0{r,t)dr.
This gives equation (11.50) or the second equation of (11.51). (d) In this example we consider F : Rq —> Rn a bounded Borel mea surable function. For the random process / we take f(t) = F(W(t)). This is clearly a bounded measurable random process generated by nonlinear trans formation of the Brownian motion W. Define gt(x) = (l/2irt)q/2exp
{-(1/2*) || x \\2},t > 0.
(11.58)
152
Filtering for Second Order Processes
Then for the mean and the covariance we have mf(t)
= Ef(t)
= [
F(z)gt(z)dz
(C(t,s)^V) = /
(11.59) (F(x) - mf(t),Z)(F(z)
- mf{s),rj)gt-8(x
-
z)gs{z)dxdz.
The expression for the covariance can be verified by use of the Markov property of W and conditional expectations. Information given by equation (11.59) is sufficient to apply theorem 3 for filtering the processes given by equations (11.1)-(11.2). (e) If / is a self similar random process, it is known that its autocovariance is hyperbolic, that is, C(t,s) = C(s,t) = (1/|* - s\a)Qf,0
< a < 1,
(11.60)
where Qj is a symmetric positive semidefinite n x n matrix, that is, Qf € M+(n x n). Given that mj is known, we have Mo(r,t) = f\l/\t G(t)=
rt / Jo
-
8\a)*0(r,s)Qfds, (H.61)
H(r)M0(r,t)dr.
Note that (11.61) involves a singular integral and since 0 < a < 1, this is well defined. Strictly speaking this is not a second order process. 11.5 Dynamically Coupled S y s t e m s In this section we assume that the process dynamics and the measurement dynamics are fully coupled in the absence of noise. Thus the system is given by dx{t) = A(t)x(t)dt + B(t)y(t)dt + f(t)dt + <jx(t)dW{t), , . (11.62) x(0) = x0, and the measurement dynamics is given by dy(t) = H{t)x(t)dt
y(o)-o,
+ C(t)y(t)dt + 0,
(1L63)
Linear and Nonlinear Filtering
153
where the matrices {A, B,H, C} are locally integrable. As we have seen in the preceding chapters with uncorrelated noise, the error covariance does not change. It is still given by equation (11.33) though the optimum filter dynamics is different. For an unbiased estimation, demanding a filter structure of the form dz = Mzdt + Nydt + mf(t)dt + Tdy, one arrives at the conclusion that M and N must be given by the expressions M — A — TH and N — B — TC. This leads to the estimation error equation given by de = (A- YH)edt + (/ - mf)dt + ax 4dV. Hence the error covariance dynamics remains unaffected by these generaliza tions, see equation (11.16). Thus for optimum filter, theorem 3 remains in force. This is stated in the following theorem. Theorem 4 Suppose the system matrices {A(t), B(t), H(t), C(t), t > 0}, have locally integrable entries and the matrices {<TI(£),(T4(£),£ > 0,} have entries which are locally square integrable. Further, the processes {xo, / , W, V} satisfy assumption (A). Then the optimum linear filter is given dz = {A- T°H)zdt + (B - T°C)ydt + mf(t)dt
+ T°dy, dW - Ta
z(0) = x 0 ,
where the optimum gain T° satisfies the necessary conditions of optimality given by Theorem 3. 11.6 Algorithm for Computation Here we present briefly an algorithm for computing the optimum filter gain. This we do by using the result of theorem 3. Suppose the n-th stage of iteration has been reached and Tn has been determined. Step 1 Use r = T n to solve for Kn using equation (11.33) or the first equation of (11.51). Step 2 Use { F \ Kn} to compute F2(Kn1Tn) n 1
and define
n n
r + = F2(K ,r ). Step 3 Use a suitable metric, for example the standard Euclidean metric, to compute
d(rn+\rn) = ||r n+1 - r n ||
Filtering for Second Order Processes
154
and stop if a predetermined level of accuracy has been reached, and print; if not, go to step 1. Note that if at the n-th stage r n + 1 equals Tn then Tn is a fixed point of the functional equation (11.51ii) given by the second equation of (11.51). That is, T n solves the fixed point problem T = F2(Kn,F) in the space Q. C o m m e n t 3 Results of section 11.4 and 11.5 can be generalized to the case where the measurement dynamics is also subjected to an additional noise hav ing second order properties. In this case the measurement dynamics may be given by dy(t) = H(t)x(t)dt
+ C(t)y(i)dt
+ g(t)dt + (jA{i)dV(t),t
> 0,
(11.65) '
K
2/(0) = 0 ,
where g is a second order random process with known mean mg (t) and covari ance Cp(£, s). In this case the filter equation will have the form dz = (A-
T°H)zdt + (B - Y°C)ydt + (mf - T°mg)dt + T°dy.
(11.66)
The equations for the error covariance and the optimum gain denoted by the pair { i f ° , r ° } are slightly more involved than those of equation (11.51). The reader is encouraged to carry out the details to prove results similar to those of theorem 3 and theorem 4.
155
C H A P T E R 12 E X T E N D E D K A L M A N FILTERING-1,11,111
12.1 Introduction In this chapter we consider linear approximation of continuous time filtering for nonlinear systems. Here we develop the so called extended Kalman filter (EKF) equations which are linear approximations of the exact nonlinear filtering equations discussed in the next chapter. We develop three different models for the EKF; the first one is based on linearization around the estimate and the second is based on linearization around the deterministic trajectory of the nonlinear undisturbed system and the third is a second order correction of the first. Our derivation is based on the same general principle as used in the preceding chapters. 12.2 System and Measurement Dynamics The system is governed by the following nonlinear stochastic differential equation in Rn dx{t) = b(x(t))dt + dx(t) + <Ji{t)dW{t) a!(t)dW(t) (12.1) x(0) = £o, x0, where b is a suitable nonlinear mapping from i?" to Rn, and 0, t>0, 4(t)dV(t), (12.2) y(0) = 0,
where h is a suitable nonlinear mapping from Rn to Rm, a^t) £ M(m x m) is a deterministic matrix valued function and V is an m-dimensional Brownian motion with covariance R € M+(m x m). As usual we assume that the processes {W(£),V(£),£ > 0} are statistically independent and also independent of the initial state x0.
Extended Kalman Filtering
156
12.3 Problem Formulation (EKF-1) Given the history of the process {y(s), 0 < s < £}, or equivalently the sigma algebra J^, the problem is to find a process rj(t),t > 0, which is ^"f-adapted so that E{x(t)} = E{n(t)},Vt>0, +: E{(x(t) - r}(t), £)*} is minimum Vf e Rn, V t > 0. This is a particular case of a more general problem. Let <j> : Rn t-> R. Find a process 4>(t) which is T\ measurable so that E{cf>(x(t))} =
E{kt)},Vt>0, (12.4)
E{{(/)(x(t)) - 4>{t))2} is minimum V t > 0.
In other words the best (UMV) estimate of the functional (j>(x(t)) at time £, is given by 4>(t). We show that >(£) is given by the conditional expectation of the random process )(x(t)) relative to the cr-algebra T^, that is, 4>(t) = E{(x{t))\F*}. Define
m = EU(x(t))\^\
(12.5)
and let
E^($(t) - (x(t))) 2\n} = m - mf+z{(m
-
mm2^?}
(12.6) By virtue of (12.5) the last term in equation (12.6) vanishes. Hence we have
E^(t) - <£(*(*)) v ? } = m) - m)2+E{(m
- 4>(x(t)))2i^ j .
(12.7) Since the last term of (12.7) is fixed, the expression on the left attains its minimum if (t) is chosen as ip(t). This verifies our claim that the conditional expectation gives the best (UMV) estimate. Hence the solution to our problem (12.3), that is, the best estimate of the state x(t) given the history T\', is given by
x(t) = EL(t)\J^\.
(12.8)
Linear and Nonlinear Filtering
157
12.4 Problem Solution with EKF-1 Equations The method we follow here is nothing more than linearization of a nonlinear problem. We assume that the drift terms b and h of equations (12.1) and (12.2) are sufficiently smooth so that they can be approximated by retaining only the first two terms of their Taylor series expansion around the estimate x(t). In fact it is sufficient if these functions are only C2. In that case Lagrange formula is used [see section 12.6]. Under this assumption the equations (12.1) and (12.2) can be approximated by dx ~ 0(t)dt + B(t)(x(t) B(t){x(t)
x{t))dt + a!(t)dW(t),x(0) CTi(*)dW(t),a;(0) = x0, x0, - x(t))dt
dy ~ n(t)dt + + H(t)(x(t)
- x(t))dt + a
= 0,
(12.9) (12 9) '
where 6(t) 3{t) = b(x(t)),B(t) b(x{t)),B{t)
= Db(x(t)) Db{x{t)) = {dbi/dxj,1< {dbi/dXj1<
n(t) = h(x(t)),H(t)
= Dh(x(t)) = {dhi/dxj,1 {dhi/dxj,
i,j < n};
0} W),S(«),#,ff(t),t>0} are JFf measurable. For convenience of presentation we shall not hesitate to make a slight abuse of notations. We shall occasionally use B(x(t)) for B{t) B(t) H(x{t)) for H{t). Since equation (12.9) is linear in x, we can use the same approach as used so frequently in linear filter theory. We choose the structure of the filter as follows: dx(t) = M{t)x(t)dt
+ g(t)dt + T(t)dy(t),x(0)
= Ex0 = x x00..
(12.11)
Here we allow {M,g,T} to be ^ - a d a p t e d . Our task now is to choose the ( matrix and vector) processes {M,g,T} so that the filter represented by (12.11) gives the unbiased-minimum-variance estimate x(t). Define the error process e(t)=x(t)-x(t),t>0. e(t) =x(t)-x(t),t>0.
(12.12)
Extended Kalman Filtering
158
Subtracting equation (12.11) from the first equation of (12.9), we obtain de(t) ~(B(t) - T(t)H(t))e(t)dt + a!{t)dW{t)
-
+ (/?(*) - r(*)*7(*) - g(t))dt -
M(t)xdt
T(t)a4{t)dV{t). (12.13)
For an unbiased estimate it suffices to choose M(t) = 0, g(t) = p{t) - r(t)T7(t), t > 0.
(12.14)
With this choice, the error equation (12.13) reduces to de{t) ~ (B(t) - T(t)H(t))e(t)dt
+ ai(t)dW(t)
-
T(t)a^(t)dV(t),
(12.15)
e(0) = eo = xo — xo, and the filter equation (12.11) reduces to
dx(t) - (0{t) - T(t)rj(t))dt + T(t)dy{t),x{0)
= Ex0 = x0.
(12.16)
Since equation (12.15) has precisely the same structure as that of equation (3.13) of chapter 3, the optimum gain is given by r ° = K°H'Rl£
(12.17)
where K° is the solution of the differential Riccati equation K = B(t)K + 0 ' ( t ) + Q n K(0) = K0.
KH'{f)Rll{t)H(t)K,
(12.18)
As we have seen in the previous chapters, equations (12.17) and (12.18) origi nate from the single equation
K = (B(t) - T°(t)H(t))K + K(B(t) - r°(t)H(t))' + Qu + rTz^r 0 )' ^(0) = K0, (12.19) where T° is the optimum filter gain that corresponds to minimum mean square error. Note that, in contrast with linear filter theory, these equations are not explicit since B and H are functions of the estimate x(t) which is our target variable. Therefore this differential Riccati equation can not be solved off line. In any case we have arrived at the following result which is well known in the literature as the Extended Kalman Filter (EKF).
Linear and Nonlinear Filtering
159
Theorem 1 Suppose the drift vectors b and h are sufficiently smooth func tions mapping Rn to Rn and Rn to Rm respectively and the dispersion matrices <7i(£),<74(£),£ > 0 are locally square integrable with 04 being nonsingular. The processes {xo, W, V} are statistically independent where W and V are Brownian motions with incremental covariances given by {Q, R} where R is positive definite. Then, the extended Kalman filter equations (EKF) are given by the following system of coupled stochastic differential equations:
dx(t) ~ b(x(t))dt + T°(t){dy(t) - h(x(t))dt), x(0) = x 0 . T°(t) = K°(t)H'(x(t))R^(t) K°(t) - (B(x(t)) - r°(t)H(x(t)))K°
+ K°(B(x(t))
(12.20) (12.21)
-
T°(t)H{x(t)))'
+ Qii + r°i? 4 4(n', K(O) = K0. (12.22) Proof. Here we present only some comments on the proof. Equation (12.20) follows from equations (12.16) and (12.10) and the definitions for (3 and 77. Equations (12.21) and (12.22) follow from equations (12.17) and (12.19) and the definitions for B and H. QED C o m m e n t 1 By definition x(t) = E{x(t)\Jrf}. Since the equations (12.20)(12.22) are merely the approximations of the correct filter equations to be seen later, it is not quite appropriate to use the symbol x for their solutions. Therefore, caution should be exercised while reading the equations (12.20)(12.22) and interpreting their solutions which are only approximations of the variables they symbolically represent. It is important to note that, in contrast with the linear filtering, K° is now adapted to T\ and therefore a stochastic process depending on the uncertainty carried by the observation process. Hence the optimum filter gain T° is also adapted to Ff. The success of the (EKF) depends very much on the smoothness of the vector fields {6, h} and the accuracy of any algorithm based on the above result. We present here an elementary algorithm for solving the (EKF) equations. 12.5 Computational Methods Since K is symmetric, equations (12.20)-(12.22) constitute a system of nonlinear differential equations of order n(n + 3)/2. The system is driven by
Extended Kalman Filtering
160
the observed process y with initial conditions {X$,KQ}. Given the process y, this is a deterministic system of equations and hence any standard technique like, Runge-Kutta , can be used to solve this problem. Since these system of equations are only approximations of the correct filter equations one must use double precision for reliable estimates. Also one can use simple Euler scheme provided the time interval over which the solution is sought is partitioned with sufficient refinement. Letting Z denote the vector itj,
iT("+ 3 )/ 2 ,
l
one can rewrite the equations (12.20)-(12.22) in the compact form dZ = F(Z)dt + G(Z)dy
{£, K
Z(0) = Zo,
where F and G are vector and matrix valued functions entirely determined by the functions {&,ft,J5, H}. By using the Euler scheme one can compute Z((s + 1) A t ) in terms of Z(s A t) and the current observation as follows : Z((s + 1) A t) ~ Z(s A t) + F(Z(s At))
At
+ G(Z(s A t))(y((s + 1) A t) - y(s A t)), s e N. (12.24) Here one may use Stratonovich formalism by converting equation (12.23) ac cording to proposition 6 of chapter 2 before writing the Euler scheme. 12.6 Problem Formulation and Equations for EKF-2 Again we consider system (12.1) and (12.2) reproduced here for conve nience dx{t) = b(x(t))dt + (n(t)dW(t), dy(t) = h(x(t))dt + a4(t)dV(t),
t > 0, x(0) = x 0 , t > 0, y(0) = 0.
(
• )
Usually one may expect that if the dispersion parameters ai, 04 are small in some sense, the signal to noise ratio is high and the process x can be well approximated by a sum of two terms: x =z+x
(12.26)
where z is the unique solution of the unperturbed (deterministic) system z(t) = b(z(t)), t > 0, z(0) = z0= x 0 .
(12.27).
Linear and Nonlinear Filtering
161
If 6 has linear growth and is locally Lipschitz, equation (12.27) has a unique (absolutely continuous ) solution on any finite time interval. Thus x represents the random fluctuation around this deterministic flow. We approximate the equations (12.25) around this deterministic trajectory by expanding b and h around z using Lagrange formula as described below. Let / G C2(Rn) with second partials uniformly bounded, that is, sup{|| (D2f)(0
U €Rn},
(12.28)
where D2 denotes the matrix of second partials. For any pair x,z € Rn consider the function 0—►/(z + 0 ( x - z ) ) , 0 € [ O , l ] , and note that (d/dO)f{z + 0(x - z)) = Df{z + 0{x - z)), x - z).
(12.29)
Integrating this over [0,1], we obtain the Lagrange formula, f(x) = f(z) + / dO (Df(z + 0(x - z)),x - z). Jo
(12.30)
This holds for any / G C 1 . If / e C2 and D2f is uniformly bounded on Rn, then by repeated application of the Lagrange formula one can obtain f(x) = f(z) + (Df(z),x-z)+f
deU
I
(D2f(z+sO{x-z))x-z,x-z)\.
ds
(12.31) Assuming that b and h are C2 functions having second partials uniformly bounded, we can expand b and h using Lagrange formula. Thus, letting B(t) and H(t) denote the matrices B(t) = {d/dxjbiizit)), H(t) = {d/dxjhi(z(t)),
l
(12.32)
it follows from Lagrange formula that b(x(t)) = b(z(t)) + B(t)(x -z)
+ o(x - z)
h(x(t)) = h(z(t)) + H(t)(x -z)+
o(x - z).
(12.33)
This leads to the following system of equations dx(t) c^ B(t)xdt -h ai(t)dW(t),
t > 0, x(0) = x0 - x 0 ,
dy(t) - h(z(t))dt 4- H(t)x + a4(t)dV(t),t
> 0, y(0) = 0.
(12.34)
Extended Kalman Filtering
162
This is the standard linear filtering problem treated in chapter 3 with the exception that the observer equation has an additional deterministic quantity. The problem is to find the best estimate of x{t) which obviously is given by xx = = E{x{t)\tf>}. E{x(t)\F?}.
(12.35)
Thus the filtering problem has been decomposed into two subproblems. The first problem is related to the deterministic flow governed by the initial value problem (12.27), and the second problem is related to the dynamics of random fluctuation of the state and measurement determined by the system of equations (12.34). This is the classical Kalman filtering problem. Hence the results of chapter 3 apply. Accordingly, the filter equation for x is given by dx = B(t)xdt + r°(t)(dy(t)
- {h(z(t)) +
H(t)x}dt),
x(0)=0.
(12.36) (12 36) '
where T0 = K0H'R^ and K° is the solution of the differential Riccati equation K = B(t)K + + KB\t) + Qn KHR^HK, (12.37) K{0) = K0. K(Q) It follows from the above results and equation (12.26) that the best estimate is given by x{t) x{t) x(t) = z{t) + x(t) (12.38) We summarize these results in the following theorem. T h e o r e m 2 Suppose the assumptions of Theorem 1 hold with b and h in C2 having bounded second partials. Then the approximate filter equations for (EKF-2) are given by the following system of coupled deterministic and stochastic differential equations: = x0,0, z = b(z(t)),z(o) b(z(t)),z(o)=x d£(t) ~ B(t)£{t)dt + KH'R^{dy{t) K = B{t)K K = B(t)K + + KB(t)' K(0) = K0. K{0)
- h(z(t))dt - H(t)x(t)dt),i(0) + KB(t)'+Qn-KH'RllHK, Qn KHR^HK,
(12.39) = 0, (12.40) (12.41)
This is the so called modified extended Kalman filter (MEKF) proposed in [13].
Linear and Nonlinear Filtering
163
Comment 2 Note that the matrices B and H are matrix valued functions of z and hence equations (12.39)-(12.41) constitute a system of n(n + 5)/2 coupled nonlinear differential equations,with (12.40) being stochastic. Given the observation y these can be solved by any standard numerical technique. Unlike in EKF-1, (theorem 1), here (12.39) and (12.41) are deterministic and can be solved off line giving {K°yz} which can then be used for the estimator equation (12.40). In contrast, the EKF-1 equations (12.20)-(12.22) must be solved in real time C o m m e n t 3 The success of this filter depends on the size of the initial covariance matrix PQ = KQ. For example, if the Tr(Po) is large, estimation error is likely to be large. Another source of poor estimation is the exclusion of second order nonlinearities. The size or the intensity of nonlinearity can be measured by the second partials {D2bi,D2hj} which have been neglected in the above approximations. 12.7 Comparison of EKF-1 and EKF-2 with Examples In case of small noise we replace o\ by S\G\ and 04 by £204- This means that if ai,i = 1,2, are bounded and the parameters Si,i — 1,2, are small, the noise power densities are small. In this case the EKF-1 and EKF-2 equations are given by dx(t) ~ b(x(t))dt + (l/el)K0H'R^{dy{t) K°(t) = B(x{t))K°
+ K°B(x(t))'
- h(x(t))dt),x(0)
= x0.
(12.42)
+ elQn 2
- (l/e 2)K°(t)H\x{t))R^H{x(t))K°,
(12.43)
K(0) = K0, z = b(z(t)),z(o)=x(h dZ(t) ~
(12.44)
B(z(t))£(t)dt + (1/4)K°H'
(z(t))Rrf
(dy(t) - h(z(t))dt - H(t)£(t)dt),
(12.45)
5(0) = 0. K° = B(z(t))K°
+ K°B{z{t)j 2
+ e\Qu
- (l/e 2)K H(z(t))R^H(z(t))K0, K°(0) = K0.
0
(12.46)
Extended Kalman Filtering
164
It was reported in [13] that EKF-2 performs better than EKF-1 under small noise situation. This was justified by several simulation results by plotting the integral squared error = I II x{t) - x(t) ||2 dt. (12.47) Jo For fixed measurement noise e^, JT,C2 (£I) w a s plotted as a function of £1. It was found that for small values of £1, both the filters exhibit similar performance but as the noise intensity increases the performance of EKF-2 supersedes that of EKF-1. Similar results were obtained when the dynamic noise S\ was fixed and the measurement noise £2 was varied. For detailed numerical results the reader is referred to the literature [13]. Unfortunately there is no formal proof of this fact. However examining the equations of EKF-1, one may notice that in the approximation of b = E{b(x(t))\J^}, the second term of the following expression Mei,£2)
b = b(x(t)) + E< (Db(x(t))(x(t)
- x(t)) + higher order terms) | ^
has been omitted using the argument that Db(x(t)) is J^ adapted and hence the conditional expectation of the second term is zero. The same comment applies to h. This is correct if the solution of equation (12.42) is precisely x as defined by the expression (12.8). But this equation is only an approximation and hence it's solution cannot be exactly x, as the notation suggests, and hence the omission is not justified. On the other hand inclusion is also not useful since x is not known. This kind of problem is avoided in EKF-2 which includes both the first and second terms. 12.8 Equations for EKF-3 We expect that inclusion of second order terms may eliminate the discrep ancy mentioned above . If both b and h are C 3 having third partials uniformly bounded, then by use of Lagrange formula one can justify that k = bi(x(t)) + (l/2)Tt{D%(x(t))K(t)} hi = hi(x(t)) + (l/2)Tr{D2hi(x(t))K(t)}
+ o(\\ x-x + o(|| x-x
|| 2 ) || 2 ).
(12.48)
Define the vectors b(x(t),K(t))
= {bi(x{t)) + (l/2)Tr{D\(x(t))K(t)},i
h(x(t),K(t))
= {hi(x(t)) + (l/2)Ti{D2hi(x(t))K(t)},i
= l,2...,n} = l,2...,m}. (12.49)
Linear and Nonlinear Filtering
165
Now we replace the equations of EKF-1 by dx(t) ~ b(x(t),K°{t))dt K°(t) = B(x(t))K°
+ K°HRlZ(dy(t)
+ K°B(x{t)j
+ Qn -
- h(x(t),K°{t))dt),x(0)
= x0. (12.50) K0(t)rf(x(t))R£H(x(t))K0,
K(0) = K0. (12.51) Thus we have yet another modification of EKF-1. One may expect this model to work better than EKF-1. We propose this as EKF-3. T h e o r e m 3 Suppose the assumptions of theorem 2 hold with b and h in C 3 having bounded third partials. Then the approximate filter equations for (EKF-3) are given by the system of coupled stochastic differential equations (12.50) and (12.51). Again, one can solve this recursively as the data y is presented in real time and obtain a better approximations of x(t) and K°(t). The extended Kalman filters are expected to work well under small noise situation. A formal error analysis of these filters along the lines suggested in [13], [80] should be useful for applications. Other useful approximation techniques can be found in [81] and [82]. C o m m e n t 4 An interesting exercise for the reader would be to evaluate the peformance of EKF-3 consisting of equations (12.50) and (12.51) by comparing their solutions with those of Zakai equation (13.37B) of chapter 13. The Zakai equation presented in chapter 13 gives the exact estimate.
167
C H A P T E R 13 N O N L I N E A R FILTERING
13.1 Introduction In this chapter we consider nonlinear filtering proper, without any approximation. We treat both continuous time Markov process and a class of jump processes. We develop the so called Zakai equation which is the counter part of linear filtering discussed in chapters 3 - 9. From the Zakai equation we derive the Kushner equation and