On the Relation between Topological Entropy and Restoration Entropy

Abstract

In the context of state estimation under communication constraints, several notions of dynamical entropy play a fundamental role, among them: topological entropy and restoration entropy. In this paper, we present a theorem that demonstrates that for most dynamical systems, restoration entropy strictly exceeds topological entropy. This implies that robust estimation policies in general require a higher rate of data transmission than non-robust ones. The proof of our theorem is quite short, but uses sophisticated tools from the theory of smooth dynamical systems.

1. Introduction

This paper compares two notions of entropy that are relevant in the context of state estimation under communication constraints. Since the work of Savkin [1], it has been well known that the topological entropy of a dynamical system characterizes the smallest rate of information above which an estimator, receiving its state information at the corresponding rate, is able to generate a state estimate of arbitrary precision. Topological entropy is a quantity that has been studied in the mathematical field of dynamical systems since the 1960s and has turned out to be a useful tool for solving many theoretical and practical problems, cf. the survey [2] and the monograph [3]. A big drawback of this notion in the context of state estimation is that topological entropy is highly discontinuous with respect to the dynamical system under consideration in any reasonable topology, cf. [4]. As a consequence, estimation policies based on topological entropy are likely to suffer from a lack of robustness. Additionally, topological entropy is very hard to compute or estimate. There are only few numerical approaches that potentially work for multi-dimensional systems, cf. [5,6,7,8], and each of them has its drawbacks and restrictions.

A possible remedy for these problems is provided in the works [9,10] of Matveev and Pogromsky. One of the main ideas in these papers is to replace the topological entropy as a figure-of-merit for the necessary rate of data transmission with a possibly larger quantity, named restoration entropy, which describes the smallest data rate above which a more robust form of state estimation can be achieved (called regular observability in [9,10]).

Looking at one of the simplest types of nonlinear dynamical systems, namely Anosov diffeomorphisms, the main result of the paper at hand demonstrates that for most dynamical systems, we have to expect that the restoration entropy strictly exceeds the topological entropy. That is, to achieve a state estimation objective that is more robust with respect to perturbations, one has to pay the price of using a channel that allows for a larger rate of data transmission. More specifically, our result shows that the equality of topological and restoration entropy implies a great amount of uniformity in the dynamical system under consideration, which can be expressed in terms of the unstable Lyapunov exponents at each point, whose sum essentially has to be a constant. Such a property can easily be destroyed by a small perturbation, showing that arbitrarily close to the given system, we find systems whose restoration entropy strictly exceeds their topological entropy. Since Anosov diffeomorphisms are considered as a paradigmatic class of chaotic dynamical systems, this property can be expected for a much larger class of systems.

To prove our result, we need a number of high-level concepts and results from the theory of topological, measurable, and smooth dynamical systems. This includes the concepts of topological and metric pressure, Lyapunov exponents, SRB measures, and uniform hyperbolicity.

For further reading on the topic of state estimation under communication constraints, we refer the reader to [1,9,10,11,12,13,14] and the references given therein.

The structure of this paper is as follows: In Section 2, we collect all necessary definitions and results from the theory of dynamical systems. Section 3 introduces the concept of restoration entropy and explains its operational meaning in the context of estimation under communication constraints. In Section 4, we prove our main result and provide some interpretation and an example. Finally, Section 5 contains some concluding remarks.

2. Tools from Dynamical Systems

Notation: By $\mathbb{Z}$, we denote the set of all integers, by $\mathbb{N}$ the set of positive integers, and ${\mathbb{N}}_0:=\{0\}\cup \mathbb{N}$. All logarithms are taken to the base two. If M is a Riemannian manifold, we write $|·|$ for the induced norm on any tangent space $T_{x}M$, $x\in M$. The notation $\parallel ·\parallel$ is reserved for operator norms. We write $\mathrm{cl}A$ and $\mathrm{int}A$ for the closure and the interior of a set A in a metric space, respectively. Finally, the notation $A\subset B$ (A subset of B) does not exclude the case $A=B$.

In this paper, we use several sophisticated results from the theory of dynamical systems, in particular from smooth ergodic theory. In the following, we try to explain these results without going too much into technical details.

Let $T:X\to X$ be a continuous map on a compact metric space $(X,d)$. Via its iterates:

$$T^0:={\mathrm{id}}_X,T^{n+1}:=T\circ T^n,n=0,1,2,\dots$$

the map T generates a discrete-time dynamical system on X with associated orbits ${\{T^n(x)\}}_{n\in {\mathbb{N}}_0}$, $x\in X$. We call the pair $(X,T)$ a topological dynamical system (TDS).

2.1. Entropy and Pressure

Let $(X,T)$ be a TDS. The topological entropy $h_{\mathrm{top}}(T)$ measures the total exponential complexity of the orbit structure of $(X,T)$ in terms of the maximal numbers of finite-time orbits that are distinguishable w.r.t. to a finite resolution. One amongst different possible formal definitions is as follows. For $n\in \mathbb{N}$ and $\epsilon >0$, a set $E\subset X$ is called $(n,\epsilon ,T)$-separated if for any $x,y\in E$ with $x\ne y$, we have:

$$d(T^i(x),T^i(y))\ge \epsilon \mathrm{for}\mathrm{at}\mathrm{least}\mathrm{one}0\le i<n.$$

That is, we can distinguish any two points in E at a resolution of $\epsilon$ by looking at their length-n finite-time orbits. By the compactness of X, there is a uniform upper bound on the cardinality of any (n, ε, T)-separated set. Writing r(n, ε, T) for the maximal possible cardinality,

$$\begin{array}{c}\hfill h_{\mathrm{top}}(T):=\underset{\epsilon \downarrow 0}{lim}\underset{n\to \infty }{lim\; sup}\frac{1}{n}logr(n,\epsilon ,T).\end{array}$$

This definition is due to Bowen [15] and (independently) Dinaburg [16]. However, it should be noted that the first definition of topological entropy, given by Adler, Konheim, and McAndrew [17], was in terms of open covers of X and was modeled in strict analogy to the metric (= measure−theoretic) entropy defined earlier by Kolmogorov and Sinai [18,19].

To define metric entropy, one additionally needs a Borel probability measure $\mu$ on X that is preserved by T in the sense that $\mu (A)=\mu (T^{-1}(A))$ for every Borel set A. By the theorem of Krylov–Bogolyubov, every continuous map on a compact space admits at least one such measure, cf. [20], Theorem 4.1.1. We write ${\mathcal{M}}_T$ for the set of all T-invariant Borel probability measures. For any finite measurable partition $\mathcal{P}$ of X, we define the entropy of T on $\mathcal{P}$ by:

$$h_{\mu }(T;\mathcal{P}):=\underset{n\to \infty }{lim}\frac{1}{n}{H}_{\mu }\left(\underset{i=0}{\overset{n-1}{\bigvee }}{T}^{-i}\mathcal{P}\right).$$

Here, ⋁ denotes the join operation. That is, ${\bigvee }_{i=0}^{n-1}{T}^{-i}\mathcal{P}$ is the partition of X whose elements are all intersections of the form $P_0\cap T^{-1}(P_1)\cap \dots \cap T^{-n+1}(P_{n-1})$ with $P_i\in \mathcal{P}$. Moreover, $H_{\mu }(·)$ denotes the Shannon entropy of a partition, i.e., $H_{\mu }(\mathcal{Q})=-{\sum }_{Q\in \mathcal{Q}}\mu (Q)log\mu (Q)$ for any finite partition $\mathcal{Q}$. The metric entropy of T w.r.t. $\mu$ is then defined by:

$$h_{\mu }(T):=\underset{\mathcal{P}}{sup}{h}_{\mu }(T;\mathcal{P}),$$

the supremum taken over all finite measurable partitions $\mathcal{P}$ of X (replacing measurable partitions with open covers and Shannon entropy with the logarithm of the cardinality of a minimal finite subcover, the same construction yields the topological entropy as defined in [17]).

To understand the meaning of $h_{\mu }$, note that $H_{\mu }(\mathcal{Q})$ is the average amount of uncertainty as one attempts to predict the partition element to which a randomly-chosen point belongs. Hence, $h_{\mu }(T)$ measures the average uncertainty per iteration in guessing the partition element of a typical length-n orbit.

The variational principle for entropy states that:

$$h_{\mathrm{top}}(T)=\underset{\mu \in {\mathcal{M}}_T}{sup}{h}_{\mu }(T),$$

(1)

where the supremum is not necessarily a maximum. This variational principle can be regarded as a quantitative version of the theorem of Krylov–Bogolyubov.

Another concept (of which entropy is a special case) used in dynamical systems and inspired by ideas in thermodynamics is pressure. In this context, any continuous function $\varphi :X\to \mathbb{R}$, also called a potential or an observable, gives rises to the metric pressure of T w.r.t. $\varphi$ for a given $\mu \in {\mathcal{M}}_T$, defined as:

$$P_{\mu }(T,\varphi ):=h_{\mu }(T)+\int \varphi \mathrm{d}\mu .$$

To define an associated notion of topological pressure, put $S_n\varphi (x):={\sum }_{i=0}^{n-1}\varphi (T^i(x))$ and:

$$R(n,\epsilon ,\varphi ;T):=sup\left\{\sum _{x\in E}{2}^{S_n\varphi (x)}:E\subset X\mathrm{is}(n,\epsilon ,T)-\mathrm{separated}\right\}.$$

Then, the topological pressure of T w.r.t. $\varphi$ is given by:

$$P_{\mathrm{top}}(T,\varphi ):=\underset{\epsilon \downarrow 0}{lim}\underset{n\to \infty }{lim\; sup}\frac{1}{n}logR(n,\epsilon ,\varphi ;T).$$

The associated variational principle, first proven in [21], reads:

$$P_{\mathrm{top}}(T,\varphi )=\underset{\mu \in {\mathcal{M}}_T}{sup}{P}_{\mu }(T,\varphi ),$$

(2)

which includes (1) as a special case (simply put $\varphi =0$).

2.2. Subadditive Cocycles

Let $T:X\to X$ be a map. A subadditive cocycle over $(X,T)$ is a sequence ${(f_n)}_{n\in {\mathbb{N}}_0}$ of functions $f_n:X\to \mathbb{R}$ satisfying:

$$f_{n+m}(x)\le f_n(x)+f_m(T^n(x)),\forall n,m\in {\mathbb{N}}_0,x\in X.$$

If equality holds in this relation, we call ${(f_n)}_{n\in {\mathbb{N}}_0}$ an additive cocycle over $(X,T)$.

If X has the structure of a probability space with a $\sigma$-algebra $\mathcal{F}$ and a probability measure $\mu$ on $\mathcal{F}$, T is measurable, and $\mu$ is T-invariant, we speak of a measurable subadditive cocycle provided that all $f_n$ are measurable. In the context of a TDS $(X,T)$, we speak of a continuous subadditive cocycle if all $f_n$ are continuous.

The most fundamental result about subadditive cocycles is Kingman’s subadditive ergodic theorem, cf. [3], Theorem 2.1.4:

Theorem 1.

Let $T:X\to X$ be a measure-preserving map on a probability space $(X,\mathcal{F},\mu )$ and ${(f_n)}_{n\in {\mathbb{N}}_0}$ a measurable subadditive cocycle over $(X,T)$ such that each $f_n$ is integrable. Then, the limit:

$$\underset{n\to \infty }{lim}\frac{1}{n}{f}_n(x)$$

exists for μ-almost every $x\in X$. If, additionally, μ is ergodic, then the limit is constant with:

$$\underset{n\to \infty }{lim}\frac{1}{n}{f}_n(x)=\underset{n\to \infty }{lim}\frac{1}{n}\int f_n\mathrm{d}\mu .$$

(3)

Observe that the limit on the right-hand side of (3) always exists by Fekete’s subadditivity lemma (see [3], Fact 2.1.1), because the sequence $a_n:=\int f_n\mathrm{d}\mu$ is subadditive, i.e., $a_{n+m}\le a_n+a_m$. Kingman’s theorem can, in particular, be applied if $(X,T)$ is a TDS, $\mu \in {\mathcal{M}}_T$, and ${(f_n)}_{n\in {\mathbb{N}}_0}$ is a continuous subadditive cocycle.

Now, we consider again a TDS $(X,T)$ and a continuous subadditive cocycle ${(f_n)}_{n\in {\mathbb{N}}_0}$ over $(X,T)$. We define the extremal growth rate of $(f_n)$ by:

$$\beta [(f_n)]:=\underset{x\in X}{sup}\underset{n\to \infty }{lim\; sup}\frac{1}{n}{f}_n(x).$$

The following result is well known and can be found in [22], Theorem A.3, for instance:

Lemma 1.

Let ${(f_n)}_{n\in {\mathbb{N}}_0}$ be a continuous subadditive cocycle over a TDS $(X,T)$. Then:

$$\beta [(f_n)]=\underset{\mu \in {\mathcal{M}}_T}{sup}\underset{n>0}{inf}\frac{1}{n}\int f_n\mathrm{d}\mu =\underset{n>0}{inf}\underset{x\in X}{sup}\frac{1}{n}{f}_n(x)=\underset{n>0}{inf}\underset{\mu \in {\mathcal{M}}_T}{sup}\frac{1}{n}\int f_n\mathrm{d}\mu .$$

Here, all infima can be replaced with limits. Moreover, every supremum is attained.

2.3. Lyapunov Exponents, SRB Measures, and Pesin’s Formula

To describe the long-term dynamical behavior of smooth systems, the notion of Lyapunov exponents is crucial. Given a $C^1$-diffeomorphism $T:M\to M$ on a compact Riemannian manifold M, the Lyapunov exponent at $x\in M$ in direction $0\ne v\in T_{x}M$ is the number:

$$\lambda (x,v):=\underset{n\to \infty }{lim}\frac{1}{n}log|\mathrm{D}{T}^n(x)v|,$$

provided that the limit exists. Lyapunov exponents measure how fast nearby solutions diverge from each other. The most general result on their existence and their properties is the multiplicative ergodic theorem (MET), also known as Oseledets theorem, cf. [23,24]. We need the following version of the theorem (which is not the most general):

Theorem 2.

Let $T:M\to M$ be a $C^1$-diffeomorphism of a compact Riemannian manifold M and $\mu \in {\mathcal{M}}_T$. Then, there exists a Borel set $\Omega \subset M$ with $\mu (\Omega )=1$ and $T(\Omega )=\Omega$ such that the following holds: for every $x\in \Omega$, there exist numbers ${\lambda }_1(x)>\dots >{\lambda }_{r(x)}(x)$, and the tangent space at x splits into linear subspaces as:

$$T_{x}M=E_1(x)\oplus \cdots \oplus E_{r(x)}(x)$$

such that the following properties hold:

(i) 

For every $0\ne v\in E_i(x)$, we have:

$$\underset{n\to \pm \infty }{lim}\frac{1}{n}log|\mathrm{D}{T}^n(x)v|={\lambda }_i(x).$$

(ii) 

The functions $r(·)$, $dim{E}_i(·)$, and ${\lambda }_i(·)$ are measurable and constant along orbits. Moreover,

$$\mathrm{D}T(x)E_i(x)=E_i(T(x)),i=1,\dots ,r(x).$$

(iii) 

For every $x\in \Omega$, the limit:

$${\Lambda }_x:=\underset{n\to \infty }{lim}{(\mathrm{D}{T}^n{(x)}^{*}\mathrm{D}{T}^n(x))}^{1/2n}$$

exists, and the different eigenvalues of ${\Lambda }_x$ are $2^{{\lambda }_1(x)},\dots ,2^{{\lambda }_{r(x)}(x)}$ (here, $\mathrm{D}{T}^n{(x)}^{*}$ denotes the adjoint of $\mathrm{D}{T}^n(x)$).

Typically, a given map has a huge number of associated invariant measures. To obtain a good description of the global dynamical behavior, one has to select specific invariant measures that determine the behavior of the system on a large set of initial states. In this context, the notion of an SRB measure (Sinai–Ruelle–Bowen measure) comes into play. An SRB measure is a measure with at least one positive Lyapunov exponent almost everywhere, having absolutely continuous conditional measures on unstable manifolds. We are not going to give a technical definition of the latter property. Instead, we state the following celebrated theorem due to Ledrappier and Young [25], which characterizes this property in terms of metric entropy. Here, we use the short-cut:

$${\lambda }^{+}(x):=\sum _{i=1}^{r(x)}max\{0,{\lambda }_i(x)dim{E}_i(x)\}$$

for the sum of all positive Lyapunov exponents at a point $x\in \Omega$, counted with multiplicities.

Theorem 3.

Let $T:M\to M$ be a $C^2$-diffeomorphism of a compact manifold M and $\mu \in {\mathcal{M}}_T$. Then, the formula:

$$h_{\mu }(T)=\int {\lambda }^{+}\mathrm{d}\mu$$

(4)

holds if and only if μ has absolutely continuous conditional measures on unstable manifolds.

Additionally, note that for any $C^1$-diffeomorphism T and any $\mu \in {\mathcal{M}}_T$, the inequality:

$$h_{\mu }(T)\le \int {\lambda }^{+}\mathrm{d}\mu$$

(5)

holds, which is known as Ruelle’s inequality or Ruelle–Margulis inequality [26] (Formula (4) was first proven by Pesin for smooth invariant measures).

2.4. Anosov Diffeomorphisms

One of the simplest classes of smooth dynamical systems with complicated dynamical behavior is the class of Anosov diffeomorphisms. In this paper, we use these systems for two reasons. First, they have positive topological entropy, and second, they are very well understood and there are many tools available to describe their properties.

Let M be a compact Riemannian manifold. A $C^1$-diffeomorphism $T:M\to M$ is called an Anosov diffeomorphism if there exists a splitting:

$$T_{x}M=E_x^u\oplus E_x^s,\forall x\in M$$

into linear subspaces such that the following conditions are satisfied:

(A1)

$\mathrm{D}T(x)E_x^u=E_{T(x)}^u$ and $\mathrm{D}T(x)E_x^s=E_{T(x)}^s$ for all $x\in M$.

(A2)

There are constants $c\ge 1$ and $\lambda \in (0,1)$, so that, for all $x\in M$ and $n\in {\mathbb{N}}_0$,

$$\begin{array}{cc}\hfill |\mathrm{D}{T}^n(x)v|& \le c{\lambda }^n|v|\mathrm{for}\mathrm{all}v\in E_x^s,\hfill \\ \hfill |\mathrm{D}{T}^{-n}(x)v|& \le c{\lambda }^n|v|\mathrm{for}\mathrm{all}v\in E_x^u.\hfill \end{array}$$

From (A1) and (A2), it automatically follows that $E_x^s$ and $E_x^u$ vary continuously with x, cf. [20], Proposition 6.4.4. The existence of a splitting as above is also known as uniform hyperbolicity.

The simplest examples of Anosov diffeomorphisms are hyperbolic linear torus automorphisms, i.e., maps on the n-dimensional torus ${\mathbb{T}}^n={\mathbb{R}}^n/{\mathbb{Z}}^n$ of the form:

$$T_A(x)=Ax(\mathrm{mod}{\mathbb{Z}}^n),T_A:{\mathbb{T}}^n\to {\mathbb{T}}^n,$$

where $A\in {\mathbb{Z}}^{n\times n}$ is an integer matrix satisfying $|detA|=1$ and $|\lambda |\ne 1$ for all eigenvalues $\lambda$ of A. Observe that the assumption $|detA|=1$ guarantees that $T_A$ is invertible with inverse $T_A^{-1}=T_{A^{-1}}$ (because $A^{-1}$ also has integer entries) and at the same time implies that $T_A$ is area-preserving. That is, the normalized Lebesgue measure on ${\mathbb{T}}^n$ is an element of ${\mathcal{M}}_{T_A}$. The assumption on the eigenvalues of A together with the fact that the derivative $\mathrm{D}{T}_A(x)$ at any point $x\in {\mathbb{T}}^n$ can be identified with A itself implies the Anosov Properties (A1) and (A2).

It is well known that Anosov diffeomorphisms are structurally stable, i.e., any sufficiently small $C^1$-perturbation $T_{\epsilon }$ of an Anosov diffeomorphism $T:M\to M$ is also an Anosov diffeomorphism, which is topologically conjugate to T, see [20], Proposition 6.4.6 and Corollary 18.2.2. That is, there exists a homeomorphism $h:M\to M$, so that:

$$h^{-1}\circ T_{\epsilon }\circ h=T.$$

If we assume that T is an arbitrary Anosov diffeomorphism of the torus, the existence of a unique entropy-maximizing measure $\mu$ follows. That is, $\mu$ is the unique element of ${\mathcal{M}}_T$ satisfying:

$$h_{\mathrm{top}}\left(T\right)=h_{\mu }\left(T\right).$$

This follows from a combination of results that can be found in Katok and Hasselblatt [20], namely Theorem 20.3.7, Proposition 18.6.5, Theorem 18.3.9, and Corollary 6.4.10. The entropy-maximizing measure $\mu$ is also known as the Bowen-measure.

In this context, also the notion of topological mixing is important. An Anosov diffeomorphism (or simply a continuous map) $T:M\to M$ is called topologically mixing if for any two nonempty open sets $A,B\subset M$, there exists an integer N such that $T^n(A)\cap B\ne \varnothing$ for all $n\ge N$. In particular, all Anosov diffeomorphisms on ${\mathbb{T}}^n$ are topologically mixing ([20], Proposition 18.6.5).

3. State Estimation and Restoration Entropy

The notion of restoration entropy was introduced in [10] for systems given by ODEs on ${\mathbb{R}}^n$. However, it is immediately clear from the definition that restoration entropy can be defined for any continuous map on a compact metric space as follows. Let $T:X\to X$ be a continuous map on a metric space $(X,d)$ and $K\subset X$ a compact set with $T(K)\subset K$. For every $x\in X$, $n\in \mathbb{N}$ and $\epsilon >0$, let $p(n,x,\epsilon )$ denote the smallest number of $\epsilon$-balls needed to cover the image $T^n(B_{\epsilon }(x)\cap K)$. If the map is not clear from the context, we also write $p(n,x,\epsilon ;T)$. Then:

$$h_{\mathrm{res}}(T_{|K}):=\underset{n\to \infty }{lim}\frac{1}{n}\underset{\epsilon \downarrow 0}{lim\; sup}\underset{x\in X}{sup}logp(n,x,\epsilon ).$$

The existence of the limit in n follows from the subadditivity of the sequence $a_n:={lim\; sup}_{\epsilon \downarrow 0}$ ${sup}_{x\in X}logp(n,x,\epsilon )$ (using Fekete’s lemma). If we assume that T is a $C^1$-diffeomorphism of a compact Riemannian manifold, the numbers $p(n,x,\epsilon )$ can be estimated in terms of the unstable singular values of $\mathrm{D}{T}^n(x)$. This is related to the simple fact that the image of a ball under a linear map (in our case, the local linear approximation $\mathrm{D}{T}^n(x)$ to $T^n$) is an ellipsoid with semi-axes of lengths proportional to the singular values. This leads to the following result, proven in [10], Theorem 11, for continuous-time systems. The proof carries over to discrete-time systems on Riemannian manifolds without any problem.

Theorem 4.

Let $T:M\to M$ be a $C^1$-diffeomorphism of a d-dimensional Riemannian manifold M and $K\subset M$ a forward-invariant compact set of T with $\mathrm{cl}K=\mathrm{cl}(\mathrm{int}K)$. Then:

$$h_{\mathrm{res}}(T_{|K})=\underset{n\to \infty }{lim}\frac{1}{n}\underset{x\in K}{max}\sum _{i=1}^{d}max\{0,log{\alpha }_i(n,x)\},$$

where ${\alpha }_1(n,x)\ge \dots \ge {\alpha }_d(n,x)$ denote the singular values of $\mathrm{D}{T}^n(x)$.

For the analysis of $h_{\mathrm{res}}$, based on the above formula, the following observations are crucial:

• We have

  $$\sum _{i=1}^{d}max\{0,log{\alpha }_i(n,x)\}=log\prod _{i=1}^{d}max\{1,log{\alpha }_i(n,x)\}=log\parallel \mathrm{D}{T}^n{(x)}^{\wedge }\parallel ,$$

  where $\mathrm{D}{T}^n{(x)}^{\wedge }$ denotes the linear map induced by $\mathrm{D}{T}^n(x)$ between the full exterior algebras of the tangent spaces $T_{x}M$ and $T_{T^n(x)}M$, respectively; see [27], Chapter I, Proposition 7.4.2.
• The sequence $f_n(x):=log\parallel \mathrm{D}{T}^n{(x)}^{\wedge }\parallel$, $f_n:M\to \mathbb{R}$, is a continuous subadditive cocycle over $(K,T_{|K})$, since:

  $$\begin{array}{cc}\hfill f_{n+m}(x)& =log\parallel \mathrm{D}{T}^{n+m}{(x)}^{\wedge }\parallel =log\parallel \mathrm{D}{T}^m{(T^n(x))}^{\wedge }\mathrm{D}{T}^n{(x)}^{\wedge }\parallel \hfill \\ & \le log\left(\parallel \mathrm{D}{T}^m{(T^n(x))}^{\wedge }\parallel ·\parallel \mathrm{D}{T}^n{(x)}^{\wedge }\parallel \right)\hfill \\ & =log\parallel \mathrm{D}{T}^n{(x)}^{\wedge }\parallel +log\parallel \mathrm{D}{T}^m{(T^n(x))}^{\wedge }\parallel =f_n(x)+f_m(T^n(x)).\hfill \end{array}$$
  Alternatively, this follows from Horn’s inequality for singular values; see [27], Chapter I, Proposition 2.3.1.

In the following, we explain the operational meaning of the quantity $h_{\mathrm{res}}(T_{|K})$.

Consider the dynamical system given by:

$$x_{t+1}=T(x_t),x_0\in K,t=0,1,2,\dots$$

(6)

Suppose that a sensor, fully observing the state $x_t$, sends its data to an encoder. At the sampling times $t=0,1,2,\dots$, the encoder sends a signal $e_t$ through a noise-free discrete channel to a decoder (without transmission delay). The decoder acts as an observer of the system, trying to reconstruct the state from the received data. We write ${\widehat{x}}_t$ for the estimate generated by the observer at time t. Moreover, we assume that we start with an initial estimate ${\widehat{x}}_0\in K$ of a specified accuracy.

With $\mathcal{M}$ denoting the coding alphabet, the encoder and the observer are described by mappings:

$$e_t={\mathcal{C}}_t(x_0,x_1,\dots ,x_t;{\widehat{x}}_0,\delta ),{\mathcal{C}}_t:K^{t+1}\times K\times {\mathbb{R}}_{>0}\to \mathcal{M},$$

and:

$${\widehat{x}}_t={\mathcal{E}}_t(e_0,e_1,\dots ,e_t;{\widehat{x}}_0,\delta ),{\mathcal{E}}_t:{\mathcal{M}}^{t+1}\times K\times {\mathbb{R}}_{>0}\to X.$$

The argument $\delta$ corresponds to the initial error at time zero, i.e., $d(x_0,{\widehat{x}}_0)\le \delta$. In particular, we assume that both the encoder and the observer are given the data ${\widehat{x}}_0$ and $\delta$.

We assume that the channel can transmit at least $b_{-}(r)$ and at most $b_{+}(r)$ bits in any time interval of length r. The capacity of the channel is then defined by:

$$C:=\underset{r\to \infty }{lim}\frac{b_{-}(r)}{r}=\underset{r\to \infty }{lim}\frac{b_{+}(r)}{r},$$

assuming that these limits exist and coincide.

We consider the following two observation objectives:

(O1)

The observer observes the system with exactness $\epsilon >0$ if there exists $\delta =\delta (\epsilon ,K)$, so that $x_0,{\widehat{x}}_0\in K$ with $d(x_0,{\widehat{x}}_0)\le \delta$ implies:

$$\underset{t\ge 0}{sup}d(x_t,{\widehat{x}}_t)\le \epsilon .$$

(O2)

The observer regularly observes the system if there exist $G,{\delta }_{*}>0$, so that for all $\delta \in (0,{\delta }_{*})$ and $x_0,{\widehat{x}}_0\in K$ with $d(x_0,{\widehat{x}}_0)\le \delta$,

$$\underset{t\ge 0}{sup}d(x_t,{\widehat{x}}_t)\le G\delta .$$

We say that the system is:

• observable on K over a channel of capacity C if for every $\epsilon >0$, an observer exists that observes the system with exactness $\epsilon$ over this channel;
• regularly observable on K over a channel of capacity C if there exists an observer that regularly observes the system over this channel.

Then, we have the following data-rate theorem, cf. [9], Theorem 8, and [10], Theorem 9.

Theorem 5.

The smallest channel capacity $C_0$, so that System (6) is:

• observable on K over every channel of capacity $C>C_0$ is given by:

  $$C_0=h_{\mathrm{top}}(T_{|K}).$$
• regularly observable on K over every channel of capacity $C>C_0$ is given by:

  $$C_0=h_{\mathrm{res}}(T_{|K}).$$

Since regular observability implies observability, it is clear that:

$$h_{\mathrm{top}}(T_{|K})\le h_{\mathrm{res}}(T_{|K}).$$

As already pointed out in the Introduction, the quantity $h_{\mathrm{top}}(·)$ is highly discontinuous w.r.t. the dynamical system. Moreover, the corresponding data-rate theorem has the disadvantage that the final error $\epsilon$ may be much larger than the initial error $\delta$, which cannot happen in the case of regular observability. From Theorem 4 in combination with Lemma 1, one sees that in the smooth case, $h_{\mathrm{res}}$ is an infimum over functions that are continuous w.r.t. T in the $C^1$-topology. This implies at least upper semicontinuity. Hence, we can expect that coding and estimation strategies based on restoration entropy enjoy better properties than those based on topological entropy.

4. Results

Before we present our main result, we prove two lemmas, which are of independent interest.

Lemma 2.

Let $T:M\to M$ be a $C^2$-diffeomorphism on a compact Riemannian manifold M. Then, for any $\mu \in {\mathcal{M}}_T$, we have:

$$\int {\lambda }^{+}\mathrm{d}\mu =\underset{n\to \infty }{lim}\frac{1}{n}\int log\parallel \mathrm{D}{T}^n{(x)}^{\wedge }\parallel \mathrm{d}\mu (x).$$

Proof. 

Let $d=dimM$. First observe that we have the identity:

$$\parallel \mathrm{D}{T}^n{(x)}^{\wedge }\parallel =max\left\{1,\underset{1\le k\le d}{max}\prod _{i=1}^k{\alpha }_i(n,x)\right\},$$

where ${\alpha }_1(n,x)\ge \dots \ge {\alpha }_d(n,x)$ are the singular values of $\mathrm{D}{T}^n(x)$, see [27], Chapter I, Proposition 7.4.2. Hence,

$$log\parallel \mathrm{D}{T}^n{(x)}^{\wedge }\parallel =max\left\{0,\underset{1\le k\le d}{max}\sum _{i=1}^{k}log{\alpha }_i(n,x)\right\}.$$

The maximum over k is clearly attained when k is the maximal number such that ${\alpha }_i(n,x)>1$ for all $1\le i\le k$. Hence,

$$log\parallel \mathrm{D}{T}^n{(x)}^{\wedge }\parallel =max\left\{0,\sum _{{\alpha }_i(n,x)>1}log{\alpha }_i(n,x)\right\}.$$

The numbers ${\alpha }_i(n,x)$ are the eigenvalues of $A_n(x):={(\mathrm{D}{T}^n{(x)}^{*}\mathrm{D}{T}^n(x))}^{1/2}$. Theorem 2 states that $A_n{(x)}^{1/n}\to {\Lambda }_x$ for $\mu$-almost every $x\in M$ and the logarithms of the eigenvalues of ${\Lambda }_x$ are the Lyapunov exponents at x. Since eigenvalues depend continuously on the matrix, it follows that:

$$\underset{n\to \infty }{lim}\frac{1}{n}log\parallel \mathrm{D}{T}^n{(x)}^{\wedge }\parallel ={\lambda }^{+}(x)\mu -\mathrm{a}.\mathrm{e}.$$

and consequently

$$\int {\lambda }^{+}\mathrm{d}\mu =\int \underset{n\to \infty }{lim}\frac{1}{n}log\parallel \mathrm{D}{T}^n{(x)}^{\wedge }\parallel \mathrm{d}\mu (x).$$

Applying the theorem of dominated convergence then yields the result. □

Lemma 3.

Let $T:M\to M$ be a $C^2$-diffeomorphism on a compact Riemannian manifold M such that $h_{\mathrm{top}}(T)=h_{\mathrm{res}}(T)$. Then, if T has an entropy-maximizing measure ${\mu }_{*}$, it follows that:

$$h_{{\mu }_{*}}(T)=\int {\lambda }^{+}\mathrm{d}{\mu }_{*}.$$

Proof. 

Assume to the contrary that $h_{{\mu }_{*}}(T)<\int {\lambda }^{+}\mathrm{d}{\mu }_{*}$ (using Ruelle’s inequality (5)). Then, Lemma 2 implies:

$$h_{\mathrm{top}}(T)=h_{{\mu }_{*}}(T)<\int {\lambda }^{+}\mathrm{d}{\mu }_{*}=\underset{n\to \infty }{lim}\frac{1}{n}\int log\parallel \mathrm{D}{T}^n{(x)}^{\wedge }\parallel \mathrm{d}{\mu }_{*}(x).$$

According to Theorem 4 and the subsequent observation, an application of Lemma 1 yields:

$$h_{\mathrm{res}}(T)=\underset{\mu \in {\mathcal{M}}_T}{sup}\underset{n\to \infty }{lim}\frac{1}{n}\int log\parallel \mathrm{D}{T}^n{(x)}^{\wedge }\parallel \mathrm{d}\mu (x).$$

Combining these observations gives $h_{\mathrm{top}}(T)<h_{\mathrm{res}}(T)$, in contradiction to our assumption. □

Now, we are in a position to state our main result.

Theorem 6.

Let $T:M\to M$ be a topologically mixing $C^2$-Anosov diffeomorphism on a compact Riemannian manifold M such that $h_{\mathrm{top}}(T)=h_{\mathrm{res}}(T)$. Then, the unique entropy-maximizing measure ${\mu }_{*}\in {\mathcal{M}}_T$ is an SRB measure. Moreover, the function:

$$\mu \mapsto \int {\lambda }^{+}\mathrm{d}\mu ,{\mathcal{M}}_T\to {\mathbb{R}}_{\ge 0}$$

is constant.

Proof. 

First note that the existence and uniqueness of an entropy-maximizing measure ${\mu }_{*}$ follows from [20], Theorem 20.3.7, Theorem 18.3.9, and Corollary 6.4.10. Here, the assumption that T is topologically mixing is crucial. By the preceding lemma combined with Theorem 3, we already know that ${\mu }_{*}$ has absolutely continuous conditional measures on unstable manifolds. Since an Anosov diffeomorphism has positive Lyapunov exponents everywhere (where they exist), attained in all directions of the unstable subspace $E_x^u$, it follows that ${\mu }_{*}$ is an SRB measure.

Now, let $\mu \in {\mathcal{M}}_T$ be chosen arbitrarily. Due to the invariance of $\mu$, we have:

$$\begin{array}{cc}\hfill {\int log|det\mathrm{D}T(x)}_{|E_x^u}|\mathrm{d}\mu (x)& =\int \frac{1}{n}\sum _{i=0}^{n-1}log|det\mathrm{D}T{(T^i(x))}_{|E_{T^i(x)}^u}|\mathrm{d}\mu (x)\hfill \\ & =\int \frac{1}{n}log|det\mathrm{D}{T}^n{(x)}_{|E_x^u}|\mathrm{d}\mu (x)\hfill \end{array}$$

for every $n\in \mathbb{N}$, implying:

$$\begin{array}{cc}\hfill \int {\lambda }^{+}\mathrm{d}\mu & =\int \underset{n\to \infty }{lim}\frac{1}{n}log|det\mathrm{D}{T}^n{(x)}_{|E_x^u}|\mathrm{d}\mu (x)\hfill \\ & =\underset{n\to \infty }{lim}\int \frac{1}{n}log|det\mathrm{D}{T}^n{(x)}_{|E_x^u}|\mathrm{d}\mu (x)=\int log|det\mathrm{D}T{(x)}_{|E_x^u}|\mathrm{d}\mu (x),\hfill \end{array}$$

where we use Kingman’s subadditive ergodic theorem, applied to the continuous additive cocycle $f_n(x):=log|det\mathrm{D}{T}^n{(x)}_{|E_x^u}|$ ($n\in {\mathbb{N}}_0$), and the theorem of dominated convergence. Observe that the function $J^{u}T(x):=log|det\mathrm{D}T{(x)}_{|E_x^u}|$ is continuous (using the fact that $x\mapsto E_x^u$ is continuous). Hence, we can consider the affine function:

$${\alpha }_{\mu }:\mathbb{R}\to \mathbb{R},{\alpha }_{\mu }(t):=P_{\mu }(T,-t{J}^{u}T)=h_{\mu }(T)-t\int {\lambda }^{+}\mathrm{d}\mu .$$

The variational principle (2) for pressure tells us that:

$$P_{\mathrm{top}}(-t{J}^{u}T)=\underset{\mu \in {\mathcal{M}}_T}{sup}{\alpha }_{\mu }(t),\forall t\in \mathbb{R}.$$

(7)

Hence, $t\mapsto P_{\mathrm{top}}(-t{J}^{u}T)$, as the supremum over affine functions, is a convex function.

Using that ${\mu }_{*}$ is the entropy-maximizing measure and Theorem 3, respectively, we obtain:

$${\alpha }_{{\mu }_{*}}(0)=h_{\mathrm{top}}(T)\mathrm{and}{\alpha }_{{\mu }_{*}}(1)=0.$$

On the other hand, also:

$$P_{\mathrm{top}}(-0·{\lambda }^{+})=h_{\mathrm{top}}(T)\mathrm{and}{P}_{\mathrm{top}}(-1·J^{u}T)=0.$$

The second identity here follows from the fact that $P_{\mathrm{top}}(-1·J^{u}T)={sup}_{\mu \in {\mathcal{M}}_T}(h_{\mu }(T)-\int {\lambda }^{+}\mathrm{d}\mu )$ and $h_{\mu }(T)\le \int {\lambda }^{+}\mathrm{d}\mu$ by Ruelle’s inequality (5). Hence, $P_{\mathrm{top}}(-1·J^{u}T)=h_{{\mu }_{*}}(T)-\int {\lambda }^{+}\mathrm{d}{\mu }_{*}=0$.

By convexity of $t\mapsto P_{\mathrm{top}}(-t{J}^{u}T)$ and (7), this implies:

$$P_{\mathrm{top}}(-t{J}^{u}T)={\alpha }_{{\mu }_{*}}(t),\forall t\in \mathbb{R}.$$

From (7), it now follows that all of the maps ${\alpha }_{\mu }$ have the same slope, i.e., $\int {\lambda }^{+}\mathrm{d}\mu$ is independent of $\mu$. □

The above theorem shows that the equality $h_{\mathrm{top}}(T)=h_{\mathrm{res}}(T)$ is a very restrictive condition. Indeed, this can be seen as follows. Any topologically mixing Anosov diffeomorphism has an abundance of periodic points. Indeed, the set of periodic points is dense in M; see [20], Corollary 6.4.19. If we consider a periodic point $p\in M$ of period $n_p\in \mathbb{N}$, we can consider the invariant measure ${\mu }_p$ given by:

$${\mu }_p:=\frac{1}{n_p}\sum _{i=0}^{n_p-1}{\delta }_{T^i(p)}$$

with ${\delta }_{(·)}$ being the Dirac measure at a point. The above theorem implies that, under $h_{\mathrm{top}}(T)=h_{\mathrm{res}}(T)$, the number:

$$\gamma (p):=\int {\lambda }^{+}\mathrm{d}{\mu }_p=\frac{1}{n_p}log\left|det\left(\mathrm{D}{T}^{n_p}{(p)}_{|E_p^u}:E_p^u\to E_p^u\right)\right|$$

is independent of the periodic point p chosen. On the other hand, we know that every sufficiently small $C^2$-perturbation of T yields another $C^2$-Anosov diffeomorphism, topologically conjugate to T, hence also topologically mixing. If this perturbation is only performed in a small vicinity of a fixed periodic orbit, it can easily change the number $\gamma (p)$, while not changing it for most of the other periodic orbits. As a consequence, the perturbed diffeomorphism $T_{\epsilon }$ cannot satisfy $h_{\mathrm{top}}(T_{\epsilon })=h_{\mathrm{res}}(T_{\epsilon })$.

The following corollary gives another characterization of Anosov diffeomorphisms with $h_{\mathrm{top}}=h_{\mathrm{res}}$ in a two-dimensional case.

Corollary 1.

Consider a $C^2$ area-preserving Anosov diffeomorphism $T:{\mathbb{T}}^2\to {\mathbb{T}}^2$ of the two-torus. Then, the equality $h_{\mathrm{top}}\left(T\right)=h_{\mathrm{res}}\left(T\right)$ is equivalent to the existence of a hyperbolic linear automorphism $T_A:{\mathbb{T}}^2\to {\mathbb{T}}^2$ and a $C^1$-diffeomorphism $h:{\mathbb{T}}^2\to {\mathbb{T}}^2$ such that $h^{-1}\circ T\circ h=T_A$.

Proof. 

It follows immediately from Theorem 6 in combination with [20], Corollary 20.4.4, that the identity $h_{\mathrm{top}}\left(T\right)=h_{\mathrm{res}}\left(T\right)$ implies the existence of a $C^1$-conjugacy, as asserted. The other direction is easy to see, using the definition of restoration entropy. If $h^{-1}\circ T\circ h=T_A$, then also $h^{-1}\circ T^n\circ h=T_A^n$ for all $n\in \mathbb{N}$. We use that a $C^1$-map on a compact manifold has a global Lipschitz constant. Let $L:=\mathrm{Lip}\left(h\right)$ and $L^{\prime }:=\mathrm{Lip}\left(h^{-1}\right)$ be Lipschitz constants of h and $h^{-1}$, respectively. Then:

$$T^n\left(B_{\epsilon }\left(x\right)\right)=h\circ T_A^n\circ h^{-1}\left(B_{\epsilon }\left(x\right)\right).$$

Observe that $h^{-1}\left(B_{\epsilon }\left(x\right)\right)\subset B_{L^{\prime }\epsilon }\left(h^{-1}\left(x\right)\right)$. Let $N\left(l\right)$ denote the minimal number of $\epsilon$-balls needed to cover an $l\epsilon$-ball in ${\mathbb{T}}^2$ for any $l>0$. Then, the minimal number of $\epsilon$-balls needed to cover $T_A^n{h}^{-1}\left(B_{\epsilon }\left(x\right)\right)$ is bounded from above by $N\left(L^{\prime }\right){sup}_{z\in {\mathbb{T}}^2}p(n,z,\epsilon ;T_A)$. This implies:

$$p(n,x,\epsilon ;T)\le N\left(L\right)N\left(L^{\prime }\right)\underset{z\in {\mathbb{T}}^2}{sup}p(n,z,\epsilon ;T_A).$$

Hence,

$$\underset{x\in {\mathbb{T}}^2}{sup}\frac{1}{n}logp(n,x,\epsilon ;T)\le \frac{1}{n}logN\left(L\right)N\left(L^{\prime }\right)+\underset{x\in {\mathbb{T}}^2}{sup}\frac{1}{n}logp(n,x,\epsilon ;T_A).$$

Taking the lim sup for $\epsilon \downarrow 0$ and subsequently the limit for $n\to \infty$, we obtain that $h_{\mathrm{res}}\left(T\right)\le h_{\mathrm{res}}\left(T_A\right)$. The other inequality can be proven analogously, so:

$$h_{\mathrm{res}}\left(T\right)=h_{\mathrm{res}}\left(T_A\right).$$

Since T and $T_A$ are topologically conjugate (the $C^1$-diffeomorphism h is a homeomorphism, in particular), they also have the same topological entropy:

$$h_{\mathrm{top}}\left(T\right)=h_{\mathrm{top}}\left(T_A\right).$$

To complete the proof, it now suffices to show that $h_{\mathrm{res}}\left(T_A\right)=h_{\mathrm{top}}\left(T_A\right)$. We can compute $h_{\mathrm{res}}\left(T_A\right)$ using Theorem 4. To this end, observe that A is a hyperbolic matrix. If $|{\lambda }_1|>1>|{\lambda }_2|$ are its eigenvalues, we obtain:

$$\underset{n\to \infty }{lim}\frac{1}{n}\sum _{i=1}^{2}max\{0,log{\alpha }_i(n,x)\}=log\left|{\lambda }_1\right|\forall x\in {\mathbb{T}}^2,$$

implying $h_{\mathrm{res}}\left(T_A\right)=log\left|{\lambda }_1\right|$. It is well known that this is also the value of the topological entropy $h_{\mathrm{top}}\left(T_A\right)$; see [20], Section 4. This also follows from the combination of the variational principle with Theorem 3. □

The following example demonstrates how restrictive the condition $h_{\mathrm{res}}(T)=h_{\mathrm{top}}(T)$ is by looking at small perturbations of Arnold’s Cat Map.

Example 1.

Arnold’s Cat Map is the hyperbolic linear two-torus automorphism $T_A:{\mathbb{T}}^2\to {\mathbb{T}}^2$ induced by the integer matrix:

$$A:=\left(\begin{array}{cc}2& 1\\ 1& 1\end{array}\right)$$

with determinant $detA=1$. Observe that the derivative $\mathrm{D}{T}_A(x)$ can be identified with A for each $x\in {\mathbb{T}}^2$. Since A is a hyperbolic matrix with eigenvalues:

$${\gamma }_1=\frac{3}{2}-\frac{1}{2}\sqrt{5}and{\gamma }_2=\frac{3}{2}+\frac{1}{2}\sqrt{5}$$

satisfying $|{\gamma }_2|>1>|{\gamma }_1|$, it follows that $T_A$ is a $C^{\infty }$ area-preserving Anosov diffeomorphism. Hence, Corollary 1 yields:

$$h_{\mathrm{top}}(T_A)=h_{\mathrm{res}}(T_A)=log|{\gamma }_2|.$$

Now, we consider a perturbation of the form:

$$T_A^{\epsilon }(x,y):=\left(2x+y+\epsilon sin(2\pi x),x+y\right)(\mathrm{mod}{\mathbb{Z}}^2),\epsilon >0$$

which is well defined as a torus map, since the sine function is $2\pi$-periodic. By the structural stability of Anosov diffeomorphisms, for a sufficiently small ε, this map is topologically conjugate to $T_A$, hence has the same topological entropy $log|{\gamma }_2|$. However, its restoration entropy is strictly greater. This can be seen by looking at the fixed point $(0,0)$ with the associated derivative:

$$D{T}_A^{\epsilon }(0,0)=\left(\begin{array}{cc}2+2\pi \epsilon & 1\\ 1& 1\end{array}\right).$$

The eigenvalues of this matrix can be computed as:

$${\lambda }_{\pm }=\frac{3}{2}+\pi \epsilon \pm \frac{1}{2}\sqrt{5+4\pi \epsilon (1+\pi \epsilon )}.$$

Since ${\lambda }_{+}>{\gamma }_2$, Theorem 4 yields $h_{\mathrm{res}}(T_A^{\epsilon })\ge log|{\lambda }_{+}|>h_{\mathrm{top}}(T_A^{\epsilon })$ for $\epsilon >0$ sufficiently small.

5. Conclusions

In this paper, we compared two notions of entropy for dynamical systems that have an operational meaning in the context of state estimation over digital channels: topological entropy and restoration entropy. Looking at Anosov diffeomorphisms (a paradigmatic class of chaotic dynamical systems), our main result demonstrates that the equality of these two quantities implies a great amount of uniformity in the given system. For area-preserving Anosov diffeomorphisms on the two-torus, this uniformity can be expressed in terms of the existence of a $C^1$-conjugacy to a linear system. Hence, we can conclude that for most dynamical systems, the strict inequality $h_{\mathrm{top}}<h_{\mathrm{res}}$ holds. The operational meaning of this inequality is that for regular observability, as defined in Section 3, a strictly larger channel capacity is necessary than for observability.