Premium
On the sample‐complexity of ℋ︁ ∞ identification
Author(s) -
Venkatesh S. R.,
Dahleh M. A.
Publication year - 2001
Publication title -
international journal of robust and nonlinear control
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.361
H-Index - 106
eISSN - 1099-1239
pISSN - 1049-8923
DOI - 10.1002/rnc.623
Subject(s) - parameterized complexity , sample complexity , bounded function , network topology , time complexity , mathematics , computational topology , context (archaeology) , norm (philosophy) , computational complexity theory , invariant (physics) , discrete mathematics , topology (electrical circuits) , computer science , algorithm , combinatorics , artificial intelligence , mathematical analysis , paleontology , scalar field , political science , law , mathematical physics , biology , operating system
In this paper we derive the sample complexity for discrete time linear time‐invariant stable systems described in the ℋ ∞ topology. The problem set‐up is as follows: the ℋ ∞ norm distance between the unknown real system and a known finitely parameterized family of systems is bounded by a known real number. We can associate, for every feasible real system, a model in the finitely parameterized family that minimizes the ℋ ∞ distance. The question now arises as to how long a data record is required to identify such a model from noisy input–output data. This question has been addressed in the context of l 1 , ℋ 2 and several other topologies, and it has been shown that the sample‐complexity is polynomial. Nevertheless, it turns out that for the ℋ ∞ topology the sample‐complexity in the worst case can be infinite. Copyright © 2001 John Wiley & Sons, Ltd.