# Entropy and Minimal Data Rates for State Estimation and Model Detection

Title | Entropy and Minimal Data Rates for State Estimation and Model Detection |

Publication Type | Conference Paper |

Year of Publication | 2016 |

Authors | Liberzon, Daniel, Mitra, Sayan |

Conference Name | Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control |

Publisher | ACM |

Conference Location | New York, NY, USA |

ISBN Number | 978-1-4503-3955-1 |

Keywords | composability, CPS modeling, Estimation, Metrics, model detection, Monitoring, pubcrawl, quantization, Resiliency, simulation, topological entropy |

Abstract | We investigate the problem of constructing exponentially converging estimates of the state of a continuous-time system from state measurements transmitted via a limited-data-rate communication channel, so that only quantized and sampled measurements of continuous signals are available to the estimator. Following prior work on topological entropy of dynamical systems, we introduce a notion of estimation entropy which captures this data rate in terms of the number of system trajectories that approximate all other trajectories with desired accuracy. We also propose a novel alternative definition of estimation entropy which uses approximating functions that are not necessarily trajectories of the system. We show that the two entropy notions are actually equivalent. We establish an upper bound for the estimation entropy in terms of the sum of the system's Lipschitz constant and the desired convergence rate, multiplied by the system dimension. We propose an iterative procedure that uses quantized and sampled state measurements to generate state estimates that converge to the true state at the desired exponential rate. The average bit rate utilized by this procedure matches the derived upper bound on the estimation entropy. We also show that no other estimator (based on iterative quantized measurements) can perform the same estimation task with bit rates lower than the estimation entropy. Finally, we develop an application of the estimation procedure in determining, from the quantized state measurements, which of two competing models of a dynamical system is the true model. We show that under a mild assumption of exponential separation of the candidate models, detection is always possible in finite time. Our numerical experiments with randomly generated affine dynamical systems suggest that in practice the algorithm always works. |

URL | http://doi.acm.org/10.1145/2883817.2883820 |

DOI | 10.1145/2883817.2883820 |

Citation Key | liberzon_entropy_2016 |