Spanning orbit-based definition

We define the nth order ball of point x ∈ X, denoted by Bⁿ(x, ϵ), as the ball around x with radius ϵ with respect to metric dⁿ defined as

$\begin{array}{l}{d}^n(x,y)=max\{d(T^{i}x,T^{i}y),i=0,\dots ,n-1\}.\hfill \end{array}$

Fig. 5.2 shows that a track beginning from x₂ is within Bⁿ(x₁, ϵ).

We say a set F is (n, ϵ)-spanning if it intersects every (n, ϵ)-ball (i.e., intersecting Bⁿ(x, ϵ) for every x). Then we define

$\begin{array}{l}r(n,ϵ)=min\{\#F:F\text{is}(n,ϵ)\text{-spanning}\}.\hfill \end{array}$

Then we define the spanning orbit-based topological entropy as follows, where the subscript s denotes “spanning”:

Separated orbit-based definition

We say a subset F of X is (n, ϵ)-separated if dⁿ(x_i, x_j) > ϵ for all x_i, x_j ∈ F and x_i≠x_j. Since X is compact, all (n, ϵ)-separated sets have finite elements, which is illustrated in Fig. 5.3. The maximal cardinality of all (n, ϵ)-separated sets is denoted by

$\begin{array}{l}s(n,ϵ)=max\{|F|:F\text{is}(n,ϵ)\text{-separated}\}.\hfill \end{array}$

We denote by s(n, ϵ) the maximum cardinality of a product (n, ϵ)-separated set, namely

$\begin{array}{l}s(n,ϵ)=min\{\#G(F):F\in {\Omega }_{n,ϵ}\}.\hfill \end{array}$

Then we define the metric-based product topological entropy as follows:

Cover-based definition

The cover-based definition of topological entropy does not require the definition of a metric; hence it is valid even in spaces without a metric structure. We define a cover of X as a family of open sets that cover X. Since X is compact, we can always find a finite subset of open sets of $\mathcal{U}$ to cover X. We say that a cover $\mathcal{V}$ is a subcover of cover $\mathcal{U}$ if $\mathcal{V}\subset \mathcal{U}$. The minimum cardinality of a subcover of cover $\mathcal{U}$ is denoted by $N(\mathcal{U})$.

We define the join of two covers $\mathcal{U}$ and $\mathcal{V}$ as

$\begin{array}{l}\mathcal{U}\vee \mathcal{V}=\{U\cap V:U\in \mathcal{U},V\in \mathcal{V}\}.\hfill \end{array}$

We further define

$\begin{array}{l}{\mathcal{U}}^n={\vee }_{n=0,\dots ,n-1}{T}^{-n}(\mathcal{U}).\hfill \end{array}$

Based on the above definitions, we can now define the cover-based topological entropy:

Equivalence

The above three definitions of topological entropy look quite different, focusing on different aspects of the dynamical system. Interestingly, they are equivalent in metric spaces:

The proof is highly nontrivial. The details can be found in chapter 6 of Ref. [12]. Due to their equivalence, we use only the notation h_s(T) in the subsequent discussion.

System model

The model of the CPS is given in Fig. 5.4. We consider the following system dynamics:

$\begin{array}{l}\mathbf{x}(t+1)=f(\mathbf{x},\mathbf{u}(t)),\hfill \\ \hfill \end{array}$

which is a simpler version of Eq. (5.1). The initial value x(0) is unknown. An encoder observes the system state and sends out a message h(jT) every T time slots, where j is the index of the message. The total number of messages is denoted by L. Hence the average transmission rate is given by $\frac{{log}_{2}L}{T}$. If the capacity of the communication channel is R, then we have

$\begin{array}{l}\frac{{log}_{2}L}{T}\le R.\hfill \\ \hfill \end{array}$

The transmitted message is essentially a function of the observation history, i.e.,

$\begin{array}{l}h(jT)=F_j(\mathbf{x}(1:jT)),\hfill \\ \hfill \end{array}$

where the subscript j in F_j means that the encoding mechanism can be time varying.

Upon receiving a message from the encoder, the controller decodes it and carries out the following possible actions:

• System state estimation: The controller estimates the system states between times (j − 1)T + 1 and jT (i.e., the system state in the previous period of the message), namely $\widehat{\mathbf{x}}((j-1)T+1),\dots ,\widehat{\mathbf{x}}(jT)$. The outcome of the estimator is given by

$\begin{array}{l}\widehat{\mathbf{x}}((j-1)T+1:jT)=G_j(h(T:jT)),\hfill \end{array}$

where the subscript j in G_j means that the estimation algorithm can be time varying.

• System state control: The controller computes the control action in the next T time slots (i.e., before receiving the next message), namely u(jT + 1), …, u((j + 1)T). The outcome of the controller is given by

$\begin{array}{l}\mathbf{u}((j-1)T+1:jT)=U_j(h(T:jT)),\hfill \\ \hfill \end{array}$

where the subscript j in G_j means that the control algorithm can be time varying.

For simplicity, we assume that there is no transmission error during the communications. This is reasonable if powerful error correction codes are applied and a single sparse error causes only negligible impact on the dynamics. Hence the limit of communications is focused only on the capacity, not the reliability.

Then the question is: How much communication is needed for a precise system state estimation or a stable system dynamics?

Communication requirements for estimation

We first focus on the system state estimation. We define the observability of the system as follows:

For the observability of the system, we have the following conclusion (Theorem 2.3.6 in Ref. [11]):

Here we provide an intuitive explanation of the encoding and decoding mechanism to achieve observability, as well as the reason for the unobservability when the transmission rate is too low. A rigorous proof can be found in chapter 2 of Ref. [11].

• R < h_s(T): We assume that a coder-decoder pair can make the system observable. Then for n time slots and any ϵ > 0, we can find 2^⌈nR⌉ spanning points in time [0, n − 1] such that they form an (n, ϵ)-separated orbits, due to the definition of observability. Then the topological entropy of the system will be no larger than ${lim}_{n\to \infty }\frac{1}{n}{log}_2{2}^{nR}<h_s(T)$, which contradicts the assumption that the topological entropy is h_s(T).

• R > h_s(T): Due to the definition of h_s(T), for any n > 1 and ϵ > 0, we can always find an (n, ϵ)-spanning set with cardinality no larger than 2^nR in the state space. Then we can simply transmit the index of the corresponding point in the spanning set (thus taking a transmission rate no larger than R) and achieve an error less than ϵ. This encoding procedure is illustrated in Fig. 5.5.

Communication requirements for linear system control

The communication requirements for control are more complicated. We focus on only the special case of linear systems without noise and with direct observation of the system state:

$\begin{array}{l}\left\{\begin{array}{c}\mathbf{x}(t+1)=\mathbf{A}\mathbf{x}(t)+\mathbf{B}\mathbf{u}(t),\hfill \\ \mathbf{y}(t)=\mathbf{x}(t).\hfill \end{array}\right.\hfill \end{array}$

The control action is for the purpose of system stabilization, which is defined as follows:

Intuitively, that the system is stabilizable means that we can arbitrarily control the system state given sufficient time. The following two assumptions are subsequently made:

• The initial state x(0) lies in a compact set ${\mathcal{X}}_1$ which has the origin as an interior point; i.e., there exists a δ > 0 such that $\parallel \mathbf{x}{\parallel }_{\infty }<\delta$ implies $\mathbf{x}\in {\mathcal{X}}_1$.

• The system (A, B) is stabilizable given a perfect system state feedback.

Then the following theorem provides conditions for the stabilizabilities of the linear system:

The first conclusion (R < h_s(A)) in the above theorem can be obtained from contradiction, as illustrated in Fig. 5.6. A detailed proof can be found in Section 2.7 of Ref. [11]. Here we provide a sketch of the proof. We assume that the linear system is still stabilizable when R < h_s(A). Since R < h_s(A), we can find a constant ϵ > 0 such that

$\begin{array}{l}{limsup}_{k\to \infty }\frac{1}{k}{log}_{2}s(k,ϵ)>R,\hfill \end{array}$

where s(k, ϵ) is the metric-based topological entropy. This implies that there is a (jT, ϵ)-separated set S of cardinality N such that

$\begin{array}{l}\frac{{log}_{2}N}{jT}>R,\hfill \end{array}$

and for any two different points x₁ and x₂ in S satisfying

$\begin{array}{l}\parallel {\mathbf{x}}_1(t)-{\mathbf{x}}_2(t){\parallel }_{\infty }\ge ϵ.\hfill \end{array}$

On the other hand, we set ${ϵ}_0=\frac{1}{2}ϵ$. Since the system is stabilizable, we can always find control actions for each element x in S such that $\parallel \mathbf{x}(t){\parallel }_{\infty }\le {ϵ}_0$. There are no more than 2^jRT possible control action sequences. Hence we can always find a sequence of controls, u*(0), …, u*(jT), in these sequences such that we can find x₁ and x₂ that are both well controlled by the sequence {u*}; i.e., both x₁′(t) =x₁(t) +x_u(t) and x₂′(t) =x₂(t) +x_u(t) satisfy Eq. (5.23) with respect to ϵ₀. Then it is easy to verify

$\begin{array}{l}\parallel {\mathbf{x}}_1(t)-{\mathbf{x}}_2(t)\parallel \ge ϵ.\hfill \end{array}$

This contradicts the assumption of the (jT, ϵ)-separated set S. Hence the cardinality of the message set cannot be less than $2^{h_s(\mathbf{A})}$.

The second conclusion (R > h_s(A)) in the theorem can be derived from the conclusions in the subsequent treatment of the optimal control of linear systems.

Communication requirements for optimal control

In the previous discussion, the feedback is to stabilize the system, regardless of the corresponding cost (e.g., a very large control action u). In the optimal control of linear systems, the costs of both system state magnitude and control action power are considered; i.e., the system cost with initial state x(0) is given by

$\begin{array}{l}J(\mathbf{x}(0))=\sum _{t=1}^{\infty }{\mathbf{x}}^T(t)\mathbf{Q}\mathbf{x}(t)+{\mathbf{u}}^T(t)\mathbf{R}\mathbf{u}(t),\hfill \end{array}$

where both Q and R are positive definite matrices.

When the feedback is perfect (i.e., there is no constraint on the communication rate), it is well known that the optimal feedback control is given in [72]

$\begin{array}{l}\mathbf{u}(t)=-\mathbf{K}\mathbf{x}(t),\hfill \end{array}$

where

$\begin{array}{l}\mathbf{K}={(\mathbf{R}+{\mathbf{B}}^T\mathbf{P}\mathbf{B})}^{-1}{\mathbf{B}}^T\mathbf{P}\mathbf{A},\hfill \end{array}$

and the matrix P satisfies the following equation:

$\begin{array}{l}\mathbf{A}(\mathbf{P}-\mathbf{P}\mathbf{B}{(\mathbf{R}+{\mathbf{B}}^T\mathbf{P}\mathbf{B})}^{-1}{\mathbf{B}}^T\mathbf{P})\mathbf{A}+\mathbf{Q}-\mathbf{P}=0.\hfill \end{array}$

The optimal cost function is given by

$\begin{array}{l}{J}_{\mathrm{opt}}(\mathbf{x}(0))={\mathbf{x}}^T(0)\mathbf{P}\mathbf{x}(0).\hfill \end{array}$

Now we consider the constraint on the communication rate; i.e., R is bounded. We define the solvability of the optimal control as follows [11]:

The conclusion on the communication requirements for the solvable optimal control is given in the following theorem:

The conclusion for R < h_s(A) is a straightforward conclusion of Theorem 3, since the system is not even stabilizable when R < h_s(A). The proof for the case of R > h_s(A) is much more involved (note that the corresponding conclusion in Theorem 3 is merely a special case). A rigorous proof can be found in Section 2.7 of Ref. [11]. Here we provide a sketch of the proof. First we choose a reasonable period T. Then we consider the system:

$\begin{array}{l}{\mathbf{x}}_a(t+1)=\mathbf{A}{\mathbf{x}}_a(t).\hfill \end{array}$

We can find a set Ω of initial point $\{{\mathbf{x}}_n^{*}(0)\}$ with cardinality 2^(T+1)α, where h_s(A) < α < R, with the following property: For any initial state x(0), we can always find a point ${\mathbf{x}}_n^{*}(0)$ in Ω such that the trace in Eq. (5.34) triggered by ${\mathbf{x}}_n^{*}(0)$ is very close to that triggered by x(0) within the time duration [0, T]. For each point $\{{\mathbf{x}}_n^{*}(0)\}$ in Ω, we can compute the corresponding control actions within time period [0, T], namely u*(0), …, u*(T − 1).

Then we define the following encoder and controller pair for time interval [0, T − 1]:

• Encoder: Given the initial state x(0), we choose the corresponding point in Ω, namely $\{{\mathbf{x}}_n^{*}(0)\}$, such that the traces are sufficiently close to each other in [0, T − 1]:

$\begin{array}{l}h(1)=\mathrm{Enc}(\mathbf{x}(0))=n.\hfill \\ \hfill \end{array}$

• Controller: In the time interval [0, T − 1], the control action is set as the optimal control action for $\{{\mathbf{x}}_n^{*}(0)\}$, namely

$\begin{array}{l}{({\mathbf{u}}^T(0),\dots ,{\mathbf{u}}^T(T-1))}^T={({({\mathbf{u}}_n^{*})}^T(0),\dots ,{({\mathbf{u}}_n^{*})}^T(T-1))}^T.\hfill \end{array}$

For the jth time period, namely [(j − 1)T, jT − 1], we can use the same encoding and control mechanism by scaling the system state and control actions, namely

$\begin{array}{l}h(j)=\mathrm{Enc}\left(\frac{1}{b^j}\mathbf{x}(0)\right)\hfill \end{array}$

and

$\begin{array}{l}{({\mathbf{u}}^T(jT),\dots ,{\mathbf{u}}^T((j+1)T-1))}^T=b^j{({({\mathbf{u}}_n^{*})}^T(0),\dots ,{({\mathbf{u}}_n^{*})}^T(T-1))}^T.\hfill \end{array}$

The whole procedure is illustrated in Fig. 5.7.

Linear systems

The topological entropy of linear systems is fully explained in the following theorem (the rigorous proof is given in Theorem 2.4.2 of Ref. [11]):

An immediate conclusion is that, when all the eigenvalues of A are within the unit circle, the corresponding topological entropy is zero. Hence the corresponding communication requirement is zero; i.e., no communication is needed for observing or stabilizing the physical systems. This is obvious since the system state will converge to zero spontaneously.

Generic systems

For the generic case of dynamical systems, there have been no systematic approaches to compute the topological entropy. The existing approaches can be categorized into the following two classes:

• Consider some special types of dynamics, such as one-dimensional piecewise monotone mappings [73].

• Discretize the mapping and then using the approaches of calculating the topological entropy of symbol dynamics.

In this book, we provide a brief introduction to the second approach by following the argument in Ref. [74]. We consider a compact topological space M and partition it into a set of subsets Q = {A₁, …, A_q}. Consider a continuous mapping T on M and a discrete time period {0, …, t − 1}. We define

$\begin{array}{l}{W}_t(T,Q)=\{(a_0,\dots ,a_{t-1})|\exists x\in M\text{and}0\le i\le t-1,s.t.,T^{i}x\in A_{a_i}\},\hfill \end{array}$

namely the set of all possible t-strings, each of which represents a series of regions in Q that a trajectory of T passes. An example is given in Fig. 5.8, where the trajectory generates a 6-string (1, 4, 2, 6, 7, 3).

Then we define the following quantity:

$\begin{array}{l}{h}^{*}(T,Q)=\underset{t\to \infty }{lim}\frac{|log{W}_t(T,Q)|}{t}.\hfill \end{array}$

We further define the concept of generating partition:

Then we obtain the following conclusion that provides bounds for the topological entropy of T:

The proof of the theorem can be found in Ref. [74].

Based on this theorem, an algorithm for computing an upper bound of the topological entropy was proposed in Ref. [74], consisting of the following four steps:

• Step 1: Select a coarse partition of M, which is denoted by A.

• Step 2: Select a partition B = {B₁, …, B_K} that is much finer than A. Each element in A is the union of a set of elements in B. Then we define a topological Markov chain. The transition matrix is given by

$\begin{array}{l}{\mathbf{B}}_{ij}=\left\{\begin{array}{cc}1,& \text{if}{B}_i\cap T^{-1}{B}_j\ne \varphi ,\\ 0,& \text{otherwise},\end{array}\right.\hfill \end{array}$

which means that B_ij equals 1 if B_i and B_j are two successive regions that a trajectory of T visits. A sequence (b₀, …, b_N−1) is called a B-word if ${\mathbf{B}}_{b_i,b_{i+1}}=1$. Each B-word corresponds to an A-word (a₀, …, a_N−1), where $B_{b_i}\subset A_{a_i}$. Then we define the set of A-words as

$\begin{array}{l}{W}_N(B,A)=\{\mathbf{a})|\exists B\text{-word}\mathbf{b}\text{generating}\mathbf{a}\}.\hfill \end{array}$

It is easy to verify

$\begin{array}{l}{W}_N(T,A)\subset W_N(B,A),\hfill \end{array}$

which implies

$\begin{array}{ll}h(B,A)\hfill & =\underset{N\to }{lim}\frac{log|W_N(B,A)|}{N}\hfill \\ \hfill & \ge \underset{N\to }{lim}\frac{log|W_N(T,A)|}{N}=h^{*}(T,A).\hfill \end{array}$

It has been shown that h(B, A) converges to h(T, A) if the diameter of B tends to zero.

• Step 3. The set of all B-words forms a sofic shift, whose detailed definition can be found in Ref. [74]. First a directed labeled graph can be constructed, in which each node corresponds to one element in B and an edge exists between nodes i and j if B_ij = 1. Moreover, if B_i ∈ α ∈ A, we label the edge ij (if it exists) as α. The following example from Ref. [74] illustrates the procedure:

Example 1

Consider a one-dimensional mapping T from [0, 1] to [0, 1], which is given by

$\begin{array}{l}Tx=\left\{\begin{array}{cc}2x,\hfill & x<1/2,\hfill \\ 1.5(x-0.5),\hfill & x\ge 1/2.\end{array}\right.\hfill \end{array}$

  (5.49)

The partitions A and B are selected as

$\begin{array}{l}\left\{\begin{array}{c}A=\{A_1,A_2\}=\{[0,0.5),[0.5,1)\},\hfill \\ B=\{B_1,B_2,B_3,B_4\}=\{[0,0.25),[0.25,0.5),[0.5,0.75),[0.75,1)\}.\end{array}\right.\hfill \end{array}$

  (5.50)

It is easy to verify that the matrix B is given by

$\begin{array}{l}\mathbf{B}=\left(\begin{array}{cccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 10\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill \end{array}\right).\hfill \end{array}$

  (5.51)

The graph generated by the matrix B is given in Fig. 5.9. A path in the graph can represent a string.

• Step 4. We compute the entropy of the sofic shift, which is shown to be equal to the topological entropy of the corresponding Markov chain. To that end, we need to find a new graph G′(B, A) satisfying

• W_N(G′(B, A)) = W_N(G(A, B));

• All outgoing edges of the same node have different labels.

The following algorithm from Ref. [74] has been proposed to find such a subgraph of G′, which is called a reduced right-resolving presentation of G:

1. Begin from an empty graph R. Add a single node in G(B, A) to R.

2. If there is at least one hyper node without outgoing hyper edges, choose one of them and label it by H. Otherwise, go to Step 6.

3. Since the hyper node H consists of multiple nodes in G(B, A), define H′ as the set of all nodes in G(B, A) reached by the outgoing edges of the nodes in H that have the same label (say, A_i). Define a new hyper node H′ and a hyper edge pointing from H to H′. Label it as A_i.

4. Repeat Step 3 for all possible labels in A.

5. Return to Step 2.

6. If a hyper node has no incoming hyper edges, remove it.

7. If a hyper node is removed, return to Step 6. Otherwise, stop and output R.

Take the example in Fig. 5.9, for instance. If we begin from node B₁, then we label B₁ as H₁. Since all the outgoing edges of B₁ are labeled as A₁, in Step 3 we form a hyper node H₂ consisting of B₁ and B₂ (since the two outgoing edges reach B₁ and B₂). Since H₂ does not have any outgoing edges, we form a hyper node H₃ consisting of B₁, B₂, B₃ and B4. Then we consider H₃ whose outgoing edges have two labels A₁ and A₂. For A₁, we form a hyper node H₄ consisting of B₁, B₂, and B₃; for A₂, the outgoing edge returns to H₄. This results in the graph shown in Fig. 5.10. Finally, we remove the hyper node H₁.
From the graph R, we can also obtain its adjacency matrix. The example in Fig. 5.10 has the matrix R given by

$\begin{array}{l}\mathbf{B}=\left(\begin{array}{ccc}\hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \end{array}\right).\hfill \end{array}$

We can obtain the eigenvalues of R, which are related to the topological entropy that we want to compute, in the following theorem [74]:

Note that although the above procedure provides a systematic approach for the concrete calculation of topological entropy, it does not completely solve the problem for the following reasons: (1) It is still not clear how to verify that a partition is generating. (2) It is still not clear how to choose the radius of the partitions. Hence we can only choose as small a radius as possible, within the capability of computing.

Gauss-Markov source

Since the sequential rate-distortion function provides a lower bound for the channel capacity of the communication channel, it is important to calculate the sequential rate-distortion function for various information sources for the purpose of online system state estimation. We follow the argument in Ref. [14] to discuss the sequential rate-distortion function for a d-dimensional Gauss-Markov source where

$\begin{array}{l}\mathbf{x}(t+1)=\mathbf{A}\mathbf{x}(t)+\mathbf{w}(t)\hfill \\ \hfill \end{array}$

and

$\begin{array}{l}d(\mathbf{x},\mathbf{y})=\parallel \mathbf{x}-\mathbf{y}{\parallel }_2^2.\hfill \\ \hfill \end{array}$

We assume a Gaussian communication channel with dimension d.

The following lemma shows the necessary property for the infimizing channel in Eq. (5.68) in the definition of a sequential rate-distortion function:

Compared with the standard form P(dY (t)|x(0 : t − 1), y(0 : t − 1)), in the form P(dY (t)|x(t), y(0 : t − 1)) the distribution of Y is dependent only on the current input of the communication channel, instead of all the history. Hence the recovered symbols have the following form:

$\begin{array}{l}\widehat{\mathbf{x}}(t)=\mathbf{F}x(t)+\mathbf{G}y(0:t-1)+\mathbf{z}(t),\hfill \end{array}$

where F is a d × d matrix, G is a d × (t − 1)d matrix, and {z(t)} is a series of independent Gaussian random vectors of dimension d.

Such a channel can be realized for a memoryless Gaussian channel with perfect feedback, which is illustrated in Fig. 5.15. The encoder obtains the innovation, which is given by

$\begin{array}{l}x(t)={\mathbf{F}}_t(\mathbf{x}(t)-E[\mathbf{x}(t)|y(0:t-1)]).\hfill \end{array}$

Since the communication channel output y(0 : t − 1) can be sent to the encoder via the perfect feedback channel, the encoder can easily compute x(t) as above. The decoder receives y(t) = x(t) + z(t) and then obtains the system state estimation:

$\begin{array}{ll}\widehat{\mathbf{x}}(t)\hfill & =\mathbf{F}(\mathbf{x}(t)-E[\mathbf{x}(t)|y(0:t-1)])\hfill \\ \hfill & +{\mathbf{F}}_{t}E[\mathbf{x}(t)|y(0:t-1)]+\mathbf{G}y(0:t-1)+\mathbf{z}(t).\hfill \end{array}$

The channel input should satisfy the power constraint:

$\begin{array}{l}P\ge E[x(t)x^T(t)]=\mathrm{trace}[{\mathbf{F}}_t^T{\Sigma }_{\mathbf{x}(t)|y(0:t-1)}{\mathbf{F}}_t],\hfill \end{array}$

where Σ_{x(t)|y(0:t−1)} is the covariance matrix of the prediction error, namely

$\begin{array}{l}{\Sigma }_{\mathbf{x}(t)|y(0:t-1)}=\mathrm{Cov}(\mathbf{x}(t)-E[\mathbf{x}(t)|y(0:t-1)]).\hfill \end{array}$

For the realized channel, Ref. [14] has proved that

$\begin{array}{l}I(\mathbf{x}(0:T-1);\widehat{\mathbf{x}}(0:T-1))=\sum _{t=0}^{T-1}I(x(t);y(t)),\hfill \end{array}$

because

$\begin{array}{ll}I(\mathbf{x}(0:T-1);\widehat{\mathbf{x}}(0:T-1))\hfill & =\sum _{t=0}^{T-1}I(\mathbf{x}(0:T-1);\widehat{\mathbf{x}}(t)|\widehat{\mathbf{x}}(0:t-1))\hfill \\ \hfill & =\sum _{t=0}^{T-1}I(\mathbf{x}(t);\widehat{\mathbf{x}}(t)|\widehat{\mathbf{x}}(0:t-1)),\hfill \end{array}$

where the second equation is due to the form of the estimation in Eq. (5.72), and

$\begin{array}{ll}I(\mathbf{x}(t);\widehat{\mathbf{x}}(t)|\widehat{\mathbf{x}}(0:t-1))\hfill & =h(\widehat{\mathbf{x}}(t)|\widehat{\mathbf{x}}(0:t-1))-h(\widehat{\mathbf{x}}(t)|\mathbf{x}(t),\widehat{\mathbf{x}}(0:t-1))\hfill \\ \hfill & =h(y(t)|\widehat{\mathbf{x}}(0:t-1))-h(y(t)|x(t),\widehat{\mathbf{x}}(0:t-1))\hfill \\ \hfill & =h(y(t))-h(y(t)|x(t))\hfill \\ \hfill & =I(x(t);y(t)),\hfill \end{array}$

where the second equation is because

$\begin{array}{l}\widehat{\mathbf{x}}(t)=y(t)+{\mathbf{F}}_{t}E[\mathbf{x}(t)|\widehat{\mathbf{x}}(0:t-1)]+{\mathbf{G}}_t\widehat{\mathbf{x}}(0:t-1).\hfill \end{array}$

Before we proceed to compute the sequential rate-distortion function, we provide a review of the traditional rate-distortion function. Consider a d-dimensional Gaussian source with independent samples and d × d covariance matrix Σ_x. The distortion function is given by $d(\mathbf{x},\widehat{\mathbf{x}})=\parallel \mathbf{x}-\widehat{\mathbf{x}}{\parallel }^2$. Then we have [33]

$\begin{array}{l}R(D)=\frac{1}{2}\sum _{n=1}^{d}log\frac{{\lambda }_n}{{\delta }_n},\hfill \end{array}$

where {λ_n}_{n=1, …, d} are the eigenvalues of Σ_x and

$\begin{array}{l}{\delta }_n=\left\{\begin{array}{cc}c,& \text{if}c\le {\lambda }_n,\\ {\lambda }_n,& \text{if}c>{\lambda }_n,\end{array}\right.\hfill \end{array}$

where the constant c is chosen such that ${\sum }_{n=1}^d{\delta }_n=D$. In particular, when d = 1, we have

$\begin{array}{l}R(D)=\frac{1}{2}log\frac{{\lambda }_1}{D}.\hfill \end{array}$

Hence δ_n can be considered as the portion of distortion assigned to the nth eigenvector of Σ_x; then the assignment of {δ_n} can be considered as water filling, as illustrated in Fig. 5.16.

The optimal channel to minimize the rate R given the distortion D is given as follows [75]. Two channels are defined:

• Backward channel: $P(\mathbf{x}|\widehat{\mathbf{x}})$. It is given by

$\begin{array}{l}\mathbf{x}=\widehat{\mathbf{x}}+\delta ,\hfill \end{array}$

where δ is the error, which is Gaussian distributed with zero mean and covariance matrix Σ_x|y. Hence the output $\widehat{\mathbf{x}}$ is also Gaussian distributed with zero mean and expectation:

$\begin{array}{l}{\Sigma }_{\widehat{x}}={\Sigma }_x-{\Sigma }_{x|y}.\hfill \end{array}$

• Forward channel: $P(\widehat{\mathbf{x}}|\mathbf{x})$. It is given by

$\begin{array}{l}\widehat{\mathbf{x}}=\mathbf{H}\mathbf{x}+\mathbf{z},\hfill \end{array}$

where $\mathbf{H}=E[\widehat{\mathbf{x}}{\mathbf{x}}^T]E[{(\mathbf{x}{\mathbf{x}}^T)}^{-1}]$, and z is Gaussian with zero mean and covariance matrix

$\begin{array}{l}{\Sigma }_z=E[\widehat{\mathbf{x}}{\widehat{\mathbf{x}}}^T]-E[\widehat{\mathbf{x}}{\mathbf{x}}^T]E[{(\mathbf{x}{\mathbf{x}}^T)}^{-1}]E[\mathbf{x}{\widehat{\mathbf{x}}}^T].\hfill \end{array}$

To realize the forward channel $\widehat{\mathbf{x}}=\mathbf{H}\mathbf{x}+\mathbf{z}$, one can define an invertible matrix Γ such that ΓHΓ⁻¹ = I. Define $\mathbf{b}=\Gamma \widehat{\mathbf{x}}$, a = Γx, and n = Γz. Then the channel b = a + n with power constraint E[a^Ta] ≤ trace(ΓΣ_xΓ^T) is matched to the information source.

We also need the concept of a matched channel. The stochastic kernel $P(d\widehat{\mathbf{x}}(t)|\mathbf{x}(0:t-1),\widehat{\mathbf{x}}(t-1))$ can be considered as a communication channel with input x(t) and output $\widehat{\mathbf{x}}(t)$ [76]. If the real communication channel is equal to the channel that minimizes the rate given the distortion, then the communication channel is said to be matched to the information source. When the communication channel is matched to the source, there is no need for the structure of separated source encoder and channel encoder. The information can be sent in an uncoded manner without any loss in performance.

Then for the sequential rate-distortion function, we can convert it to the traditional rate-distortion expression. We begin with the scalar Gaussian source case. The distortion is given by ${\sigma }_x^2{2}^{-2R}$. The encoder computes the innovation information:

$\begin{array}{ll}\mathbf{x}(t)\hfill & -E[\mathbf{x}(t)|\widehat{\mathbf{x}}(0:t-1)]\hfill \\ \hfill & =\mathbf{A}\mathbf{x}(t-1)+\mathbf{w}(t)-\mathbf{A}\widehat{\mathbf{x}}(t-1)\hfill \\ \hfill & =\mathbf{A}(\mathbf{x}(t-1)-\widehat{\mathbf{x}}(t-1))+\mathbf{w}(t)\hfill \\ \hfill & =\mathbf{A}\delta (t-1)+\mathbf{w}(t),\hfill \end{array}$

where $\delta (t)=\mathbf{x}-\widehat{\mathbf{x}}(t)$ is the estimation error. Since the error variance is equal to the distortion, namely D(t) = E[δ²(t)], then the variance of the innovation information is given by

$\begin{array}{l}E[\parallel x(t){\parallel }^2]=A^{2}D(t-1)+{\sigma }_w^2,\hfill \end{array}$

where ${\sigma }_w^2$ is the scalar notation of Σ_w.

In the above argument for the traditional rate-distortion function, we have shown that the scalar Gaussian variable has variance ${\sigma }_x^2$ when a Gaussian channel having capacity R is matched to the source. Hence the distortions at different times can be obtained recursively as follows:

$\begin{array}{l}\left\{\begin{array}{c}D(t)=(A^{2}D(t-1)+{\sigma }_w^2)2^{-2R(t)},\forall t\ge 1,\\ D(0)={\sigma }_{x_0}^2{2}^{-2R(0)}.\end{array}\right.\hfill \end{array}$

For the sequential rate-distortion function, we have D(t) = D. Hence we have

$\begin{array}{l}\left\{\begin{array}{c}R(t)=max\{0,1/2log(A^2+({\sigma }_w^2/D))\},\forall t\ge 1,\\ R(0)=max\{0,1/2log({\sigma }_w^2/D)\}.\end{array}\right.\hfill \end{array}$

When T is sufficiently large, the impact of R(0) will vanish. Hence we have

$\begin{array}{l}\underset{T\to \infty }{lim}{R}_T^s(D)=max\left\{0,\frac{1}{2}log\left(A^2+\frac{{\sigma }_w^2}{D}\right)\right\}.\hfill \end{array}$

Now we handle the generic case of a d-dimensional Gauss-Markov source. The covariance matrix of the distortion error δ(t) is denoted by Σ(t) = E[δ(t)δ^T(t)]. The evolution of the covariance matrix can be easily shown to be

$\begin{array}{l}\Sigma (t)=\mathbf{A}\Sigma (t-1){\mathbf{A}}^T+{\Sigma }_w.\hfill \end{array}$

Consider the unitary matrix U(t) that diagonalizes the matrix AΣ(t − 1)A^T + Σ_w:

$\begin{array}{l}\mathbf{U}(\mathbf{A}\Sigma (t-1){\mathbf{A}}^T+{\Sigma }_w){\mathbf{U}}^T=\mathrm{diag}[{\lambda }_1(t),\dots ,{\lambda }_d(t)].\hfill \end{array}$

From the previous water-filling argument, to achieve the distortion D, the coding rate needs to be

$\begin{array}{l}R(t)=\sum _{n=1}^d\frac{1}{2}log\left(\frac{{\lambda }_n(t)}{{\sigma }_n(t)}\right),\hfill \end{array}$

where

$\begin{array}{l}{\sigma }_n(t)=\left\{\begin{array}{cc}c(t),& \text{if}c(t)\le {\lambda }_n(t),\\ {\lambda }_n(t),& \text{if}c(t)>{\lambda }_n(t),\end{array}\right.\hfill \end{array}$

where the constant c(t) is chosen such that ${\sum }_{n=1}^d{\sigma }_n(t)=D$.