Research and Advances
Artificial Intelligence and Machine Learning Research highlights

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

Posted
  1. Abstract
  2. 1. Introduction
  3. 2. Preliminaries
  4. 3. Closed-Form Expression For The Worst-Case Topological Entropy Of Switched Linear Systems
  5. 4. Practical Coder–Decoder
  6. 5. Numerical Experiments
  7. 6. Conclusion
  8. Acknowledgments
  9. References
  10. Authors
  11. Footnotes
Read the related Technical Perspective
organ stops with hand

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.

Back to Top

1. Introduction

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 Savkin17.

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, Matveev16 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

f1.jpg
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 [T1, T2] (resp. [T1, T2)) refers to an interval of times (in particular, T1, T2 ∈ ℕ), then it is understood to contain only the integers from T1 to T2 (resp. T2 – 1) inclusive.

Back to Top

2. Preliminaries

*  2.1. Topological entropy

Consider a discrete-time switched system

eq01.gif

where σ(t) ∈ Σ := {1, …, N} and fi : ℝd → ℝd for all i ∈ Σ. The function σ : ℕ → Σ is called the switching signala of the system and specifies which mode, that is, which transition map fi, is used by the switched system at each time. We denote by xσ(t, ξ) the solution, at time t, of Equation (1) with switching signal σ and initial state ξ ∈ ℝd. Let K ⊆ ℝd be a compact set with nonempty interior, called the initial set. We will write (fσ, K) to denote system (1) with switching signal σ and initial set K; that is, xσ(·, ξ) is a trajectory of (fσ, K) if and only if ξ ∈ K.

We introduce here the definition of topological entropy (firstly introduced by Bowen,5 and extended to the case of nonautonomous systems by Kolyada and Snoha12). 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 EK 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 EK that is ε-close to xσ(·, ξ) for all t ∈ [0, T]. See Figure 2 for an illustration. We let sspan (ε, T; fσ, K) be the smallest cardinality of an (ε, T)-spanning set for (fσ, K).

f2.jpg
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

eq02.gif

(The limit on the left is well defined because sspan(ε, 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):

eq03.gif

where σ is the switching signal as in Equation (1) and Ai ∈ ℝdxd for all i ∈ Σ. SLSs are thus particular instances of system (1) where each mode is linear. Following the notation of the previous subsection, we let xσ (t, ξ) be the solution, at time t, of system (3) with switching signal σ and initial state ξ ∈ ℝd. In formulas, it is convenient to identify the SLS (3) by its set of modes AΣ := {A1, …, AN}. We will also use (Aσ, K) to denote system (3) with switching signal σ and initial set K. The system being linear, the transition of the state from a time t1 to a time t2 can be represented by a matrix: for t1, t2 ∈ ℕ, t1t2, we denote the fundamental matrix solution of system (3) from t1 to t2 with switching signal σ by

eq04.gif

The fundamental matrix solution satisfies that for all ξ ∈ ℝd and t1, t2 ∈ ℕ, t1t2, xσ(t2, ξ) = Φσ, t1, t2, xσ(t1,ξ).

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 al23 (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

eq05.gif

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 A1 = 1, and A2 = 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, ξ) = 2t/2⌋ξ. We will show that cacm6502_m.gif . 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 = ⌈ε-12T/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/(2n) ≤ ε2T/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

ueq01.gif

Injecting in Equation (2), we get that cacm6502_ap.gif is an upper bound on h(Aσ):

ueq02.gif

Now, we show that cacm6502_ap.gif is a lower bound on h(Aσ). Let m = ⌈ε-12T/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 |ξ−η|>ε22−T/2, so that |xσ(T,ξ)−xσ(T,η)| = 2T/2⌋|ξ-η|>2ε. This implies that

ueq03.gif

(see, for example, Liberzon and Mitra15, Lemma 3, for details). Hence, injecting in Equation (2), it follows that cacm6502_n.gif .

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, ξ) = 2tξ, and we deduce that h(Aσ) = log2 2 = 1. Hence, h*(AΣ) = 1.

Back to Top

3. Closed-Form Expression For The Worst-Case Topological Entropy Of Switched Linear Systems

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Σ := {A1, …, AN} ⊆ ℝdxd, the joint spectral radius of AΣ is defined as

eq06.gif

This quantity was introduced by Rota and Strang in I96018 in order to characterize the stability of SLSs. In particular, the JSR has the following property (see, e.g., Jungers9, 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, Arnold1 (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 (i1, …, ik ∈ {1, …, d}k, with k ∈ {0, …, d} and i1 < i2 < … < ik. Hence, the size of I is 2d.

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

ueq04.gif

(See also Section 5 for a numerical example.)

The following proposition, whose proof can be found in Arnold1 (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.

  1. I=I, (AB) = AB,(A)=(A).
  2. 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).
  3. cacm6502_o.gif where cacm6502_p.gif are the singular values of A.
  4. The eigenvalues of A are given byiIλi(A),II, 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

eq07.gif

where cacm6502_q.gif .

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, Jungers9 (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 cacm6502_r.gif can be computed in a systematic way. However, it should be noted that the dimension of cacm6502_r.gif increases exponentially with the dimension of the system, and thus so will the complexity of approximating the JSR of cacm6502_r.gif (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 cacm6502_s.gif —although not sufficient to fight the curse of dimensionality—is to observe that as the matrices cacm6502_t.gif are block diagonal (each diagonal block corresponding to a given size of the multi-indexes IJ), the computation of the JSR of cacm6502_r.gif can be decoupled among the different diagonal blocks (see Jungers9, 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Σ:={A1, …, AN}⊆ℝdxd be a set of normal matrices. For each i ∈ Σ, let λ1(Ai), …, λd(Ai) be the eigenvalues of Ai. Then

ueq05.gif

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 exponents1, 2 and entropy-related properties11, 13 of dynamical systems and control systems. For instance, we note the remarkable formula by Kozlovski13 for the topological entropy of a discrete-time autonomous dynamical system, described by a C¥ map f: XX, on a compact Riemannian manifold:

ueq06.gif

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.

Back to Top

4. Practical Coder–Decoder

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 = T0 < T1 < T2 < … (Tj ∈ ℕ), a coder measures the state x(Tj) of the system, and sends a symbol e(Tj) to a decoder via a noiseless digital channel which can carry one discrete-valued symbol per time epoch [Tj, Tj+1], selected from a coding alphabet εj. Neglecting propagation delay and transmission errors, each symbol takes at most one epoch duration Tj+1Tj to be completely transmitted. Hence, at time Tj+1, the decoder has e(T0), …, e(Tj) available and generates estimates cacm6502_u.gif of the state of the system for the ongoing epoch [Tj+1, Tj+2).

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):

eq08.gif

where cacm6502_v.gif is an estimate of the current state x(Tj), and δj satisfies cacm6502_w.gif . The output is e(Tj)∈εj⊆ℝd, where εj is a finite set depending on j and σ. The symbol e(Tj) will be transmitted to the decoder at most at Tj+1. The decoder is a family of functions D[·,·,·|j,σ (also parameterized by j and σ):

eq09.gif

where cacm6502_x.gif satisfies cacm6502_y.gif , and e(Tj-1) is the symbol transmitted at Tj-1 and received by the decoder at Tj. If j = 0, take cacm6502_z.gif . The decoder outputs estimates of the state for the ongoing epoch [Tj, Tj+1). The transmission times Tj, the error bounds δj, and the coding alphabets εj depend only on the switching signal σ and thus they can be computed by both the coder and the decoder independently. The data rate R (in bits per unit of time) of the coder-decoder is defined as

eq10.gif

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

eq11.gif

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 Tj+1Tj modes that are used during the ongoing epoch [Tj, Tj+1] are known by the coder and the decoder.

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 RR’ (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

ueq07.gif

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 r1, …, rd ≥ 0, we define

ueq08.gif

Its cardinality satisfies cacm6502_aa.gif where ⌈α⌉* =max{⌈α⌉,1}. Finally, for ξ ∈ ℝd, we let Q(ξ) be the closest point to ξ in Grid(r1, …, rd). Hence, Q(·) is a cacm6502_ab.gif -point quantizer and satisfies

ueq09.gif

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 RR’. (The reader may find useful to refer to Figure 3, where the different quantities appearing in the definition of the coder–decoder are represented.)

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

Let T0 = 0. Also, let cacm6502_af.gif be an estimation of the initial state and δ0 > 0 be such that cacm6502_ag.gif . Fix α > 1. For each j ∈ ℕ, let δj0j (this will imply that the bound on the estimation error cacm6502_ah.gif decreases by a factor 1/α between two transmission times Tj and Tj+1, and thus the rate g of decay of the estimation error (see Definition 3) is given by α-1/τ where τ is an upper bound on Tj+1Tj).

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

eq12.gif

Finally, Tj+1 being fixed, we let

eq13.gif

  • The coder is defined as follows. At time Tj, if cacm6502_aj.gif is the current estimate of the state (stored in the memory of the coder) and x(Tj) is the current state of the system (the coder has access to the plant), we let cacm6502_ak.gif . Let 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 Tj is then defined as

eq14.gif

where Q(·) is the quantizer associated to εj = Grid(r1, …, rd).

  • The decoder is defined as follows. At time Tj, the decoder receives the symbol e(Tj-1) and has the last estimate cacm6502_al.gif in memory. Then, the decoder computes the estimates cacm6502_aq.gif for the ongoing epoch [Tj, Tj+1) as follows:

eq15.gif

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

eq16.gif

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

f4.jpg
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 RR’ that observes system (3). If R’ > h*(AΣ), then there is a practical coder–decoder with data rate RR’ 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 δj0j, α gives the rate of decrease of the worst-case estimation error at the transmission times Tj. On the other hand, by Equation (12), for a fixed α > 0, the maximal length Tj+1Tj of an epoch will depend on the maximal allowed data rate R of the coder–decoder; the smaller R, the longer Tj+1Tj. Furthermore, if R is smaller than the worst-case topological entropy—and only in this case—the maximal epoch length may be infinite.

Back to Top

5. Numerical Experiments

*  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

ueq10.gif

We use Theorem 1 to compute the worst-case topological entropy of this system. Therefore, we compute the exterior power of A1 and A2:

ueq11.gif

We have used the JSR Toolbox21 (in MATLAB) to compute the JSR of cacm6502_r.gif : This gives cacm6502_s.gif . Hence, we conclude that h*(AΣ) = 0.3079.

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

ueq12.gif

Because A1 and A2 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 log2 3 = 1.5850. The reader will check that the same result can be obtained by applying directly Theorem 1; indeed the exterior power of A1 and A2 are given by

ueq13.gif

and the JSR of upper-triangular matrices is given by the largest absolute value of its diagonal entries (see Jungers9, 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 cacm6502_af.gif and δ0 are given in Figure 5-top; and we use different values for the maximal data rate R, as explained here.

f5.jpg
Figure 5. Top: Evolution of x(t) and cacm6502_am.gif for a sample execution of the coder–decoder with data rate R = 4. Bottom: Evolution of the estimation error cacm6502_an.gif 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 Tj (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, Tj+1Tj = 1 (see also Remark 2). A sample execution of the coder–decoder is presented in Figure 5—top. In this picture, the states x(t) of the true system are represented in blue. The estimates cacm6502_u.gif computed by the coder–decoder are represented in red.

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 cacm6502_ao.gif is represented in Figure 5-bottom. As expected, we observe that the estimation error decreases more rapidly when the data rate is higher.

Back to Top

6. Conclusion

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 Mason10 and Sun and Ge20—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 Savkin19 (topological entropy for nondeterministic systems); Colonius6, Hagihara and Nair7, and Savkin19 (control of autonomous systems with limited data rate), and Liberzon14 (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 techniques3,4 that allow one to decide whether the system has a low-dimensional dominant behavior.

Back to Top

Acknowledgments

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 17th 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 22nd 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 57th 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 23rd International Conference on Hybrid Systems: Computation and Control, April 2020, ACM.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More