Alessandro CHIUSO
 
Date of final exam: 29/02/2000

E-mail: chiuso@math.kth.se

Tutor: Prof.  G. Picci, Università di Padova

  ___________________________________________________________________________________________________________


Geometric methods for subspace identification
  ___________________________________________________________________________________________________________

Advisor:

Prof.  G. Picci, Università di Padova

Summary of the thesis

In this thesis we will discuss geometric ``subspace methods'' for identification of linear, time-invariant, finite dimensional systems in state-space form.
The classical approach to system identification is based on optimization methods, where the system parameters are obtained from minimization of a suitable cost function. These methods often require iterative optimization procedures. The choice of canonical parametrizations represent a bottleneck in passing from SISO to MIMO identification.
Geometric, or realization-based, methods rely on the ideas of stochastic realization theory, which have been developed, mainly for time series, by many authors, for instance Akaike, Faurre, Lindquist and Picci, Picci, Ruckebusch.
Subspace methods, roughly speaking, translate the constructions of stochastic realization theory into procedures for model building which work on measured data. They owe the name ``subspace'' to the fact that the basic objects which are constructed are subspaces generated by the data, and geometric operations such as orthogonal and oblique projections are all what is needed to compute estimates of the parameters.
The appealing features of subspace methods may be enumerated as follows:

  1. there is no need for canonical parametrizations;
  2. no iterative nonlinear optimization is required;
  3. only simple but numerically robust tools of numerical linear algebra such as QR, SVD, QSVD, are used;
  4. since they rely on the theoretical background of stochastic realization theory a much deeper understanding of the involved procedures is possible.
Even though subspace methods have been around for a while, there are a number of questions which are still open.
  1. First, stochastic realization theory with exogenous inputs has not been fully developed.
  2. For systems with exogenous inputs there are no known procedures for constructing a basis in the state space, to be precise in a finite time oblique Markovian splitting subspace, directly from finite-time input output data. With directly we mean only with geometric operations which do not involve preliminary estimation of some system parameters. While the algorithm of van Overschee and De Moor for time series follows exactly the ideal steps suggested by stochastic realization theory, this has not been possible so far in identification with exogenous inputs. In different algorithms existing in the literature ad hoc tricks are used or an approximate version of the state is involved. This is the reason why the state-of-the-art may be considered satisfactory for time-series identification but not for systems with exogenous inputs.
  3. The characterization of the accuracy of the estimates seems still to be a partially open problem. Steps toward solving this problem have been made in the literature in the last few years where results on asymptotic normality of the estimates are obtained and procedures to compute asymptotic variance have been suggested. Others have pursued a different approach, studying uncertainty via Bootstrap methods.
  4. Related to the previous point is the question of numerical conditioning of subspace algorithm. It turns out that subspace algorithms with exogenous input may be very badly conditioned.
  5. As it is well known in the identification community, the choice of the input is crucial in the outcome of an identification experiment. Therefore, it is important to study the performance of algorithms as a ``function'' of the input characteristic. In particular there should be rules for the construction of ``probing inputs'' for the validation of identification algorithms. With ``probing inputs'' we mean inputs which are tailored in order to reveal the main limitations of the algorithms.
  6. Subspace identification in the presence of feedback from the ``output'' to the ``input'' has been addressed by some authors, but seems to be far from being completely understood.
The main contributions of the thesis are as follows.
  1. Geometric stochastic realization theory for systems with exogenous inputs is studied in some detail. Some results present in the literature are extended and some geometric insight is gained. Also some results on the geometric properties of modeling in the presence of feedback are illustrated.
  2. An analysis of numerical conditioning of the N4SID algorithm is provided showing that it may turn out to be rather ill-conditioned in some situations.
  3. Insight and some design rules are provided for constructing probing inputs for the validation of subspace identification algorithms.
  4. An analysis of the finite sample effects on the determination of the observability matrix is performed. A comparison of the accuracy between different procedures (corresponding to different choices of weighting matrices) is provided.
  5. The orthogonal decomposition algorithm of Picci and Katayama is improved and implemented. Simulation results and comparison with the N4SID algorithm are discussed.
  6. A ``subspace'' algorithm for identification in the presence of feedback is proposed and compared with a subspace-based joint input-output approach.

    _______________________________________

OTHER THEMES DEVELOPED

Estimation problems in Computer Vision

Supervisor: Prof. G. Picci, Università di Padova, Prof. S. Soatto, Washington University St. Louis

Computer Vision has gained in the last few years a remarkable attention. Two main motivations have contributed to this fact: from one side the great interest in applications and from the other the wealth of theoretical issues related.
In fact many ``Computer Vision'' problems are ``hard'' and mathematically challenging.
If we restrict our attention to the SFM (``Structure from Motion'') problem, we are faced with estimation problems on differentiable manifolds, in particular Lie Groups.
Various aspects have been studied and investigated.

  1. Tracking of point features as estimation on the unit sphere: tracking of point feature in Computer Vision is formulated as an destimation problem on the unit sphere (see Picci). An information theoretic criterion is used to obtain an approximate non-linear filter for a class of diffusions living on the unit sphere.
  2. Optimal SFM: the (nonlinear) cost function associated to the SFM problem from optical flow has been studied, provably convergent algorithms have been proposed, statistical properties of the estimate are studied and interpretation of local minima as well-know visual illusions such as bas-relief ambiguity and rubbery motion is provided.
  3. EKF based motion estimation: the problem of estimating structure from motion (monocular vision) can be formulated as state estimation of a certain (nonlinear) model. An approach which has been pursued in the literature in the last few years is based on the costruction of an EKF-based observer to obtain estimates of structure and motion. Further improvements have been obtained to deal with occlusions. The stability properties of the proposed observer are also under investigation.
  4. Monte Carlo filtering on Lie Groups. Obtaining finite dimensional filters (even approximated) on differentiable manifolds is a extremely difficult problem. There are results of non-exixtence of finite dimensional optimal solution which cover most of interesting situation. For this reason we are studying the possibility of using Monte Carlo methods for obtaining finite dimensional filters. These methods have recently gained a remarkable attention, especially in the statistical community.

  _______________________________________