Complexity of identification of linear systems with rational transfer functions
type: Item
instance of: scholarly article
title: Complexity of identification of linear systems with rational transfer functions
zbMATH Open document ID: 0917.93013
DOI: 10.1007/BF02750393
author: K. Appert
published in: MCSS. Mathematics of Control, Signals, and Systems
publication date: 1999-08-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 93B30
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 93C05
zbMATH DE Number: 1246369
zbMATH Keywords: ARX models
zbMATH Keywords: sample complexity
zbMATH Keywords: complexity of identification
zbMATH Keywords: impulse response
zbMATH Keywords: fractional covers
reviewed by: Tzvetan Semerdjiev
MaRDI profile type: Publication
Wikidata QID: Q56319474
cites work: Q4885251
cites work: The sample complexity of worst-case identification of FIR linear systems
cites work: Relating \(H_{2}\) and \(H_{\infty}\) bounds for finite-dimensional systems
cites work: Robust identification in the disc algebra using rational wavelets and orthonormal basis functions
cites work: Q4859387
cites work: Fractional covers for convolution products
cites work: Sample complexity of worst-case \(H^\infty\)-identification
cites work: Robust identification and Galois sequences
cites work: Worst-case control-relevant identification
cites work: Information-based complexity and nonparamteric worst-case system identification
cites work: Q3994887
cites work: Worst-case identification in \(\ell_ 2\): Linear and nonlinear algorithms
cites work: Q4340908
cites work: On the time complexity of worst-case system identification
cites work: On approximation of stable linear dynamical systems using Laguerre and Kautz functions
full work available at URL: https://doi.org/10.1007/bf02750393
OpenAlex ID: W2106759140
DBLP publication ID: journals/mcss/HarrisonPW98
description: scientific article; zbMATH DE number 1246369