Subspace Identification Algorithms and Stochastic Realization
by Jan H. van Schuppen
Feedback control is used in engineering systems to guarantee stability and to optimize performance. Control design is based on a model of an engineering system in the form of a dynamic system. The determination of a dynamic system from data is based on system identification and on realization theory. Results of realization theory form also the theoretical basis of control theory. Research on realization and system identification is carried out at the ERCIM Institutes: CNR.ISB, CWI, INRIA-IRISA, INRIA-Sophia-Antipolis, SICS-KTH and SZTAKI.
Kalman filters are used for prediction of, eg, water levels, economic goods, and air polution concentrations. Controllers for linear systems are used for control of, eg, electric motors, air planes, and of chemical processes. The design of Kalman filters and of linear controllers depends on the availability of a dynamic system for the dynamic phenomenon concerned. In system identification algorithms are derived and studied to determine from a time series a dynamic system. System identification algorithms for single-input-single-output linear systems have been available in the System Identification Toolbox of MATLAB for quite a while. However, for multi-input-multi-output linear systems such algorithms were not available until recently. The most effective algorithms now available are based on research initiated by R.E. Kalman in the 1960’s and the 1970’s.
The prediction algorithm that is now known as the Kalman filter was published in 1960. It provides predictions of a stochastic process described by a Gaussian system, a linear system driven by a Gaussian distributed sequence of independent random variables. After its initial success, Kalman proposed in 1964 a fundamental study of representations of stochastic systems. Stochastic realization theory for Gaussian systems was developed mainly by P. Faurre, G. Ruckebusch, A. Lindquist, and G. Picci in the period 1967-1985. H. Akaike, stimulated by Kalman, and inspired by stochastic realization theory, has formulated system identification algorithms for Gaussian systems during the 1970’s. W. Larimore in R.K. Mehra’s company Scientific Systems Inc., further developed the system identification algorithm, which became known as the `subspace identification algorithm’ because of the interpretation provided in terms of stochastic realization theory. B. de Moor and P. van Overschee improved the numerical properties of the subspace identification algorithms by the use of singular-value decomposition during the 1990’s and developed generalizations. Since then several variants of the subspace identification algorithm have been published, for example by A. Lindquist and G. Picci. In hindsight the research process seems to have been excessively long.
Consider a finite time series. From the data an estimate is formed of its covariance function. The time series is partitioned into a finite future and a finite past series. A canonical variable decomposition is then applied to these series. The relation between the future and the past series is then approximated, the low order approximant only contains the significant canonical variables. The resulting state at anytime is then obtained as a linear function of the finite past series. Finally a regression operation of a future state and the output on a past state is used to compute the matrices of a Gaussian system. The output of this system is the approximant of the considered time series. Variants of the algorithm differ in the choice of basis for the space generated by the time series and in the approximation step. Numericallly reliable algorithms are based on the singular value decomposition.
The subspace identification algorithm for multi-input-multi-output Gaussian systems is now available in the MATLAB Toolbox System Identification. This computer program package is available in a large number of companies, agencies, and universities. Students in control and signal processing are trained in its use. The algorithms are effective and rather robust. There is a small difference between the approximant of a subspace identification algorithm and that of a maximum likelihoud algorithm and an explanation for this is still subject of study.
The view that stochastic realization theory is useful for system identification, is now well established. This has stimulated further research on stochastic realization theory for other classes of stochastic systems. Stochastic realization of finite stochastic systems, also called hidden Markov models, has been carried out but the problem is far from satisfactorily solved. Stochastic realization in the abstract setting of s-algebras has also been considered. System identification of stochastic systems will lead to further research in stochastic realization theory.
The effectiveness of control theory is mainly due to the availability of realistic models of dynamic systems for the phenonema concerned. System identification algorithms are the main tool to construct such dynamic systems. The effectiveness of the currently available algorithms for system identification of multi-input-multi-output Gaussian systems is amazing. These algorithms are based on stochastic realization theory for Gaussian systems and on realization theory for finite-dimensional linear systems. The development of these theories was stimulated by R.E. Kalman. The results of realization theory and the application of subspace identification algorithms form an example of what has been called the ‘unreasonable effectiveness’ of mathematics.
Please contact:
Jan H. van Schuppen - CWI
Tel: +31 20 592 4085
E-mail: J.H.van.Schuppen@cwi.nl