The sample complexity of worst-case identification of FIR linear systems

Abstract

We consider the problem of identification of linear systems in the presence of measurement noise which is unknown but bounded in magnitude by some /spl delta/>0. We focus on the case of linear systems with a finite impulse response (FIR). It is known that the optimal identification error is related (within a factor of 2) to the diameter of a so-called uncertainty set and that the latter diameter is upper-bounded by 2/spl delta/, if a sufficiently long identification experiment is performed. If the identification error is measured with respect to the l/sub 1/ norm, we establish that, for any K/spl ges/1, the minimal length of an identification experiment that is guaranteed to lead to a diameter bounded by 2K/spl delta/ behaves like 2/sup Nf(1/K)/, when N is large, where N is the length of the impulse response and f is a positive function known in closed form. We contrast this with identification in H/sub /spl infin//, where an experiment of length O(N/sup 3/) suffices. While the framework is entirely deterministic, our results are proved using probabilistic tools.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>