On the sample-complexity of \({\mathcal H}_\infty\) identification (Q2730989)

The authors derive the sample complexity for discrete-time linear time-invariant stable systems in which the measured output, \(y\), and the input, \(u\), are related by the equation: NEWLINE\[NEWLINEy(t)=Tu(t)+w(t),\quad t=0,1,\dots,n,\quad T\in\mathcal J NEWLINE\]NEWLINE where, \(\mathcal J\), as alluded to before is a complex a priori known subset of \(\mathcal T\) which contains the real system; \(w\) is a filtered stable linear white Gaussian noise process uncorrelated from the input, given by NEWLINE\[NEWLINEw=Hv,\quad v\in N(0,\sigma),\quad \|H\|_1\leqslant\eta.NEWLINE\]NEWLINE The problem set-up is as follows: the \(\mathcal H_\infty\) norm distance between the unknown real system and a known finitely parametrized family of systems is bounded by a known real number. One can associate, for every feasible real system, a model in the finitely parametrized family that minimizes the \(\mathcal H_\infty\) distance. The question arises as to how long a data record is required to identify such a model from noisy input-output data. It is shown that for systems described with \(\ell_1\), \(\mathcal H_2\) and other \(\ell_p\) topologies, algorithms could be devised so that the estimates converged to optimal with polynomial sample complexity. In the backdrop of these results the infinite sample complexity for the \(\mathcal H_\infty\) case appears particularly surprising. On the one hand the space \(\mathbb R\mathcal H_\infty\) is contained in the space \(\ell_1\) and on the other \(\mathcal H^2\) space has a weaker topology than \(\mathcal H_\infty\). However, in spite of these superficial similarities it turns out that \(\mathcal H_\infty\) has infinite sample complexity. This, in a sense, implies that the estimate of the distance between an element in the \(\mathbb R\mathcal H_\infty\) space and the finitely parametrized set of models is too coarse if given in terms of the \(H_\infty\) norm. Consequently, the importance of choosing the right metric for carrying out system identification cannot be understated.