{'fraction_non_alphanumeric': 0.06333042910041385, 'fraction_numerical': 0.016009583968634285, 'mean_word_length': 3.8906790945406127, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 24, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Interval-valued estimation for discrete-time linear systems: application to switched systems

This paper proposes a new framework for constructing interval-valued state estimators for discrete-time linear and switched linear systems. Our main results are (i) the derivation of the tightest interval-valued estimator for linear discrete-time systems; (ii) a systematic design method for interval-valued state estimators; (iii) an application of the proposed estimation framework to switched linear systems.


Introduction
Recovering the hidden state of a dynamic process is a problem of major importance in many decision-making systems e.g., control or monitoring systems. State estimation methods rely on a mathematical model of the system which relates the unknown state to the observed input and output of the system. However, often in practice, the model and the observed signals are uncertain and hence described by set-valued (in particular R n interval-valued) functions of time. As initiated in [1], this form of uncertainty prompts the necessity of constructing intervalvalued estimators which return at any time instant the set of all the possible values of the state. This type of estimators (observers) were investigated in a series of papers for a variety of system classes: continuous-time Linear Time Invariant (LTI) [2,3,4,5,6,7], discrete-time linear systems [8,9,10,11], linear parameter-varying systems [12,13] and some specific classes of nonlinear systems [14,15]. For more on the interval observer literature we refer to a recent survey reported in [16].
We consider in this paper the problem of designing interval-valued estimators for two classes of dynamic systems: discrete-time linear systems (LS) and switched linear systems (SLS). Concerning linear systems, many estimators exist in the literature as recalled above. However, a question of major importance that has not received much attention so far is that of the size of 1 the estimated interval set. In effect, there exist in principle infinitely many interval estimators that satisfy the outer-bounding condition for the state trajectories of the system of interest. But the best estimator would be the one that generates the smallest possible interval sets (in some sense) that contains the actual state. We therefore consider here the question of how to characterize the tightest interval-valued estimator for discrete-time linear systems. Note that this question was also tackled in our previous works [2,17] but for the case of continuous-time LTI systems. The discrete-time case is sufficiently different to deserve a separate treatment. Note that the concept of tightness (of the interval-valued estimator) introduced here is different from the notion of optimal design used in, for example, [18,19,3,8]. The first characterizes the intersection of all intervals which contain the true state while the second refers to the selection of the parameters which optimize a certain performance function (e.g., peak-to-peak gain or H ∞ norm) for a given parametrized structure of estimators. Indeed both approaches can be nicely combined as follows: select an optimal gain of the observer in the sense of some performance index an then construct the tightest estimator for this value of the gain using the approach of the current paper. Our approach leads to a tight estimator in convolutional form whose numerical implementation may, in the general case, be computationally costly. We therefore briefly discuss its realizability by an LTI state-space form. Contrary to the continuous-time case, the realization problem is numerically tractable in discrete-time. In case a state-space realization does not exist, we consider some over-approximations of the tightest estimator.
The second part of the paper extends the discussion to switched linear systems. An increasing number of interval observer design methods are being proposed for this class of systems (see e.g., [20,21,18,22]). The main challenge that still needs to be overcome for most of these methods is the conservatism of the design conditions. Here, we first discuss the expression of the tightest estimator for switched linear systems. We then consider a less computationally demanding relaxation of this tightest estimator and propose a potentially less conservative design condition for the existence of a stable interval-valued estimator under arbitrary switchings. Moreover, the search for the estimator's parameters is numerically tractable and more precisely, expressible in the form of a convex feasibility problem.
Outline. The remainder of the paper is organized as follows. In Section 2, we set up the estimation problem and present the technical material to be used later for designing the estimator. In Section 3 we discuss estimators in open-loop, that is, estimators that result only from the simulation of the state transition equation without any use of the measurement. Section 4 discusses a systematic way of transforming a classical observer into an interval-valued estimator in the new estimation framework. Section 5 considers an extension of the design method to switched linear systems. Section 6 reports some numerical results confirming tightness of the proposed estimator. We conclude the paper in Section 7.
Notations. R (resp. R + ) is the set of real (resp. nonnegative real) numbers; Z (resp. Z + ) is the set of (resp. nonnegative) integers. For a real number x, |x| will refer to the absolute value of x. For x = [x 1 · · · x n ] ⊤ ∈ R n , x p will denote the p-norm of x defined by x p = (|x 1 | p + · · · + |x n | p ) 1/p , for p ≥ 1. In particular for p = ∞, x ∞ = max i=1,...,n |x i |. For a matrix A ∈ R n×m , A F is the Frobenius norm of A defined by A F = tr(A ⊤ A) 1/2 (with tr referring to the trace of a matrix). If A = [a ij ] and B = [b ij ] are real matrices of the same dimensions, the notation A ≤ B will be understood as an elementwise inequality on the entries, i.e., a ij ≤ b ij for all (i, j). |A| corresponds to the matrix [|a ij |] obtained by taking the absolute value of each entry of A. For a square matrix A, ρ(A) will refer to spectral radius of A ; for a finite set Σ = {A 1 , . . . , A m } of square matrices, ρ(Σ) will be the joint spectral radius of Σ and |Σ| will refer to the set {|A 1 |, . . . , |A m |}. In case A and B are real square matrices, A B (resp. A ≻ B) means that A − B is positive semi-definite (resp. positive definite).

Estimation problem settings
Consider a Linear Time Invariant (LTI) system described by where x(t) ∈ R n , w(t) ∈ R nw , y(t) ∈ R ny , are respectively the state, control input and output at time t ∈ Z + ; {v(t)} ⊂ R ny are unknown but bounded disturbances. A ∈ R n×n , B ∈ R n×nw , C ∈ R ny×n are some real matrices. Throughout the paper we make the following assumption concerning the external signals acting in system (1).
To begin with, let us fix some notation. Consider two vectors x and x in R n such that x ≤ x with the inequality holding componentwise. An interval [x, x] of R n is the subset defined by We consider in this paper the problem of designing an interval-valued estimator for the state of the LTI system (1). Considering that the initial state x(0) of (1) lives in an interval of the form [x(0), x(0)] ⊂ R n and that the external signals w and v are subject to Assumption 1, we want to estimate upper and lower bounds x(t) and x(t) for all the possible state trajectories of the uncertain system (1).
Definition 1 (Interval estimator). Consider the system (1) and pose b and Y t = y(0), . . . , y(t) . Consider a dynamical system defined by where F t and G t are some functions indexed by time, (x(t), x(t)) denote the output for any t ∈ Z + and X 0 = (x(0), x(0)). The system (3) is called an interval-valued estimator for system (1) if: 1. Any state trajectory x of (1) satisfies Here the inputs of system (3) are the signals b w , b v , y and the vector X 0 . By BIBO stability we mean here that x and x in (3) are bounded whenever those input signals have bounded infinity norms. (3) is in the general form of a causal dynamic system. As such it is not necessarily realizable in the form of a discrete-time state-space representation. This is why we will prefer throughout this paper the terminology interval-valued estimator to interval observer (the latter being conventionally used to refer to a state-space realization of the estimator, when it exists).

Remark 1. The estimator as expressed in
We will discuss two types of interval-valued estimators: open-loop interval estimators (or simulators) where (3) does not depend on the measurements Y t and the measurement noise V t ; and closed-loop interval estimators where measurement is fed back to the estimator. There are in principle infinitely many estimators that qualify as interval estimators in the sense of Definition 1. It is therefore desirable to define a performance index (measuring e.g. the size of the estimator) which selects the best estimator among all. We will be interested here in the smallest interval estimator in the following sense.
Definition 2. Let S denote a subset of R n . An interval I S ⊂ R n is called the tightest interval containing S if S ⊂ I S and if for any interval J of R n , S ⊂ J ⇒ I S ⊂ J .
In other words, the tightest interval I S "generated" by S is the intersection of all intervals containing S. appeared in [23] and was proved using a different line of arguments. The approach taken here is tailored to proving the second part, namely the fact that C(c, p) is indeed the tightest interval containing I. This is a key result in determining the tightest interval-valued state estimator.

Additional technical material
For easier reference in this paper, we now state a couple of facts to be used in the stability proofs and in the bounding conditions. The next lemma recalls some useful basic facts from [24,Chap. 8].
Lemma 2. Let A and B be matrices of compatible dimensions. Then the following properties hold (componentwise): The last equation just states that A and |A| have the same Frobenius norm.
Definition 3 (Joint spectral radius of set of matrices [25]). Let Σ = {A 1 , . . . , A m } be a finite set of square matrices in R n×n . Let · denote an arbitrary norm on R n×n . The joint spectral radius of Σ denoted ρ(Σ) is defined as the number In the particular case where the set Σ contains a single matrix, the joint spectral radius reduces to the usual spectral radius of that single member of Σ. As argued in [25], the joint spectral radius of a compact set of matrices always exists and is independent of the norm involved in its definition (12). For Σ = {A 1 , . . . , A m }, we use the notation |Σ| to denote the set of matrices |Σ| = {|A 1 |, . . . , |A m |} obtained by taking the absolute value of all matrices in Σ. We also define similarly Ψ(Σ) = {Ψ(A 1 ), . . . , Ψ(A m )} with Ψ(·) defined as in (9).
Proof. The inequality (13a) follows directly from the identities (11b), (11d) and (11e) stated above. In effect, since, as remarked above, the joint spectral radius is independent of the norm used in its definition (12), let us employ the Frobenius norm. Then Note that the inequality above is a consequence of (11b), (11d) and (11e) by which . In virtue of the relation (10), to obtain (13b), it suffices to use the invariance property of the joint spectral radius under similarity transformation [25]. In effect, according to (10) all matrices contained in Ψ(Σ) are commonly reducible to block-diagonal matrices in the sense that there exists a matrix T n as defined after Eq. (10) such that for all A i ∈ Σ ⊂ R n×n , By then applying Proposition 1.5 in [25] and the inequality (13a), we have ρ(Ψ(Σ)) = max (ρ(Σ), ρ(|Σ|)) = ρ(|Σ|).
In the special case where Σ is reduced to a singleton, (13a) recovers the more standard relation ρ(A) ≤ ρ(|A|).
Proof. Clearly, it follows from the assumption of the lemma that for any (i 1 , . . . , i q ) ∈ S q , there is (j 1 , . . . , j q ) ∈ S q such that 0 ≤ A i 1 · · · A iq ≤Ā j 1 · · ·Ā jq . The result then follows by applying the statement (11d) of Lemma 2.
3 Open-loop state interval estimator for LTI systems

Open-loop simulation: the best interval estimator
We first discuss a simulation (that is, an estimation without using the measurement) of the state trajectory of (1) under an uncertain input sequence {w(t)} and when the initial state x(0) is drawn from a known interval set. For this purpose, we assume that the matrices A and B have fixed and known values and further, that A is a Schur matrix. Then designing the tightest estimator boils down to searching for the smallest sequence (in the sense of Definition 2) {[x(t), x(t)] : t ∈ Z + } of interval sets of R n which bound all the possible state trajectories generated by {w(t)} and the uncertain initial state through the first equation of (1). Let (c x (0), p x (0)) and (c w (t), p w (t)), t ∈ Z + , denote the center-radius representations for the interval-valued initial state [x(0), x(0)] and uncertain input [w(t), w(t)] respectively. Then the 7 next theorem characterizes the tightest interval-valued state estimate in open-loop for system (1). where define the tightest (open-loop) interval-valued estimator for system (1) in the sense of Definition 2.
Proof. The proof is an immediate consequence of Lemma 1. In effect, applying repeatedly the first equation in (1) yields with the notation w 0:t defined by w 0:t = [w(0) ⊤ · · · w(t) ⊤ ] ⊤ . Then by applying Lemma 1 with z and f replaced by x(0) and w 0:t−1 , and M and N replaced by A t and A t−1 B · · · AB B respectively, we can conclude that the interval sequence defined by (14)- (15) is a bounding one for the state of system (1) and is also the tightest. As to the BIBO stability, it is also immediate since A is Schur stable.
Applying directly Eqs (14) and (15) at each time step to compute c x and p x may be very costly (and even unaffordable) when the time horizon for estimation gets large. It is therefore desirable to search instead for a one-step ahead difference equations for implementing the derived tightest estimator. In this respect, we can remark that c x in (14) can be easily realized by a state-space representation of the form However, realizing p x in (15) is quite challenging in general. Though in the specific situations where the entries of A and B have the same sign, p x satisfies p x (t + 1) = |A| p x (t) + |B| p w (t).

Exact state-space realization of the estimator
In a more general situation one can search for linear time-invariant realization of system (15) (whose input and output are respectively p w and p x ) independently of the class of inputs. The question is that of finding a set of matrices (A, and H is the impulse response of the system (15) defined by ]. This can be expressed in term of a rank condition. For any positive integers (i, j) consider the block Hankel matrix defined by Then a necessary and sufficient condition for the existence of an LTI realization of system (15) is obtained as follows [26, p.125]. (15) is LTI realizable in finite dimension if and only if there exist integers r, l and m such that

Theorem 2. System
Standard realization algorithms can be employed to compute, whenever the condition of Theorem 2 is satisfied, a minimal LTI realization (A,B, C) of (15). For more on this matter, the interested reader is referred to, e.g., [26,27,28].

Over-approximations
When the realizability condition (19) fails to hold, then obtaining the tightest interval estimator requires computing the smallest radius from its convolutional expression given in (15). However this might become quickly impractical as time goes to infinity. So, in practice, by default of being able to realize p x with a finite-dimensional state-space representation, a relaxation may be necessary. Here we discuss two methods for overestimating p x (t).

A truncated approximation
The first approximation method relies on an expansion of x(t) over a sliding time horizon of fixed size. More specifically, by noting that for some fixed q, we can invoke Lemma 1 to obtain an overestimate of p x as given in the following proposition. Proposition 1. Let q be a fixed positive integer. Consider the signalp x,q : with A and B being the matrices of the system (1) and p x (0) and p w defined as in the statement of Theorem 1. Then the following statements are true: where c x and p x are defined in (14)-(15).
To prove the second statement, it suffices to show that there exists an integer q ⋆ such that ρ(|A q |) < 1 ∀q ≥ q ⋆ . To see this, recall that ρ(A) < 1 implies that lim q→+∞ A q F = 0. Hence, there exists an integer q ⋆ such that A q F < 1 for all q ≥ q ⋆ . On the other hand we have 1 What Proposition 1 says is that if we choose appropriately the integer q, then the sequence of intervals [c x (t) −p x,q (t), c x (t) +p x,q (t)], t ∈ Z + , withp x,q (t) expressed as in (20), defines an interval estimator for system (1) in the sense of Definition 1. This interval estimator always contains the tightest one characterized in Theorem 1. Naturally, the larger q, the higher the computational cost associated with the implementation but the smaller the radiusp x,q (t) and the errorp x,q (t) − p x (t).
In contrast, the resulting radiusp x,1 (t) is larger, that is, the associated bounds of the intervalvalued estimate are looser. One can further observe that the interval estimator (22) can indeed be written in the more classical observer form (see Remark 2): where Ψ is defined as in (9).

Over-approximating the input
The second approximation method makes use of the following proposition (whose proof follows by simple calculations).
Proposition 2. Assume that p w (t) = p w (0) for all t ∈ Z + , i.e., p w is constant. Then the sequence {p x (t)} in (15) can be realized as follows: with state (M (t), r(t)) ∈ R n×n × R n and I n being the identity matrix of order n.
Indeed by Assumption 1, {p w (t)} is bounded. Therefore, let r o be the vector in R nw whose i-th entry denoted r o i is defined by r o i = max t∈Z + p w,i (t) where p w,i (t) refers to the i-th entry of p w (t). Then {w(t)} satisfies c w (t) − r o ≤ w(t) ≤ c w (t) + r o and hence (c w (t), r o ) is a valid but looser interval representation for the input signal w which fulfills the condition of Proposition 2. As a consequence, replacing p w (0) in (23) with r o gives a computable realization of an interval estimator for the state of system (1).

Closed-loop state estimator 4.1 A formal characterization of the best linear estimator
In case the system (1) is not stable but detectable 2 , it is possible to find a matrix gain L such that A − LC is Schur stable. We can then construct an interval-valued state estimator from the classical observer form. For example, departing from the structure of the classical Luenberger observer, it is easy to see that the true state of system of (1) satisfies where Since this equation has the same form as (1) and L is assumed be such that A − LC is Schur stable, all the preceding discussion in Section 3 is applicable to the closed-loop case. Note that beyond the possibility of retrieving stability from linear output injection as in (24), it is intuitive that exploiting the measurements can help tighten further the interval-valued estimate of the state. For a given L ∈ L L ∈ R n×ny : ρ(A − LC) < 1 , define E L to be the set of all pairs of vectorvalued signals (x, x) on Z + which (lower and upper) bound the state x under the constraint (24), We give below a formal characterization of the best estimator over all members of E ∪ L∈L E L .

Theorem 3. Consider the LTI system (1) under Assumption 1. Then the sequence of intervals
for all t ∈ Z + and all i = 1, . . . , n, witĥ define the tightest interval-valued state estimator for system (1) within the class E in the sense of Definition 2.
Here, notation of the typeĉ i (t, L) refers to the i-th entry of the vectorĉ(t, L) ∈ R n .
If we now let L vary over L, then naturally the pair (x ⋆ , x ⋆ ) as defined in (25)-(26) gives the tightest interval-valued state estimator for system (1) of the class E.
We note that (x ⋆ , x ⋆ ) does not necessarily lie in E. It is also worth pointing out that from a computational perspective, the estimator (x ⋆ , x ⋆ ) defined by (25)-(26) is very hard to handle. We will therefore study further the type of approximation given in Proposition 1 for a fixed value of L ∈ L.

A systematic design method
In virtue of Lemma 1, an interval estimator can, in principle, be obtained from any standard linear observer. A general recipe for constructing such an interval estimator consists in (i) adjusting the equation of the classical observer so that it is satisfied by the true state as in (24); and then (ii) applying Lemma 1 either to (24) directly or to a truncated expansion of it similar to the one discussed in the beginning of Section 3.3.1. Following this logic, let us apply the truncated interval estimator stated in Proposition 1 to the system (24) (which, recall, is a standard observer-based expression of the state of system (1)). Denote with (c cl x , p cl x,q ) the center-radius representation of the resulting interval-valued estimator. Then for a given L ∈ L, we have c cl x (t) =ĉ(t, L) ∀t ∈ Z + , withĉ(t, L) defined in (27). As already mentioned, such a vector-valued signal c cl x is realizable in state-space form by the following difference equation As to the radius p cl x,q : Z + → R n + , it is defined by Here, (c s (t), p s (t)) ∈ R ns × R ns + , n s = n w + 2n y , is a center-radius representation of s(t) for t ∈ Z + . In explicit expressions, we have c s (t) = [c w (t) ⊤ y(t) ⊤ c v (t) ⊤ ] ⊤ and p s (t) = [p w (t) ⊤ 0 ⊤ ny p v (t) ⊤ ] ⊤ with 0 ny denoting a n y -dimensional vector containing zeros. In the special case where q = 1, the pair p cl x,q can be very simply realized as In this latter particular case, by expressing x(t) = c cl x (t) − p cl x,1 (t) and x(t) = c cl x (t) + p cl x,1 (t) from the solution (c cl x , p cl x,1 ) of the system given in (29) and (31) respectively, we obtain a dynamical system which is similar to the interval observer given in [29]. Note however that both are not the same as the current expression provides a more flexible way for handling the measurement noise. Further, as will be stated below, our condition of stability (which is ρ(|A − LC|) < 1) reads very simply in this case.
The following statement can be obtained.
Theorem 4. Consider the system (1) under Assumption 1. If the pair (A, C) is detectable, then there exists a matrix gain L ∈ R n×ny and an integer q ⋆ such that for any q ≥ q ⋆ , (c cl x , p cl x,q ) expressed in (29)-(30) defines an interval-valued estimator for system (1). In particular, if ρ(|A − LC|) < 1, then (c cl x , p cl x,1 ) given in (29) and (31) respectively, defines an interval-valued estimator for system (1).
Proof. We already know from the first statement of Proposition 1 that (c cl x , p cl x,q ) satisfies the bounding condition of Definition 1 in the sense that the state of system (1) obeys c cl . It remains to prove the BIBO stability of the system (p x (0), p s ) → (c cl x , p cl x,q ). For this purpose, recall from control theory that the detectability property of (A, C) guarantees the existence of L ∈ R n×ny such that ρ(A − LC) < 1. We can then find, as shown in the proof of Proposition 1, point 2), an integer q ⋆ such that ρ(|A − LC| q ) < 1 for any q ≥ q ⋆ . Hence for any L satisfying ρ(A − LC) < 1 there exists q ⋆ such that for any q ≥ q ⋆ , (c cl x , p cl x,q ) constitutes an interval-valued estimator for system (1) in the sense of Definition 1. In the particular case where q is taken equal to 1, the BIBO stability condition for (p x (0), p s ) → (c cl x , p cl x,1 ) holds if ρ(|A − LC|) < 1 hence proving the last statement of the theorem.
To obtain the estimator (c cl x , p cl x,q ) we just need to select a matrix L ∈ R n×ny obeying ρ(A−LC) < 1 and then find the minimum q ⋆ by testing incrementally whether ρ(|A−LC| q ) < 1 for q = 1, 2, . . . until obtaining a positive return. From a numerical standpoint, obtaining L and q ⋆ under the stability constraint is quite easy by standard routines. Observability (or just detectability) of (A, C) is a sufficient condition for ensuring the existence of an interval-valued estimator of the form (c cl x , p cl x,q ). Now if we impose q = 1 for the design (for example, for computational reasons), then L must satisfy ρ(|A − LC|) < 1 as prescribed by Theorem 4. In this latter case, a question is how to effectively select a matrix gain L ∈ R n×ny , when possible, so as to realize this condition. An answer is provided by the following lemma. A similar (but only sufficient) result was obtained in [29].
(b) There exist a diagonal positive definite matrix P ∈ R n×n + and some matrices Y ∈ R n×ny , X ∈ R n×n + satisfying the conditions: Whenever (32) holds, the matrix L in (a) is given by L = P −1 Y .
Proof. Since |A − LC| is a nonnegative matrix, we can apply Theorem 15 in [30, p. 41] to state that ρ(|A − LC|) < 1 if and only if there exists a diagonal and positive definite matrix P such that |A − LC| ⊤ P |A − LC| − P ≺ 0, a condition which can be rewritten as where Y = P L. Now by posing X = |P A − Y C| and making use of the Schur complement trick, we see that (a) ⇒ (b).
Let us now prove that (b) ⇒ (a). It is clear that if (b) holds then the first equation of condition (32) implies, by the Schur complement rule, that X ⊤ P −1 X − P = (P −1 X) ⊤ P (P −1 X) − P ≺ 0 which in turn means that P −1 X is a Schur matrix, i.e., ρ(P −1 X) < 1. Moreover, it follows from the last condition of (32), the nonnegativity of P and its diagonal structure (upon multiplying each side on the left by P −1 ), that 0 ≤ P −1 |P A − Y C| = |A − LC| ≤ P −1 X. By applying Lemma 4, we conclude that ρ(|A − LC|) ≤ ρ(P −1 X) < 1.
Lemma 5 shows that one can compute the observer gain L efficiently by solving a feasibility problem which is expressible in terms of Linear Matrix Inequalities (LMI) [31]. In comparison to some other results [19,18,16], we do not put any positivity constraint on A − LC for the existence of L hence, yielding less conservative design conditions. In effect, if we introduce the notations L pos = {L ∈ R n×ny : ρ(A − LC) < 1, A − LC ≥ 0} and L abs = {L ∈ R n×ny : ρ(|A − LC|) < 1} for a given pair (A, C), then clearly, L pos ⊂ L abs . As a result, a search of the matrix gain L over L abs is more likely to be successful than a search over L pos .

Remark 4.
In addition to ensuring stability as required by Theorem 4, the matrix gain L could be selected so as to achieve a certain level of convergence speed or to optimize a certain performance index, expressed for example in term of a norm of the system (p x (0), p s ) → p cl x,q defined in (30). Such an approach was adopted in, for example, [32,19,3]. Here however, our focus is rather on characterizing tightness in the sense of Definition 2 for a given matrix gain L. 15 We consider now applying the estimation method discussed earlier to switched linear systems described by equations of the form where (x, y, w, v) have the same significance as in (1), σ : Z + → S with S = {1, . . . , s} being a finite set, is the switching signal and (A i , B i , C i ), i ∈ S, are the system matrices. We will consider that (w, v) are still subject to Assumption 1.

Settings for the state estimation
Assumption 2. The switching signal σ involved in (34) is taken to be arbitrary but known.
The first step of the estimator design method is to observe that for any set of matrices {L i ∈ R n×ny : i ∈ S}, the state of the switched linear system (34) obeys where σ is the same switching signal as in (34), Let Φ denote the transition matrix function of (35) defined for all (t, t 0 ) with t ≥ t 0 , by Then the state x(t) of (34) can be expressed as The second ingredient is an appropriate concept of stability on the homogenous part of (35) defined by z(t + 1) = F σ(t) z(t). In view of Assumption 2, this notion of stability must hold regardless of the switching signal. It is therefore merely a property of the finite set Σ F {F i ∈ R n×n : i ∈ S} of square matrices, hence the following definition.
Definition 4 (Stability of a finite set of matrices). The homogenous part of the discrete-time SLS (35) (or equivalently, the finite collection Σ F of matrices) is called • uniformly stable if there is c > 0 such that for all q ≥ 1 and for all (i 1 , · · · , i q ) ∈ S q , F i 1 · · · F iq 2 ≤ c • uniformly exponentially stable (u.e.s.) if there exist some real numbers c > 0 and λ ∈ ]0, 1[ such that for all q ≥ 1 and for all (i 1 , · · · , i q ) ∈ S q , F i 1 · · · F iq 2 ≤ cλ q . 16 An algebraic characterization of the stability of a switched linear system (or equivalently, the stability of a finite set of square matrices) was obtained in [33] in terms of the joint spectral radius as follows.
By Lemma 3, a direct corollary of this theorem is that there is an equivalence between stability of |Σ| and that of Ψ(Σ). Also, Σ is stable whenever |Σ| is stable. Now, applying Lemma 1 to (36) shows that for given gains L i , the pair (c sls x , p sls x ) given by defines the tightest interval-valued estimator for the SLS (34) provided that the BIBO stability condition of Definition 1 is satisfied. And it can be easily seen that the dynamic systems defined by (37) and (38) are BIBO stable if Σ F is u.e.s. Note that, like in Theorem 3, we can also optimize over all sets {L i } i∈S of gains that render Σ F stable. Concerning the implementation aspects, it is useful to observe that the function c sls x in (37) satisfies the one step-ahead equation with c sls x (0) = c x (0). In contrast, realizing p sls x in finite dimension is, like in the case of linear systems, still a challenging problem. Nevertheless, a time-invariant switched linear state-space realization of (38) can, under certain conditions, be obtained by resorting to the realization theory of switched linear systems presented in [34] but we will not elaborate more on this problem here. Turning instead to over-approximations of the estimator, it is interesting to see that the truncated estimate discussed in Section 3.3.1 is applicable here as well. In particular, when the truncation order q is equal to 1, we obtain p sls withĉ sls x (0) = c x (0) andp sls x (0) = p x (0). Thanks to the statement (13a) of Lemma 3 and Theorem 5, these latter equations define an interval estimator if is u.e.s. in the sense of Definition 4. Hence the question we discuss next is how to select the matrix gains L i ∈ R n×ny so as to render |Σ F | u.e.s., hence making (40)-(41) a valid interval estimator. Observe that |Σ F | is a positive discrete-time switched linear system just as those studied in [35] (in continuous-time) considered under arbitrary switching signal.

Guaranteeing the stability condition
In this section, we derive a tractable condition for computing effectively gains L i which ensure exponential stability of |Σ F |. For this purpose, we will need the following lemma.
Lemma 6. Consider two finite collections of nonnegative matrices Σ = A i ∈ R n×n + : i ∈ S and Σ = Ā i ∈ R n×n + : i ∈ S , where S and S are finite sets with possibly different cardinalities. If for any i ∈ S, there is j ∈ S such that A i ≤Ā j , then Σ is uniformly stable (resp. u.e.s.) whenever Σ is uniformly stable (resp. u.e.s.).
Theorem 6 shows that the problem of designing an interval-valued estimator in the form (40)-(41) for the SLS system (34) can be relaxed to the problem of solving the convex feasibility problem (44)-(45) for the matrix gains L ii ∈ R n×ny , i ∈ S. Hence a numerical solution can be efficiently obtained by relying on existing semi-definite programming solvers.

Remark 5.
Similarly as in the case of LTI systems (see Theorem 4), we can construct a q-order truncated interval estimator in the switched system case as well. In effect, it can be shown that for Σ F = {F i : i ∈ S}, ρ(Σ F ) < 1 implies the existence of some q ⋆ such that ρ(|Σ q F |) < 1 for all q ≥ q ⋆ with the notation |Σ q F | defined by |Σ q F | = {|U 1 · · · U q | : U i ∈ Σ F , i = 1, . . . , q} (i.e., |Σ q F | is the set of matrices formed as the product of q members of Σ F , taken in absolute value. Based on this fact, we can search for the {L i } by dropping the absolute values in the stability condition (43). The associated LMI takes the form with variables Y ji ∈ R n×ny , (i, j) ∈ S 2 , P i ∈ R n×n (positive-definite and no longer diagonal), i ∈ S, γ > 0. By then selecting an appropriate value for q, the pair (c sls x , p sls x,q ) : Z + → R n × R n + defined respectively in (39) and (46) (see below) constitute an interval-valued estimator for the switched system (34), The advantage of such an estimator is that its (relaxed) synthesis conditions (analogues of (44)-(45)) are less conservative. Its inconvenience is an increase of computational cost in the numerical evaluation of p sls x,q in case q is taken large. 19 This section reports some simulation results that illustrate the performances of the interval estimators discussed in the paper.

An example of linear system in open loop
We first consider a linear system in the form (1) in an open-loop configuration, that is, without making use of any measurement. In order to be able to implement all the estimators discussed in Section 3, the dynamic matrix A is selected such that ρ(|A|) < 1, The set of initial states is defined by c For any t ∈ Z + , we let the input intervals be defined by c w (t) = sin(2πν c t) and p w (t) = 0.10| cos(2πν p t)| with ν c = 0.01 and ν p = 0.001. We first check the realizability of p x in (15) in state-space form. For the example (47), it is numerically found that the Hankel matrix H i,j defined in (18) has finite constant rank equal to 6 for sufficiently large i and j. It therefore follows from Theorem 2 that the tightest intervalvalued estimator given by (14)-(15) admits an LTI state-space realization (A, B, C, φ 0 ) as defined in Section 3.2 with minimal dimension d = 6. Hence it can be cheaply implemented.
With these data the estimators defined in Eqs (15), (23), (20) and (22) are simulated. More precisely, 100 possible state trajectories are obtained from inputs {w(t)} and initial states x(0) drawn randomly from the corresponding intervals defined above. Figure 1 shows that all the estimators enclose the true state trajectories in gray. As proved in the paper, (15) yields the smallest interval estimator. It is interesting to observe that the estimator (20) (which is implemented here for q = 1 and q = 2) can provide an estimate that is very close to the best one without q being large. The estimate delivered by the estimator (23) (with here r o = 0.3 ≥ p w (t) for all t; see Section 3.3 for a definition of r o ) is a little worse but the worst of all on this example is the result returned by (22) which gives a quite large interval set.

An example of switched linear system
We now consider an example of switched linear system in the form (34) with matrices (A i , B i , C i ) defined as follows:  The simulation is carried out for the closed-loop scenario in the following setting: the set of initial conditions and the set of admissible input signals are kept the same as in Section 6.1. As to the measurement noise {v(t)}, it is assumed to live in the constant interval [−0.1, 0.1]. We then solve (44)-(45) to find observer stabilizing gains L i and plug them in (40)-(41). Finally, estimating the state trajectory of the SLS example described above using the tightest estimator (37)-(38) and the one in (40)-(41) gives the result depicted in Figure 2. Here the switching signal is piecewise constant with dwell time of 30 time samples in each mode. Again, it can be noticed that the actual state is effectively enclosed by both estimators and that the claimed property of tightness is supported by the empirical evidence.

Conclusion
In this paper we have presented a new approach to the interval-valued state estimation problem. The proposed framework is mainly discussed for the case of discrete-time linear systems and later, extended to switched linear systems. In particular, we have derived the tightest interval estimator which enclose all the possible state trajectories generated by discrete-time linear (and switched linear) systems. Such an estimator can, under some conditions, be realized in an LTI state-space form. When this condition fails to hold, alternative over-approximations can be considered. Considering one of those approximations in the form of one-step ahead state-space representation, we propose a method to compute the parameters of the estimator by solving convex feasibility problems.