Complexity of identification of linear systems with rational transfer functions

We study the complexity of worst-case time-domain identification of linear time-invariant systems using model sets consisting of degree-n rational models with poles in a fixed region of the complex plane. For specific noise level delta and tolerance levels tau, the number of required output samples and the total sampling time should be as small as possible. In discrete time, using known fractional covers for certain polynomial spaces (with the same norm), we show that the complexity is O(n(2)) for the H(infinity) norm, O(n) for the l(2) norm, and exponential in n for the l(1) norm, for each delta and tau. We also show that these bounds are tight. For the continuous-time case we prove analogous results, and show that,the input signals may be compactly supported step functions with equally spaced nodes. We show, however, that the internodal spacing must approach 0 as n increases.