The Cost of Complexity in System Identification: Frequency Function Estimation of Finite Impulse Response Systems

In this paper, we consider full order modeling, i.e., when the true system belongs to the model set. We investigate the minimum amount of input energy required to estimate a given linear system with a full order model within a prescribed degree of accuracy γ, as a function of the model complexity. This quantity we define to be the “cost of complexity.” The degree of accuracy is measured by the inverse of the maximum variance of the discrete-time frequency function estimator over a given frequency range [-ω_B,ω_B]. It is commonly believed that the cost increases as the model complexity increases. However, the amount of information that is to be extracted from the system also influences the cost. The objective of this paper is to quantify these dependencies for systems described by finite-impulse response models. It is shown that, asymptotically in the model order n and sample size, the cost is well approximated by γσ_o²nω_B/π where σ_o² is the noise variance. This expression can be used as a simple rule of thumb for assessing trade-offs that have to be made in a system identification project where full order models are used. For example, for given experiment duration, excitation level and desired accuracy, one can assess how the achievable frequency range depends on the required model order. This type of consideration is useful when formally planning experiments. In addition, we establish several properties of the cost of complexity. We find, for example, that if ω_B is very close (but not necessarily equal) to π, the optimal input satisfies the model quality constraint for all frequencies.