done in Lemma 7.2 (in the Appendix), where it is shown that
pN, n = u Mnz.
(126)
T, N
Now, for a given T and N, we can obtain an upper bound G
for G using the lower bounds
FT( x), FT, N( x) and FN( x), as follows
∞
T, N
G
=
1 − max{ FT( x), FT, N( x), FN( x)} dx.
(127)
0
86
Discrete Time Systems
We do so in the next theorem.
Theorem 4.2. Let T and N be two given positive integers with N 0 ≤ T ≤ N and such that for all
0 ≤ m < 2 N, | SN
m | ≥ N 0 ⇒ φ(∞, SN
m ) < ∞ . Let J be the number of sequences such that O( ST
m) has
full column rank. Let E 0
0 and Ej, 0 < j ≤ J denote the set of numbers Tr φ(∞, STm) , 0 < m ≤ J,
arranged in ascending order, (i.e., Ej = Tr φ(∞, STm ) , for some m
j
j, and E 0 ≤ E 1 ≤ · · · ≤ E f ). For
each 0 ≤ j < J, let πj = ∑ mj P( ST) , and let M, u and v be as defined as in Lemma 4.3. Then, an
k=0
k
upper bound for the EEC is given by
T, N
G ≤ G
,
(128)
where
T, N
T
T, N
N
G
= Tr( G 1 + G 2 + G 3 ),
(129)
and
J
T
G 1 = ∑(1 − πj)( Ej+1 − Ej)
(130)
j=0
N−1 N
T, N
0 −1
∗
∗
G 2
= ∑ ∑ λl(1 − λ) j− l
j!
P ( j + 1) − P ( j)
(131)
l!( j − l)!
j= T l=0
∞
N
∗
∗
G 3 = ∑ u MN+ jz{ Aj( AP ( N) A + Q − P ( N)) A j}.
(132)
j=0
Moreover, if A is diagonalizable, i.e.
A = VDV−1,
(133)
with D diagonal, and
max |eig( A)|2 ρ < 1,
(134)
where
ρ = (max |sv M|),
(135)
then the EEC is finite and
N
G 3 ≤ u MNz Tr(Γ ),
(136)
where
Γ
X 1/2 V −1 ⊗ V Δ X 1/2 V −1 ⊗ V
(137)
X
APA + Q − P.
(138)
Also, the i, j-th entry [Δ] i, j of the n 2 × n 2 matrix Δ is given by
√
[Δ]
2 N 0 − 1
i, j
−
→ −
→ .
(139)
1 − ρ[ D ] i[ D ] j
Proof: First, notice that FT( x) is defined for all x > 0, whereas FT( x) is defined on the range
P ( T) < x ≤ P ( N) and FT( x) on P ( N) < x. Now, for all x ≥ p∗( T), we have
On the Error Covariance Distribution for Kalman Filters with Packet Dropouts
87
N 0−1
FT( x) =
∑ P( ST) =
λl(
j
1 − ∑
1 − λ) T− l
T!
,
(140)
l!( T − l)!
j:| ST|≥ N
l=0
j
0
which equals the probability of receiving a sequence of length T with N 0 or more ones. Now,
for each integer 1 < n < N − T, and for p∗( T + n) ≤ x < p∗( T + n + 1), FT, N( x) represents the probability of receiving a sequence of length T + n with more than or exactly N 0 ones.
Hence, FT, N( x) is greater than FT( x) on the range P ( T) < x ≤ P ( N). Also, FN( x) measures the probability of receiving a sequence of length N with a subsequence of length T with N 0 or
more ones. Hence, it is greater than FT( x) on P ( N) < x. Therefore, we have that
⎧
⎪
⎨ FT( x),
x ≤ p∗( T)
max{ FT( x), FT, N( x), FN( x)} = ⎪ FT, N( x), p∗( T) < x ≤ p∗( N) (141)
⎩ FN( x), p∗( N) < x.
We will use each of these three bounds to compute each term in (129). To obtain (130), notice
that FT( x) can be written as
FT( x) = πi( x), i( x) = max{ i : Ei < x}.
(142)
In view of the above, we have that
p∗( T)
J
(
T
1 − FT( x)) dx = ∑(1 − πj)( Ej+1 − Ej) = G 1 .
(143)
0
j=0
Using the definition of FT, N ( x) in (112) we obtain
p∗( N)
N−1 N 0−1
(
∗
∗
1 − FT, N( x)) dx = ∑ ∑ λl(1 − λ) j− l
j!
P ( j + 1) − P ( j)
(144)
p∗( T)
l!( j − l)!
j= T l=0
= T, N
G 2 .
(145)
Similarly, the definition of FN( x) in (118) can be used to obtain
∞
∞
(
∗
∗
T, N
1 − FN( x)) dx = ∑ u Mjz Tr{ Aj( AP ( N) A + Q − P ( N)) A j} = G 3 .
(146)
p∗( N)
j=0
To conclude the proof, notice that
uMjz = < u, Mjz >
(147)
≤ u 2 Mjz 2
(148)
≤ u 2 Mj z 2
(149)
≤ u 2 M j z 2
(150)
= u 2(max sv M) j z 2
(151)
=
2 N 0 − 1(max sv M) j.
(152)
88
Discrete Time Systems
1
0.9
0.8
λ = 0.8
λ = 0.5
x)≤ 0.7
(P tP
0.6
0.5
T = 8
Shi et al.
0.40
5
10
15
20
x
Fig. 2. Comparison of the bounds of the Cumulative Distribution Function.
where max sv M denotes the maximum singular value of M. Then, to obtain (136), we use the
∗
∗
result in Lemma 7.1 (in the Appendix) with b = max sv M and X = AP ( N) A + Q − P ( N).
5. Examples
In this section we present a numerical comparison of our results with those available in the
literature.
5.1 Bounds on the CDF
In Shi et al. (2010), the bounds of the CDF are given in terms of the probability to observe
missing measurements in a row. Consider the scalar system below, taken from Shi et al. (2010).
A = 1.4, C = 1, Q = 0.2, R = 0.5
(153)
We consider two different measurement arrival probabilities (i.e., λ = 0.5 and λ = 0.8) and
compute the upper and lower bounds for the CDF. We do so using the expressions derived
in Section 3, as well as those given in Shi et al. (2010). We see in Figure 2 how our proposed
bounds are significantly tighter.
5.2 Bounds on the EEC
In this section we compare our proposed EEC bounds with those in Sinopoli et al. (2004)
and Rohr et al. (2010).
On the Error Covariance Distribution for Kalman Filters with Packet Dropouts
89
Bound
Lower Upper
From Sinopoli et al. (2004) 4.57
11.96
From Rohr et al. (2010)
-
10.53
Proposed
10.53 11.14
Table 1. Comparison of EEC bounds using a scalar system.
Bound
Lower