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.

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.⁸ and Matveev and Savkin¹⁷.

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¹⁶ and Pogromsky and Savkin.¹⁹ 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.¹⁹ 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.¹⁶

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.⁹ 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.,²² 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.¹⁴

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

Back to Top

2. Preliminaries

 2.1. Topological entropy

Consider a discrete-time switched system

where σ(t) ∈ Σ := {1, …, N} and f_i : ℝ^d → ℝ^d for all i ∈ Σ. The function σ : ℕ → Σ is called the switching signal^a of the system and specifies which mode, that is, which transition map f_i, 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,⁵ and extended to the case of nonautonomous systems by Kolyada and Snoha¹²). 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 ∈ ℝ^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_Σ := {A₁, …, A_N}. 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 t₁ to a time t₂ can be represented by a matrix: for t₁, t₂ ∈ ℕ, t₁ ≤ t₂, we denote the fundamental matrix solution of system (3) from t₁ to t₂ with switching signal σ by

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

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²³ (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, and A₂ = 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 = ⌈ε^-12^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/(2n) ≤ ε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 = ⌈ε^-12^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¹⁵, 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 = 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_Σ := {A₁, …, A_N} ⊆ ℝ^dxd, the joint spectral radius of A_Σ is defined as

This quantity was introduced by Rota and Strang in I960¹⁸ in order to characterize the stability of SLSs. In particular, the JSR has the following property (see, e.g., Jungers⁹, 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¹ (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₁, …, i_k ∈ {1, …, d}^k, with k ∈ {0, …, d} and i₁ < i₂ < … < i_k. Hence, the size of I is 2^d.

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¹ (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)^∧ = A^∧B^∧,(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. where are the singular values of A.
4. The eigenvalues of A^∧ are given by ∏_i∈Iλ_i(A),I∈I, where λ₁(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⁹ (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⁹, 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₁, …, A_N}⊆ℝ^dxd be a set of normal matrices. For each i ∈ Σ, let λ₁(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¹³ 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.

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

where is an estimate of the current state x(T_j), and δ_j satisfies . The output is e(T_j)∈ε_j⊆ℝ^d, where ε_j is a finite set depending on j and σ. The symbol e(T_j) will be transmitted to the decoder at most at T_j+1. The decoder is a family of functions D[·,·,·|j,σ (also parameterized by 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 j = 0, take . The decoder outputs estimates of the state for the ongoing epoch [T_j, T_j+1). The transmission times T_j, 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

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 [T_j, T_j+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 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₁, …, 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₁, …, r_d). Hence, Q(·) is a -point quantizer and satisfies

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₁, r₂), where are the singular values of Φ_σ, T_j, T_j+1. According to Equation (15), Grid(r₁, r₂) is scaled and rotated by δ_j+1d^−1/2U, 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. Also, let be an estimation of the initial state and δ₀ > 0 be such that . Fix α > 1. For each j ∈ ℕ, let δ_j=δ₀ =α^j (this will imply that the bound on the estimation error decreases by a factor 1/α between two transmission times T_j and T_j+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 T_j+1 – T_j).

• At time T_j, the values of 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_j, we let , be the singular values of the fundamental matrix solution Φ_σ,Tj,T. We define T_j+1 as the smallest T ∈ ℕ, T > T_j, satisfying

Finally, T_j+1 being fixed, we let

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

where Q(·) is the quantizer associated to ε_j = Grid(r₁, …, r_d).

• The decoder is defined as follows. At time T_j, the decoder receives the symbol 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=δ₀/α^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 T_j+1 – T_j of an epoch will depend on the maximal allowed data rate R of the coder–decoder; the smaller R, the longer T_j+1 – T_j. 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

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

We have used the JSR Toolbox²¹ (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₁ and A₂ 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₂ 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₁ and A₂ are given by

and the JSR of upper-triangular matrices is given by the largest absolute value of its diagonal entries (see Jungers⁹, 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 δ₀ 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 x(t) of the true system are represented in blue. The estimates 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 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 Mason¹⁰ and Sun and Ge²⁰—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¹⁹ (topological entropy for nondeterministic systems); Colonius⁶, Hagihara and Nair⁷, and Savkin¹⁹ (control of autonomous systems with limited data rate), and Liberzon¹⁴ (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.

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.