THE SAMPLE COMPLEXITY OF WORST-CASE IDENTIFICATION OF FIR LINEAR-SYSTEMS

We consider the problem of identification of linear systems in the presence of measurement noise which is unknown but bounded in magnitude by some delta > 0. We focus on the case of linear systems with a finite impulse response. 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 2delta, if a sufficiently long identification experiment is performed. We establish that, for any K greater-than-or-equal-to 1, the minimal length of an identification experiment that is guaranteed to lead to a diameter bounded by 2Kdelta behaves like 2Nf(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. While the framework is entirely deterministic, our results are proved using probabilistic tools.