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 δ>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δ, if a sufficiently long identification experiment is performed. If the identification error is measured with respect to the l₁ norm, we establish that, for any K⩾1, the minimal length of an identification experiment that is guaranteed to lead to a diameter bounded by 2Kδ behaves like 2^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_∞, where an experiment of length O(N³) suffices. While the framework is entirely deterministic, our results are proved using probabilistic tools