Narrow Results

Prediction, smoothing, filtering and synchronization or observer design given finitely many measurements and a given (possibly nonlinear) dynamical map are discussed from a computational complexity point of view. All these problems are particular instances of finding a zero of an appropriately defined function. The recognition of this fact enables one to approach these questions from a computational complexity point of view. For polynomial maps the computational complexity of a global Newton algorithm adapted to identify the finite trajectory of the dynamical system's state over the desired window scales in a polynomial manner with the condition number (an invariant for the problem at hand) and the degree of the polynomials required to describe the models. The computational complexity analysis allows one to identify the most efficient manner to approach synchronization (prediction, smoothing, filtering) problems. Moreover differences between adaptive and nonadaptive formulations are revealed based on the condition number of the associated zero finding problem. The advocated formulation, with the associated global Newton algorithm has good robustness properties with respect to measurement errors and model errors for both adaptive and nonadaptive problems. These aspects are illustrated through a simulation study based around the Hénon map.

We develop an iterative descent algorithm for minimizing the pointwise maximum of a finite collection of convex thrice-differentiable functions;

To recompute x_R after each update of R, we propose to use a global newton procedure of [3]. We show that, under a certain nondegeneracy assumption on F and assuming infinite precision arithmetic, the number of newton steps required to recompute x_R is at most a constant plus log₂log₂(1/∈).