Complexity of identification of linear systems with rational transfer functions (Q1276392)

The main objective of the paper is to study the complexity of the identification of the impulse response \(h\) of a linear time-invariant system by measuring the system's response to a carefully chosen input signal \(n\). In particular, the authors consider the complexity of word-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 a 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), it is shown that the complexity is \(O(n^2)\) for the \(H^\infty\) norm, \(O(n)\) for the \(l^2\) norm, and exponential in \(n\) for the \(l^1\) norm, for each \(\delta\) and \(\tau\). It is also shown that these bounds are tight. For the continuous-time case it is shown that the input signals may be compactly supported step functions with equally spaced nodes. It is shown, however that the internodal spacing must approach \(0\) as \(n\) increases.