CDC 2016 pre-workshop on realization theory and its role in system identification

Goal of the workshop

The goal of this workshop is twofold. First, it aims at acquainting the audience with the role of realization theory in system identification of linear systems. This is done by presenting a number of results, both classical and recent, on realization theory of linear systems and its applications to system identification. Second, it aims at presenting realization theory and its applications for other classes of systems: finite-state stochastic systems, hybrid systems, LPV systems and some classes of non-linear systems. The workshop is thus intended to be tutorial in nature: its goal is to present the basic ideas in a clear and accessible fashion, and to give a glimpse of various application domains.

The motivation for the workshop is the following. Realization theory plays an important role in system identification, but this role is a technical one and for this reason it is not always visible. As a result, young researchers are often not very familiar with the topic. In turn, this makes it difficult for them to use realization theory to analyze system identification methods or to come up with new one, based on realization theory. In addition, when attempts are made to develop system identification methods for systems which are not linear, for example LPV or hybrid systems, many of the standard facts, which are taken for granted for linear systems, need not remain true. Hence, in order to be able to decide which assumptions are meaningful and to be able to come up with a theoretical analysis of system identification algorithms, realization theory for these new classes of systems is needed. The workshop addresses both issues, by providing a tutorial overview of classical linear realization theory and by giving an overview of realization theory for other system classes.

Workshop length

full-day.

Target audience

The workshop targets researchers in control theory, especially in system identification, who would like to get acquainted with realization theory and its application to system identification. The workshop could especially be useful for young researchers, who might not have been exposed to the topic before.


Prerequisites

The workshop assumes no more than the standard knowledge of classical linear control theory. However, a certain level of mathematical maturity and some degree of familiarity with system identification is an advantage.

Contents of the workshop

The topic of the workshop is realization theory of various classes of systems and its role in system identification.

The workshop will start by a brief review of basics of realization theory of linear systems, both in deterministic and stochastic settings. Most of the members of the audience are likely to be at least partially familiar with these results. This short introduction will be followed by more specialized lectures.

The lecture by Anders Lindquist will deal with stochastic partial realization theory and its relationship with subspace identification methods. Subspace identification methods are usually based on partial realization theory, however, they often ignore the condition of positive realness imposed by the stochastic realization problem. Instead, they treat the problem as a deterministic partial realization problem. As a result, these algorithms may perform very poorly for certain systems. The talk will explain this problem in detail and discuss examples when subspace identification fail due to this problem. This talk demonstrates the importance of realization theory for subspace identification algorithms.

The lecture by Bernard Hanzon will present the application of realization theory to parametric system identification. It will present the smooth Riemannian manifold structure of equivalence classes of minimal linear systems, their local charts and their relationship with local canonical form, and the relationship between parametric system identification and this manifold structure. Parameterization and parametric identification of lossless systems will also be discussed. The lecture will conclude by presenting future research directions and the relationship with related disciplines such as machine learning and data analytics. This talk demonstrates the importance of realization theory for parametric identification of state-space representations.

The lecture of Alessandro Chiuso will deal with application of realization theory to system identification methods based on regularization. Regularization is a standard approach in machine learning. The talk will explain how to combine realization theory in general, and the concept of Hankel matrices in particular, with regularization, in order to derive new identification algorithms for MIMO systems. The latter algorithms turn out to be competitive with the existing algorithms, and sometimes they are better than the state-of-the-art. This talk demonstrates the relevance of realization theory for new developments in system identification.

The lecture by Jan H. van Schuppen provides an overview of realization theory of finite-valued and countably valued stochastic systems, i.e. stochastic systems the state and output process of which take values in a finite (respectively countable) set. The talk will cover both the discrete-time and the continuous-time case. Such stochastic systems include finite-state hidden Markov models and counting processes, and they are widely used in information theory, communication theory, signal processing, queueing theory, and control engineering. Such models are also useful for approximating highly complex non-linear systems, which are difficult to handle with other techniques.

Mihaly Petreczky will present an overview of realization theory of linear switched, bilinear and LPV systems. The relevance of these results for system identification will also be discussed. The rationale for grouping these topics together is that realization theory of bilinear, switched and LPV systems are closely related and use essentially the same mathematical tools.

Finally, the talk of Jana Nemcova will provide an overview of realization theory of nonlinear systems described by polynomial/rational equations. These systems appear naturally in a number of domains, for example, they are standard tools for modelling biochemical reaction networks. While this theory is not yet complete, it is a subject of intensive research, and the existing results are already useful for system identification of these systems, in particular, for identifiability analysis.


Tentative schedule of the workshop

  • 09:00 - 10:30 Realization theory of linear systems: a brief review of the classical results (Mihaly Petreczky).
  • 10:30 - 11:00 Partial realization theory and subspace identification for time series (Anders Lindquist).
  • 11:00 - 11:30 Break.
  • 11:30 - 12:30 Realization theory meets Regularisation: an overview of some recent results (Alessandro Chiuso).
  • 12:30 - 13:30 Lunch break.

  • 13:30 - 15:00 Geometric aspects of system identification (Bernard Hanzon).
  • 15:00 - 15:15 Break.
  • 15:15 - 16:15 Stochastic Realization of Finite-Valued and of Countably-Valued Stochastic Processes (Jan H. van Schuppen).
  • 16:15 - 16:30 Break.
  • 16:30 - 17:30 Realization theory of switched linear, bilinear and LPV systems (Mihaly Petreczky).
  • 17:30 - 18:00 Realization theory of rational and polynomial systems (Jana Nemcova).


Abstract of the talks

  • Title: Realization theory of linear systems: review of the classical results.

    Speaker: Mihaly Petreczky (Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL), UMR CNRS 9189)

    Abstract: The goal of this talk is to review some basic notions of realization theory of time-invariant linear (LTI) systems, thus preparing the ground for the other lectures. We briefly review such topics as minimality of LTI systems, Kalman decomposition, the notion of Markov parameters and Hankel-matrices, Kalman-Ho realization algorithm. We will also briefly mention some core notions of stochastic realization theory, such as the notions of weak and strong realizations, deterministic realizations of covariance sequences, matrix Riccati equations and forward innovation representations.

  • Title: Partial realization theory and subspace identification for time series.

    Speaker: Anders Lindquist (Shanghai Jiao Tong University, Royal Institute of Technology (KTH), Stockholm)

    Abstract: This is a tutorial talk reviewing the connection between subspace identification for time series and partial realization theory. Most subspace identification procedures are directly or, more often, indirectly based on partial realization theory. The appropriate realization problem for system identification is the rational covariance extension problem. However, most basic subspace algorithms actually solves a deterministic partial realization problem where the basic condition of positive realness has been removed. This may lead to failure for theoretical rather than numerical reasons. In fact, a sequence of estimated covariance lags has both an algebraic and a positive degree, and failure may occur when the degrees do not coincide. Thus we need the condition that the algebraic and the positive degrees are the same. One can generate data for which this degree condition does not hold and for which several subspace identification algorithms exhibit massive failure.

  • Title: Realization theory meets Regularisation: an overview of some recent results

    Speaker: Alessandro Chiuso (Department of Information Engineering - University of Padova), joint work with Giulia Prando.

    Abstract: In this talk we shall discuss some recent developments in the area of system identification where regularisation ideas have been used, in different ways, in conjunction with realisation theory. In particular the low rank structure of Hankel matrices has been exploited, thus allowing to apply, and actually extend, recent work on low rank matrix estimation. This has led to new algorithms for MIMO system identification which are competitive, and sometimes outperform, state-of-the-art identification algorithms.

  • Title: Geometric aspects of System Identification.

    Speaker: Bernard Hanzon (University College Cork), joint work with Martine Olivi and Ralf Peeters.

    Abstract: In this presentation we want to give an overview of the geometric approach to system identification and related problems such as model reduction. We want to use Maximum likelihood estimation and $H_2$ ("least squares") model reduction as leading examples. The starting point is the result (due to JMC Clark) that families of linear time-invariant systems of fixed finite order are differentiable manifolds. It can be shown that in most cases they cannot be described by a unique Euclidean chart of the dimension of the manifold. Therefore it is natural to use local canonical forms and corresponding local coordinate charts. In case one employs search algorithms such as gradient algorithms to find local optima of the criterion function (such as the likelihood function) one needs to be able to change between coordinate charts. In order to keep consistency between the gradient steps taken in the various charts (ideally the steps taken are wholly coordinate free) one can use Riemannian gradients. These are based on the concept of a Riemannian metric on the manifold. This will be explained and some examples will be treated, including the illustrative example of the case of stable SISO systems of order one (viewed as submanifold of the space $H_2$), in which the intrinsic geodesic metric is fully understood. The example also shows some intrinsic difficulties as it turns out there is no Euclidean parametrization that can describe the neighbourhood of the origin. In answer to the perceived problems one can use the idea of Separable Least Squares and Separable System Idenfication, in which one splits the optimization problem involved into a family of quadratic, or at least convex, problems and a "concentrated" optimization problem over the set of (stable) systems in input-normal form. Actually the optimization can be viewed as optimization over a associated family of lossless systems. The geometry of that family is much better behaved. The family of lossless systems has interesting balanced (this concept will be explained) local canonical forms that can be parametrized using only orthogonal matrices and transformations. These are well-behaved numerically and have a lot of mathematical structure that can be exploited for various purposes. A very interesting set of local canonical forms is obtained by imposing a so-called subdiagonal pivot structure on the matrices involved. This is a very flexible set of local canonical forms which allow easy decision rules to shift between charts. Also some remarks will be made about a much larger family of charts that could be used, and which are based on interpolation theory. They are especially useful in case one is interested in systems that satisfy certain interpolation conditions. If time permits some further applications will be mentioned as well as related recent theoretical developments. Also we plan to give some concluding remarks about how the theory may develop further given the recent advances and interest in related areas such as machine learning and data analytics.

  • Title: Stochastic Realization of Finite-Valued and of Countably-Valued Stochastic Processes

    Speaker: Jan H. van Schuppen (Delft University of Technology and Van Schuppen Control Research)

    Abstract The aim of the lecture is to present to the audience of the workshop a tutorial lecture on stochastic realization of finite-valued and of countably-valued stochastic processes.

    The motivation of the lecture is the use in control and in filtering of stochastic control systems with finite-valued and with countably-valued output processes. Such systems are known as finite stochastic systems, hidden Markov models, and counting process systems. Research areas in which such systems are used include: information theory, communication theory, signal processing, queueing theory, control engineering, etc. In addition, such systems are used as approximations of continuous-space stochastic systems. Such an approximation has the advantage that algorithms for filtering and for control of finite stochastic systems are available.

    The concept of a finite stochastic system with a finite-valued output process will be defined both for discrete-time and for continuous-time systems. The associated concept of a countable-valued stochastic system is defined in which the set of gamma probability distributions appears. It will be shown that all these stochastic systems have both a forward and a backward representation.

    The weak and the strong stochastic realization problems for finite-valued and for countably-valued processes will be formulated and embedded in a larger class of problems. The weak problem asks when considered an observed process for the existence of a stochastic realization as a finite system, for the minimality of a realization, and for the classification of all minimal stochastic realizations. The existence problem has been solved for finite-valued processes during the 1960's. It is formulated in terms of the probability distributions of the output process which have to belong to a polyhedral cone with a finite number of vertices.

    The minimality of stochastic realizations is not solved satisfactorily yet and the existing approaches will be discussed. For this the concepts of stochastic observability and of stochastic co-observability are formulated. It will be shown how to reduce a stochastic system to a stochastic realization of its output process which is both stochastically observable and stochastically co-observable. For the classification subproblem, the decomposition of positive matrices into a direct sum of irreducible positive matrices will be used followed by an investigation of the class of irreducible positive matrices.

    For finite stochastic control systems the concepts of stochastic controllability and of stochastic co-controllability will be defined and its characterizations are discussed.

    The weak stochastic realization problem for countable-output stochastic systems will be discussed separately towards the end of the lecture. This case can be related to that for finite-valued processes.

  • Title: Realization theory of switched linear systems, bilinear and LPV systems

    Speaker: Mihaly Petreczky (Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL), UMR CNRS 9189)

    Abstract: In this lecture we will present an overview of recent results on realization theory of linear switched, bilinear systems and of linear parameter-varying (LPV) systems. These three system classes are closely related: bilinear systems can be viewed as a subclass of LPV systems, if the scheduling parameter is viewed as an input, and linear switched systems can be viewed as LPV systems if the scheduling parameters take values in a finite set. We will present results on minimality, with reachability and observability, Hankel-matrices, realization algorithms and partial realization. We will explain the relationship with bilinear systems too. We will mention the consequences of these results for system identification of linear switched, bilinear and LPV systems

  • Title: Realization theory of rational and polynomial systems.

    Speaker: Jana Nemcova (University of chemistry and technology, Prague)

    Abstract: The talk will give an overview of realization theory of non-linear systems described by polynomial and rational equations. Such systems appear in a wide variety of different domains, for example, in models of biochemical reaction networks. Conditions for minimality in terms of reachability and observability will be presented, along with conditions for existence of a realization. Uniqueness modulo isomorphism of minimal realizations will also be discussed, together with the application of these results to identifiability analysis of rational/polynomial systems. Finally, if time permits, recent results on realization theory of the so-called Nash systems (non-linear systems defined by analytic semi-algebraic functions) will also be presented.



Organizer 

The organizer of this workshop Mihaly Petreczky. Mihaly Petreczky received the Ph.D. degree from Vrije Universiteit in Amsterdam, The Netherlands in 2006. In the past, he was a postdoc at Johns Hopkins University, USA (2006 - 2007), Eindhoven University of Technology, The Netherlands (2007-2009) and assistant professor at Maastricht University, The Netherlands (2009 - 2011) and at Ecole des Mines de Douai, France (2011 - 2015). He is currently a CNRS researcher at Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL), UMR CNRS 9189, France. His research interests include realization theory, system identification and model reduction of hybrid and LPV systems.


Comments