Home/Magazine Archive/February 2022 (Vol. 65, No. 2)/Worst-Case Topological Entropy and Minimal Data Rate.../Full Text

Research highlights
## Worst-Case Topological Entropy and Minimal Data Rate for State Estimation of Switched Linear Systems

In this paper, we study the problem of estimating the state of a switched linear system (SLS), when the observation of the system is subject to communication constraints. We introduce the concept of worst-case topological entropy of such systems, and we show that this quantity is equal to the minimal data rate (number of bits per second) required for the state estimation of the system under arbitrary switching. Furthermore, we provide a closed-form expression for the worst-case topological entropy of switched linear systems, showing that its evaluation reduces to the computation of the joint spectral radius (JSR) of some lifted switched linear system obtained from the original one by using tools from multilinear algebra, and thus can benefit from well-established algorithms for the stability analysis of switched linear systems. Finally, drawing on this expression, we describe a practical coder-decoder that estimates the state of the system and operates at a data rate arbitrarily close to the worst-case topological entropy.

Modern control systems (such as IoT, cyber-physical systems, etc.) often involve spatially distributed components that communicate through a shared, digital communication network. Due to the digital nature of the network, all data must be quantized before transmission, resulting in quantization error that can affect the performance of the observing/controlling scheme. Furthermore, in applications, the capacity of the network is often limited by cost, power, physical, and/or security constraints. Consequently, a major challenge in the design of such networked systems is to determine the minimal communication data rate required to achieve a given control task. This fundamental question has motivated a lot of research efforts from the control community in recent years, with great theoretical and practical advances; as surveyed in the works of Hespanha et al.^{8} and Matveev and Savkin^{17}.

Inspired by Shannon's work on the link between information entropy and minimal data rate for reliable communication, it was soon realized that the question of data rate requirements for networked systems has strong connections with the notion of topological entropy of these systems; see, for example, Matveev^{16} and Pogromsky and Savkin.^{19} This quantity, introduced in the late 1960s and now ubiquitous in systems theory, accounts for the growth rate of the smallest number of functions necessary to approximate the trajectories of the system with arbitrary finite accuracy on bounded time intervals (with respect to the length of the interval). It can also be seen as a measure of the rate at which information about the initial condition is generated by the system as time evolves.^{19} It is known for instance that for some classes of dynamical systems (such as time-invariant systems with forward invariant initial set), the topological entropy coincides with the minimal data rate for state estimation.^{16}

In this paper, we study discrete-time switched linear systems (SLSs). We are interested in determining the minimal data rate at which a coder needs to send information to a decoder to be able to estimate the state of the system with exponentially decreasing error (see also Figure 1 for an illustration). SLSs are systems described by a finite set of linear modes among which the system can switch over time. As a paradigmatic class of cyber-physical systems, SLSs have attracted much attention from the control community in recent years. These systems turn out to be extremely challenging in terms of control and analysis, even for basic questions such as stability or stabilizability.^{9} In particular, in contrast to LTI systems for which comprehensive eigenvalue-based expressions for the topological entropy and the minimal data rate for state estimation are available, none of these quantities are well understood for SLSs. Several theoretical and practical advances have nevertheless been achieved; for instance, upper bounds and lower bounds on the topological entropy of SLSs, *when the sequence of modes is fixed a priori*, are derived in the work of Yang et al.,^{22} and sufficient data rate bounds for feedback stabilization of SLSs, when the switching signal is unobserved by the decoder, are established in the work of Liberzon.^{14}

**Figure 1. State estimation with limited data rate.**

In this paper, we study the questions of topological entropy and minimal data rate for state estimation of SLSs in a *worst-case scenario* approach; that is, we aim to determine sharp upper bounds on the topological entropy and find coders–decoders that can estimate the state of the system, for every switching sequence. The worst-case scenario is a popular approach in the study of switched systems, as it provides formal guarantees that the system satisfies the specifications in every situation. Our contribution is twofold. First, we introduce and study the concept of *worst-case topological entropy* of SLSs, defined as the maximal topological entropy that can be reached by the system among all sequences of modes (aka. switching signals). We present a closed-form expression for the worst-case topological entropy of SLSs. More precisely, we show that it can be expressed as the joint spectral radius (JSR, a ubiquitous measure of stability of SLSs) of a "lifted" SLS representing the action of the original system on elements of volume (obtained by leveraging tools from multilinear algebra). The main asset of this expression is that it can be computed numerically via well-established algorithms for the computation of the joint spectral radius. Consequently, it allows for a systematic analysis of the worst-case topological entropy of SLSs.

The second contribution is to provide a practical coder-decoder that estimates the state of the SLS with exponentially decreasing estimation error, and operates at a data rate arbitrarily close to the worst-case topological entropy of the system. In particular, compared to other bounds on the topological entropy of SLSs available in the literature (for which no practical coders–decoders have been proposed), this demonstrates the practical relevance of the worst-case topological entropy for the problem of state estimation of SLSs under data-rate constraints.

The paper is organized as follows. In Section 2, we introduce the notions of topological entropy and SLSs. In Section 3, we present the closed-from expression for the worst-case topological entropy of SLSs and discuss the computability aspects. In Section 4, we present a practical coder–decoder for the state estimation of SLSs, operating at data rate as close as desired to the worst-case topological entropy of the system. Finally, in Section 5, we demonstrate the applicability of our results on numerical examples.

In our analysis, it is assumed that the switching signal is known by the coder–decoder during the state estimation process. This framework is motivated by the fact that the switching signal is not always known at the time of the coder–decoder's *design*, but is available to the coder–decoder during its *operation.* An example of application is when one has to design the communication infrastructure between the plant (e.g., of a factory) and the observer (placed at a remote location, e.g., the headquarter of the company), and the switching signal is not known at the time of the infrastructure's design or might change with time. For instance, a given sequence of modes might be used by the plant of a factory for a certain amount of time. But after a few days or months, another signal might be needed (e.g. to meet the ever-changing consumer demand). In this case, it is desirable that only the plant and the observer need to be reconfigured, whereas the communication infrastructure remains unchanged. To meet these requirements, the communication channel will need to satisfy constraints driven by the worst-case topological entropy. Other examples of applications involving the control of SLSs with data-rate constraints are discussed in the conclusion.

*Notation.* ℕ is the set of nonnegative integers {0, 1, 2, …}. For vectors, · denotes the Euclidean norm, and for matrices, it denotes the spectral norm. *B*(ξ, *r*) is the Euclidean closed ball in ℝ^{d} centered at ξ ∈ ℝ^{d}, with radius *r* ≥ 0. ⌈·⌉, ⌊·⌋ are the ceil and floor functions respectively. We focus on dynamical systems in discrete time; therefore, if [*T*_{1}, *T*_{2}] (resp. [*T*_{1}, *T*_{2})) refers to an interval of *times* (in particular, *T*_{1}, *T*_{2} ∈ ℕ), then it is understood to contain only the integers from *T*_{1} to *T*_{2} (resp. *T*_{2} – 1) inclusive.

**2.1. Topological entropy**

Consider a discrete-time *switched system*

where σ(*t*) ∈ Σ := {1, …, *N*} and *f _{i}* : ℝ

We introduce here the definition of topological entropy (firstly introduced by Bowen,^{5} and extended to the case of nonautonomous systems by Kolyada and Snoha^{12}). The definition relies on the notion of minimal sets of functions necessary to approximate the trajectories of the system with arbitrary finite accuracy on bounded intervals.

More precisely, let σ be a switching signal for system (1). For ε > 0 and *T* ∈ ℕ, we say that *E* ⊆ *K* is an (ε, *T*)-*spanning set* for (*f*_{σ}, *K*) if for every ξ ∈ *K*, there is η ∈ *E* such that *x*_{σ}(*t*, η) ≤ ε for all *t* ∈ [0, *T*]. This means that for every trajectory *x*_{σ} (·, ξ) of (*f*_{σ}, *K*), there is a trajectory of *f*_{σ} starting in *E* ⊆ *K* that is ε-close to *x*_{σ}(·, ξ) for all *t* ∈ [0, *T*]. See Figure 2 for an illustration. We let *s*_{span} (ε, *T*; *f*_{σ}, *K*) be the smallest cardinality of an (ε, *T*)-spanning set for (*f*_{σ}, *K*).

**Figure 2. The set of trajectories in blue is (ε, T)-spanning for (f_{σ}, K) if every trajectory x_{σ} (·, ξ) (e.g., the trajectory represented in red) is contained in the "ε-tube" around at least one of the trajectories in blue for all t ∈ [0, T].**

*Definition 1.* The *topological entropy* of system (1) with switching signal σ and initial set *K* is defined as

(The limit on the left is well defined because *s*_{span}(ε, *T*; *f*_{σ}, *K*) is nonincreasing in ε.)

**2.2. Switched linear systems**

In this paper, we are interested in the topological entropy of discrete-time *switched linear systems* (SLSs):

where σ is the switching signal as in Equation (1) and *A _{i}* ∈ ℝ

The fundamental matrix solution satisfies that for all ξ ∈ ℝ^{d} and *t*_{1}, *t*_{2} ∈ ℕ, *t*_{1} ≤ *t*_{2}, *x*_{σ}(*t*_{2}, ξ) = Φ_{σ, t1, t2,} *x*_{σ}(*t*_{1},ξ).

The topological entropy of (*A*_{σ}, *K*), denoted by *h*(*A*_{σ}, *K*), is defined in the same way as for switched systems (see Definition 1). However, in the case of SLSs, *h*(*A*_{σ}, *K*) does not depend on a particular choice of the initial set *K* ⊆ ℝ^{d}, as long as it is compact with nonempty interior; see, for example, Yang et al^{23} (Proposition 2). Therefore, we omit the initial set in the notation and denote by *h*(*A*_{σ}) the topological entropy of *A*_{σ}.

We study the worst-case topological entropy of system (3), that is, the maximal topological entropy that can be reached by the system among all its switching signals.

*Definition 2.* The *worst-case topological entropy* of system (3) is defined as

where the supremum is over all switching signals *σ* : ℕ → Σ.

The computational aspects of the worst-case topological entropy are discussed in Section 3. It should also be noted that at this point, there is a priori no link between the topological entropy (which is defined as a topological property of the system) and the minimal data rate for state estimation of the system (which involves the notion of coder–decoder). In Section 4, we show that the worst-case topological entropy *is* in fact equal to the minimal data rate for state estimation of the system under arbitrary switching, and that this data rate limit can be approached as close as desired by *practical* coders–decoders.

The example here illustrates the notions of SLS, spanning sets, topological entropy, and worst-case topological entropy.

*Example 1.* Consider the one-dimensional SLS (3) with Σ = {1, 2}, and *A*_{1} = 1, and *A*_{2} = 2. Let σ be the switching signal alternating modes 1 and 2: σ = (1, 2, 1, 2, …). The trajectories of the system are thus given by *x*_{σ}(*t*, ξ) = 2^{⌊t/2⌋}ξ. We will show that . As mentioned above, for SLSs, as long as topological entropy is concerned, the choice of the initial set is not important; hence, we fix *K* = [0, 1].

For ε > 0 and *T* ∈ ℕ, let *n* = ⌈ε^{-1}2^{T/2-1}⌉ and *E* = {0, 1/*n*, 2/*n*, …, 1}. We show that *E* is (ε, *T*)-spanning for (*A*_{σ}, *K*). To do this, let ξ ∈ *K*, and let η ∈ *E* be such that |ξ – η| = min_{η'∈E} |ξ – η'|. Then, by definition of *E*, it holds that |ξ – η| ≤ 1/(2*n*) ≤ ε2^{-T/2}. This implies that for every *t*∈[0,*T*], |*x*_{σ}(*t*, ξ)-*x*_{σ}(*t*, η)| =2^{⌊t/2⌋}|ξ-η|≤ε. Hence, *E* is (ε, *T*)-spanning for (*A*_{σ}, *K*) and thus

Injecting in Equation (2), we get that is an upper bound on *h*(*A*_{σ}):

Now, we show that is a lower bound on *h*(*A*_{σ}). Let *m* = ⌈ε^{-1}2^{T/2-2}⌉ – 1 (without loss of generality, we may assume *m* > 0, because we take the limit when ε → 0 and *T* → ¥), and define *F* = {0, 1/*m*, 2/*m*, …, 1}. Then, for any distinct ξ, η ∈ *F*, it holds that |ξ−*η*|>ε2^{2−T/2}, so that |*x*_{σ}(*T*,ξ)−*x*_{σ}(*T*,*η*)| = 2^{⌊T/2⌋}|ξ-η|>2ε. This implies that

(see, for example, Liberzon and Mitra^{15}, Lemma 3, for details). Hence, injecting in Equation (2), it follows that .

As for the worst-case topological entropy, it is quite intuitive that a switching signal σ that maximizes the topological entropy is given for instance by using only mode 2: σ = (2, 2, 2, …). In this case, *x*_{σ}(*t*, ξ) = 2^{t}ξ, and we deduce that *h*(*A*_{σ}) = log_{2} 2 = 1. Hence, *h*_{*}(A_{Σ}) = 1.

We start by presenting a closed-form expression for the worst-case topological entropy of SLSs. This will require concepts from stability analysis of SLSs (namely, the joint spectral radius) and from multilinear algebra (namely, the exterior power of a matrix). We also discuss the algorithmic aspects of computing the worst-case topological entropy of SLSs with this expression. Connections with related results in the literature are discussed at the end of this section.

**3.1. Joint spectral radius**

The joint spectral radius (JSR) of a set of matrices measures the asymptotic growth rate of the maximal norm of products of matrices in the set, when the size of the product goes to ¥. More precisely, for a finite set of matrices A_{Σ} := {*A*_{1}, …, *A _{N}*} ⊆ ℝ

This quantity was introduced by Rota and Strang in I960^{18} in order to characterize the stability of SLSs. In particular, the JSR has the following property (see, e.g., Jungers^{9}, Theorem 1.2): Every trajectory *x*_{σ} (·, ξ) (i.e., for any switching signal σ and any ξ ⊆ ℝ^{d}) of the SLS associated to A_{Σ} converges to zero as *t* → ¥, if and only if the JSR of A_{Σ} satisfies *ρ*(A_{Σ}) < 1.

**3.2. Exterior power of matrices**

Exterior algebras are algebraic constructions used to study the notions of areas, volumes, and their higher-dimensional analogues, in general vector spaces. In particular, the notion of exterior power of linear operators is used to represent the action of these operators on such elements of areas, volumes, etc. The exterior power can be defined in a coordinate-free fashion; see, for example, Arnold^{1} (Section 3.2.2). However, in this paper, due to space limitation, we will restrict our attention to the exterior powers of *matrices*, which are themselves matrices and thus allow for a coordinate-based definition.

To do this, let *I* be the set of all multi-indexes of the form (*i*_{1}, …, *i*_{k} ∈ {1, …, *d*}^{k}, with *k* ∈ {0, …, *d*} and *i*_{1} < *i*_{2} < … < *i _{k}*. Hence, the size of

Let *A* ∈ ℝ^{dxd}. The *exterior power* of *A*, denoted by *A*^{∧}, is the 2^{d} X 2^{d} matrix whose entries are indexed by the elements of *I*, and is defined for any *I*, *J* ∈ *I* by

(See also Section 5 for a numerical example.)

The following proposition, whose proof can be found in Arnold^{1} (Section 3.2.3), summarizes the properties of the exterior power of matrices that we will need in this work.

PROPOSITION 1. *Let A*, *B* ∈ ℝ^{dxd}.

*I*^{∧}=*I*, (*AB*)^{∧}=*A*^{∧}*B*^{∧},(*A*^{⊤})^{∧}=(*A*^{∧})^{⊤}.*If A is upper-triangular (resp. lower-triangular, or orthogonal), then so is A*^{∧}*(if the elements of I are ordered with the canonical "lexicographical" ordering).*-
*where**are the singular values of A.* *The eigenvalues of A*∏^{∧}are given by_{i∈I}λ_{i}(*A*),*I*∈*I*,*where*λ_{1}(*A*), …, λ_{d}(*A*)*are the eigenvalues of A.*

**3.3. Main result and consequences**

The main contribution of this section is the following theorem which provides a closed-form expression for the worst-case topological entropy of SLSs.

THEOREM 1. *The worst-case topological entropy of* system (3) *satisfies*

where .

A wide range of methods, of very different natures, have been proposed in the last decades to evaluate the JSR of a set of matrices; see, for example, Jungers^{9} (Section 2.3). Although theoretical discouraging results exist for the computation of the JSR in general, these methods turn out to be extremely powerful in practice and to provide JSR approximation algorithms of high accuracy. Any of these algorithms can be used to approximate the right-hand side term of Equation (7). The computation of the exterior power of a matrix is straight-forward from its definition, and thus can be computed in a systematic way. However, it should be noted that the dimension of increases exponentially with the dimension of the system, and thus so will the complexity of approximating the JSR of (this is the curse of dimensionality). In this regard, we note that a simple and algorithm-independent way to substantially speed up the approximation of —although not sufficient to fight the curse of dimensionality—is to observe that as the matrices are block diagonal (each diagonal block corresponding to a given size of the multi-indexes *I* ∈ *J*), the computation of the JSR of can be decoupled among the different diagonal blocks (see Jungers^{9}, Proposition 1.5).

Furthermore, there are cases for which the computation of the JSR is straightforward; for instance, if A_{σ} is a set of normal (or triangular) matrices. Combining these observations with the properties of the exterior power of matrices (Proposition 1), this gives efficient ways to compute the worst-case topological entropy of such sets of matrices.

COROLLARY 1. *Let* *A*_{Σ}:={*A*_{1}, …, *A*_{N}}⊆ℝ^{d}x*d* *be a set of normal matrices. For each i* ∈ Σ, *let* λ_{1}(*A*_{i}), …, λ_{d}(*A*_{i}) *be the eigenvalues of A _{i}. Then*

*The same holds for sets of upper-triangular (resp. lower-triangular) matrices. Moreover, in this case, the eigenvalues are on the diagonal of the matrices.*

Numerical illustrative examples of the computation of the worst-case topological entropy of SLSs, using Theorem 1 and Corollary 1, are presented in Subsection 5.1.

**3.4. Related works**

The worst-case topological entropy provides an upper bound on the topological entropy of *A*_{σ} for any switching signal σ. The question of estimating *h*(*A*_{σ}) has been addressed, for example, in the works of Yang et al.^{22, 23}. Because the focus is put on a particular matrix sequence *A*_{σ} (disregarding other sequences), the bounds on *h*(*A*_{σ}) obtained in the works of Yang et al.^{22, 23} are in general better than the worst-case topological entropy. However, in some "ill-conditioned" cases (e.g., triangular systems with large differences among the diagonal entries), the bounds available in the works of Yang et al.^{22, 23} can be quite conservative. In these cases, it can be beneficial to use *h*_{*}(A_{Σ}) as an upper bound on *h*(*A*_{σ}).

As already mentioned, the joint spectral radius is a cornerstone of SLS theory, and has attracted a lot of attention in the last decades.^{9, 18, 21} As a measure of the *worst-case* asymptotic growth rate of the trajectories of the system, it is not surprising to encounter this quantity in the characterization of the worst-case topological entropy.

Exterior algebras have also received attention in dynamical systems theory; in particular, in the study of the Lyapunov exponents^{1, 2} and entropy-related properties^{11, 13} of dynamical systems and control systems. For instance, we note the remarkable formula by Kozlovski^{13} for the topological entropy of a discrete-time autonomous dynamical system, described by a *C*^{¥} map *f*: *X* → *X*, on a compact Riemannian manifold:

Theorem 1 shows that the integral can be replaced by a maximum over all switching signals in the case of the worst-case topological entropy of SLSs, and enables practical computation using the stability theory of SLSs.

We investigate the problem of estimating the state of system (3) via a limited data-rate communication network. The observation process is as follows (see also Figure 1 for an illustration). At specific transmission times, 0 = *T*_{0} < *T*_{1} < *T*_{2} < … (*T _{j}* ∈ ℕ), a

More precisely, the coder is a family of functions *C*[·, ·, · |*j*, σ] (parameterized by *j* the index of the epoch and σ the switching signal of the system):

where is an estimate of the current state *x*(*T _{j}*), and δ

where satisfies , and *e*(*T*_{j-1}) is the symbol transmitted at *T*_{j-1} and received by the decoder at *T _{j}*. If

We want to build coders–decoders that estimate the state of the system with exponentially decreasing error.

*Definition 3.* The coder–decoder (Equations (8) and (9)) is said to *observe* the SLS (3) with initial set *K* if there exists *C* > 0 and *g* ∈ (0, 1) such that for every switching signal σ and initial state ξ ∈ *K*, it holds that

*Remark 1.* Equations (8) and (9) assume that the whole switching signal is known by the coder and the decoder during its operation (see also Section 1 for the relevance of this assumption). In fact, as it will be clear from the implementation of the coder and decoder (see paragraphs below), it is sufficient that only the *T*_{j+1} – *T _{j}* modes that are used during the ongoing epoch [

We describe a family of practical coders–decoders that observe system (3) and whose data rate can be as close as desired to the worst-case topological entropy of the system. More precisely, for any compact set *K* ⊆ ℝ^{d} and *R'* > *h*_{*}(A_{Σ}), there is such a coder–decoder that observes system (3) with initial set *K* and whose data rate satisfies *R* ≤ *R'* (see also Theorem 2 at the end of this section). This result relies on the properties of the joint spectral radius and the exterior power of matrices to build coders–decoders with data rate as close as desired to the right-hand side term of Equation (7).

*Coder–decoder's implementation.* For *r* > 0, we let

where ℤ_{even} (resp. ℤ_{odd}) is the set of even (resp. odd) integers. By construction, for every ξ ∈ [-*r*, *r*], there is η ∈ *I*(*r*) such that |ξ – η| ≤ 1, and we have that |*I*(*r*)|≤⌈*r*⌉. If *r* = 0, we let *I*(0) = {0}. Now, for *r*_{1}, …, *r _{d}* ≥ 0, we define

Its cardinality satisfies where ⌈α⌉* =max{⌈α⌉,1}. Finally, for ξ ∈ ℝ^{d}, we let *Q*(ξ) be the closest point to ξ in Grid(*r*_{1}, …, *r _{d}*). Hence,

Let *K* ⊆ ℝ^{d} be a compact set and fix a target data rate *R'* strictly larger than the right-hand side term of Equation (7). We will build a coder–decoder that observes the SLS (3) with initial set *K* and whose data rate satisfies *R* ≤ *R'*. (The reader may find useful to refer to Figure 3, where the different quantities appearing in the definition of the coder–decoder are represented.)

**Figure 3. The different quantities appearing in the definition of the coder–decoder. The gray dots (bottom left) represent Grid( r_{1}, r_{2}), where are the singular values of Φ_{σ}, T_{j}, T_{j+1}. According to Equation (15), Grid(r_{1}, r_{2}) is scaled and rotated by δ_{j+1}d^{−1/2}U, and centered at . The latter is the best available estimate of x(T_{j+1}) before the reception of the symbol e(T_{j}). At reception of e(T_{j}), the new estimate is then given by the center of the square in which the state x(T_{j+1}) lies.**

Let *T*_{0} = 0. Also, let be an estimation of the initial state and δ_{0} > 0 be such that . Fix α > 1. For each *j* ∈ ℕ, let δ_{j}=δ_{0} =α^{j} (this will imply that the bound on the estimation error decreases by a factor 1/α between two transmission times *T _{j}* and

- At time
*T*, the values of_{j}*T*_{j+1}and ε_{j}are computed as follows (these computations are carried out by both the coder and the decoder independently). For*T*∈ ℕ,*T*>*T*, we let , be the singular values of the fundamental matrix solution Φ_{j}_{σ,Tj,T}. We define*T*_{j+1}as the smallest*T*∈ ℕ,*T*>*T*, satisfying_{j}

Finally, *T*_{j+1} being fixed, we let

- The coder is defined as follows. At time
*T*, if is the current estimate of the state (stored in the memory of the coder) and_{j}*x*(*T*) is the current state of the system (the coder has access to the plant), we let . Let_{j}*U SV*^{*}be the Singular Value Decomposition of Φ_{σ,Tj,Tj+1}, where the singular values on the diagonal of*S*are in the same order as in Equation (13). The symbol sent by the coder at time*T*is then defined as_{j}

where *Q*(·) is the quantizer associated to ε_{j} = Grid(*r*_{1}, …, *r _{d}*).

- The decoder is defined as follows. At time
*T*, the decoder receives the symbol_{j}*e*(*T*_{j-1}) and has the last estimate in memory. Then, the decoder computes the estimates for the ongoing epoch [*T*,_{j}*T*_{j+1}) as follows:

where *U SV*^{*} is the Singular Value Decomposition of Φ_{σ,Tj−1,Tj}, as above. If *T _{j}* = 0, simply use the initial estimate given in the parameters of the coder–decoder. Next, define inductively

The implementation of the above coder–decoder is described in Figure 4.

**Figure 4. Coder and decoder implementations.**

Summarizing, we have proved the following result on the equivalence of the worst-case topological entropy and the minimal data rate for state estimation of the system under arbitrary switching signals.

THEOREM 2. *Let K* ⊆ ℝ^{d} *be compact, and consider the SLS* (3). *If R'* < *h*_{*}(A_{Σ}), *then there is no coder–decoder with data rate R* ≤ *R' that observes system* (3). *If R'* > *h*_{*}(A_{Σ}), *then there is a practical coder–decoder with data rate R* ≤ *R' that observes system* (3).

*Remark 2.* It is worth noticing the following effects of the parameters α and *R* on the output of the coder–decoder. By definition of δ_{j}=δ_{0}/α^{j}, α gives the rate of decrease of the worst-case estimation error at the transmission times *T _{j}*. On the other hand, by Equation (12), for a fixed α > 0, the maximal length

**5.1. Worst-case topological entropy**

We use the results of Section 3 to compute the worst-case topological entropy of SLSs with general and triangular matrices.

*Example 2.* Consider the two-dimensional SLS (3) with Σ = {1, 2}, and

We use Theorem 1 to compute the worst-case topological entropy of this system. Therefore, we compute the exterior power of *A*_{1} and *A*_{2}:

We have used the JSR Toolbox^{21} (in MATLAB) to compute the JSR of : This gives . Hence, we conclude that *h*_{*}(A_{Σ}) = 0.3079.

*Example 3.* Consider the 2-dimensional SLS (3) with Σ = {1, 2}, and

Because *A*_{1} and *A*_{2} are upper-triangular matrices, we may apply Corollary 1. We deduce that the worst-case topological entropy of the SLS associated with A_{Σ} is equal to log_{2} 3 = 1.5850. The reader will check that the same result can be obtained by applying directly Theorem 1; indeed the exterior power of *A*_{1} and *A*_{2} are given by

and the JSR of upper-triangular matrices is given by the largest absolute value of its diagonal entries (see Jungers^{9}, Proposition 2.3).

**5.2. State estimation with limited data rate**

We apply the coder–decoder described in Section 4 for the state estimation of the SLS in Example 2. The parameters of the coder–decoder (see Figure 4) are set as follows: We fix the value α = 2.5; the values of and δ_{0} are given in Figure 5-top; and we use different values for the maximal data rate *R*, as explained here.

**Figure 5. Top: Evolution of x(t) and for a sample execution of the coder–decoder with data rate R = 4. Bottom: Evolution of the estimation error for sample executions of the coder–decoder with data rates R = 0.8 (red) and R = 0.5 (blue). The vertical gray lines indicate the transmission times T_{j} (in general, the error decreases at these times because the decoder receives a new symbol).**

Firstly, to make a comprehensive visual illustration, we use a data rate of *R* = 4, which is much larger than the worst-case topological entropy (see Example 2). This ensures that each epoch lasts one unit of time, that is, *T*_{j+1} – *T _{j}* = 1 (see also Remark 2). A sample execution of the coder–decoder is presented in Figure 5—top. In this picture, the states

Secondly, we simulate the execution of the coder–decoder with data rates that are closer to the worst-case topological entropy of the system, namely *R* = 0.8 and *R* = 0.5. For these values of *R*, the duration of the epochs is longer (between 5 and 12, in our simulation). The evolution of the estimation error is represented in Figure 5-bottom. As expected, we observe that the estimation error decreases more rapidly when the data rate is higher.

This paper introduced the concept of worst-case topological entropy for switched linear systems. It was shown that this quantity is relevant for the problem of state estimation of these systems with limited data rate. More precisely, we constructed a practical coder–decoder, operating at a data rate as close as desired to the worst-case topological entropy, which estimates the state of the system for any switching signal and with exponentially decreasing estimation error. We also discussed the computational aspects of the worst-case topological entropy. In particular, we provided a closed-form expression describing the worst-case topological entropy as the joint spectral radius of some set of matrices obtained from the original system by taking the exterior power of the individual modes. Among other consequences, the computation of the worst-case topological entropy can thereby benefit from the numerous algorithmic tools developed in the last decades for the computation of the joint spectral radius of switched linear systems.

In our framework, it is assumed that the switching signal is known by the coder–decoder. However, it was noted in Remark 1 that only a few future values of the switching signal actually need to be known by the coder-decoder. Based on this observation, we plan to show that the concept of worst-case topological entropy is also relevant for the *control* of switched linear systems with limited data rate. We think for instance to control schemes involving the switching signal as control input (see, e.g., Jungers and Mason^{10} and Sun and Ge^{20}—Chapter 4).

We also plan to consider variants of this framework, involving for instance relaxations of the assumption that the switching signal is known by the coder-decoder (non-deterministic systems), and considering the stabilization of switched linear systems under data-rate constraints. Related questions have been addressed, for example, in the works of Savkin^{19} (topological entropy for nondeterministic systems); Colonius^{6}, Hagihara and Nair^{7}, and Savkin^{19} (control of autonomous systems with limited data rate), and Liberzon^{14} (stabilization of nondeterministic switched linear systems with limited data rate). Another potential direction for further research is to combine our results for the computation of the worst-case topological entropy with other techniques for the analysis of switched linear systems, in order to fight the curse of dimensionality. We think for instance to *p*-dominance analysis techniques^{3,4} that allow one to decide whether the system has a low-dimensional dominant behavior.

The authors would like to thank Daniel Liberzon (University of Illinois in Urbana-Champaign) for insightful discussions on the results presented in the paper.

1. Arnold, L. Random dynamical systems. In *Springer Monographs in Mathematics.* Springer-Verlag, Berlin, 1998.

2. Barreira, L. *Lyapunov exponents.* Springer Science+Business Media, Basel, 2017.

3. Berger, G.O., Forni, F., Jungers, R.M. Path-complete *p*-dominant switching linear systems. In *2018 IEEE 57th IEEE Conference on Decision and Control (CDC)* (2018), IEEE, Miami, 6446–6451.

4. Berger, G.O., Jungers, R.M. A converse Lyapunov theorem for *p*-dominant switched linear systems. In *2019 18th European Control Conference (ECC)* (2019), IEEE, Naples, 1263–1268.

5. Bowen, R. Entropy for group endomorphisms and homogeneous spaces. *Trans. Am. Math. Soc. 153* (1971), 401–414.

6. Colonius, F. Minimal bit rates and entropy for exponential stabilization. *SIAM J. Control Optim. 50*, 5 (2012), 2988–3010.

7. Hagihara, R., Nair, G.N. Two extensions of topological feedback entropy. *Math. Control Signals Syst. 25*, 4 (2013), 473–490.

8. Hespanha, J.P., Naghshtabrizi, P., Xu, Y. A survey of recent results in networked control systems. *Proc. IEEE 95*, 1 (2007), 138–162.

9. Jungers, R.M. The joint spectral radius: Theory and applications. In *Lecture Notes in Control and Information Sciences.* Volume 385. Springer-Verlag, Berlin Heidelberg, 2009.

10. Jungers, R.M., Mason, P. On feedback stabilization of linear switched systems via switching signal control. *SIAM J. Control Optim. 55*, 2 (2017), 1179–1198.

11. Kawan, C. Invariance entropy for deterministic control systems. In *Lecture Notes in Mathematics.* Volume 2089. Springer Science+Business Media, Cham, 2013.

12. Kolyada, S., Snoha, L. Topological entropy of nonautonomous dynamical systems. *Random Comput. Dyn. 4*, 2 (1996), 205–233.

13. Kozlovski, O.S. An integral formula for topological entropy of *C*^{¥} maps. *Ergod. Theory Dyn. Syst. 18*, 2 (1998), 405–424.

14. Liberzon, D. Finite data-rate feedback stabilization of switched and hybrid linear systems. *Automatica 50*, 2 (2014), 409–420.

15. Liberzon, D., Mitra, S. Entropy and minimal bit rates for state estimation and model detection. *IEEE Trans. Autom. Control 63*, 10 (2018), 3330–3344.

16. Matveev, A.S., Pogromsky, A. Observation of nonlinear systems via finite capacity channels: Constructive data rate limits. *Automatica 70*, (2016), 217–229.

17. Matveev, A.S., Savkin, A.V. Estimation and control over communication networks. In *Control Engineering.* Springer Science+Business Media, Basel, 2009.

18. Rota, G.-C., Strang, W.G. A note on the joint spectral radius. *Proc. Netherlands Acad. 22*, (1960), 379–381.

19. Savkin, A.V. Analysis and synthesis of networked control systems: Topological entropy, observability, robustness and optimal control. *Automatica 42*, 1 (2006), 51–62.

20. Sun, Z., Ge, S.S. Stability theory of switched dynamical systems. In *Communications and Control Engineering.* Springer-Verlag, London, 2011.

21. Vankeerberghen, G., Hendrickx, J., Jungers, R.M. JSR: A toolbox to compute the joint spectral radius. In *Proceedings of the 17 ^{th} International Conference on Hybrid Systems: Computation and Control* (2014), ACM, Berlin, 151–156.

22. Yang, G., Hespanha, J.P., Liberzon, D. On topological entropy and stability of switched linear systems. In *Proceedings of the 22 ^{nd} International Conference on Hybrid Systems: Computation and Control* (2019), ACM, Montreal, 119–127.

23. Yang, G., Schmidt, A.J., Liberzon, D. On topological entropy of switched linear systems with diagonal, triangular, and general matrices. In *2018 IEEE 57 ^{th} IEEE Conference on Decision and Control (CDC)* (2018), IEEE, Miami, 5682–5687.

a. In our framework (worst-case scenario analysis), the switching signal is an external input on which the user has no control, and the objective is to deduce properties of the system that will be valid for all switching signals.

The original version of this paper was published in *Proceedings of the 23 ^{rd} International Conference on Hybrid Systems: Computation and Control*, April 2020, ACM.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2022 ACM, Inc.

No entries found