ON THE TIME-COMPLEXITY OF WORST-CASE SYSTEM-IDENTIFICATION

In this paper we treat a general worst-case system identification prob lem. This problem is worst-case with respect to both noise and system modeling uncertainty. We consider this problem under various a priori information structures. We determine bounds on the minimum duration id entification experiment that must be run to identify the plant to with in a specified guaranteed worst-case error bound. Our results are algo rithm independent. We show that this minimum duration is prohibitively long. Based on our results, we suggest that worst-case (with respect to noise) system identification requires unrealistic amounts of experi mental data.