Information-Based Complexity and Nonparametric Worst-Case System Identification

In this paper we review recent results on nonparametric approaches to identification of linear dynamic systems, under nonprobabilistic assumptions on measurement uncertainties. Two main categories of problems are considered in the paper: H_∞ and l₁ settings. The H_∞ setting assumes that the true system is linear time-invariant and the available information is represented by samples of the frequency response of the system, corrupted by an l_∞-norm bounded noise. The aim is to estimate a proper, stable finite-dimensional model. The estimation error is quantified according to an H_∞ norm, measuring the "distance" of the estimated model from the worst-case system in the class of allowable systems, for the worst-case realization of the measurement error. In the l₁ setting, the aim is to identify the samples of the impulse response of an unknown linear time-invariant system. The available information is given by input/output measurements corrupted by l_∞-bounded noise and the estimation error is measured according to an l₁ norm, for the worst case with respect to allowable systems and noise. In this paper, the main results available in the literature for both settings are reviewed, with particular attention to (a) evaluation of the diameter of information under various experimental conditions, (b) convergence to zero of the diameter of information (i.e., existence of robustly convergent identification procedures), and (c) computation of optimal and almost-optimal algorithms. Some results are also reported for the l_∞ setting, similar to the l₁ setting, with the exception of the estimation error, which is measured by an l_∞ norm.