Complexity issues in synchronisation

Abstract

In this paper, we look at synchronization over a finite window of data from a computational complexity point of view. The setting is purely in discrete time. It is shown that for polynomial systems the computational complexity of a readily available global Newton algorithm adapted to identify the finite trajectory of the dynamical system's state over the observation window scales in a polynomial manner in the dimension of the system state and the degree of the polynomials required to describe the models. Moreover, this algorithm has good robustness properties with respect to measurement errors and model errors. Simulation results are included.