Complexity of identification of input-output systems (Q1900360)

The paper deals with the complexity of deterministic identification of abstract classes of input-output systems, based on a finite number of experiments. A measure of complexity (difficulty) of the identification problem is the minimum number of experiments (tests) needed to obtain an exact or approximate system model (this is called the size of the identification). Some bounds on the identification size for several classes of systems are derived. In particular, an upper bound on the size for the class of Lipschitz systems with totally bounded input space is given, it is based on the metric entropy of this space (i.e. the minimum number of points in a net of the space of inputs). Also, a lower bound on the size is derived for interpolative identification of a compact class of systems with compact input space and finite-dimensional output space; it uses the metric entropy and the \(n\)-width of the class of unknown systems. Finally, entropy and capacity bounds for several classes of Lipschitz systems are presented. Some illustrative examples are given.