Operational modal analysis from impulse response data can alternatively be viewed as an identification of a stable autonomous linear time-invariant system. For example, earthquake response data of civil engineering structures and impulsive excitation of bridges leads to this problem. Identification from a single experiment, however, does not yield a consistent estimator in the output error setting due to the exponential decay of the noise-free signal. Using data from multiple experiments, on the other hand, is not straightforward because of the need to match the initial conditions in the repeated experiments. Consequently, we consider the identification from arbitrary initial conditions and show that consistent estimation is possible in this case. The computational method proposed in the paper is based on analytic elimination of the initial conditions (nuisance parameter) and local optimization over the remaining (model) parameters. It is implemented in a ready to use software package, available from http://slra.github.io/software.html

Low-rank approximations play an important role in systems theory and signal processing. The problems of model reduction and system identification can be posed and solved as a low-rank approximation problem for structured matrices. On the other hand, signal source separation, nonlinear system identification, and multidimensional signal processing and data analysis can be approached with powerful methods of low-rank tensor factorizations. The proposed invited session is focused on theoretical and algorithmic aspects of matrix and tensor low-rank approximations, with applications in system theory and multidimensional signal processing.

We are focused on numerical methods for decomposing a multivariate polynomial as a sum of univariate polynomials in linear forms. The main tool is the recent result on correspondence between the Waring rank of a homogeneous polynomial and the rank of a partially known quasi-Hankel matrix constructed from the coefficients of the polynomial. Based on this correspondence, we show that the original decomposition problem can be reformulated as structured low-rank matrix completion (or as structured low-rank approximation in the case of approximate decomposition). We construct algorithms for the polynomial decomposition problem. In the case of bivariate polynomials, we provide an extension of the well-known Sylvester algorithm for binary forms.

This paper focuses on a state-space based approach for the identification of a rather general nonlinear block-structured model. The model has several Single-Input Single-Output (SISO) static polynomial nonlinearities connected to a Multiple-Input Multiple-Output (MIMO) dynamic part. The presented method is an extension and improvement of prior work, where at most two nonlinearities could be identified. The location of the nonlinearities or their relation to other parts of the model does not have to be known beforehand: the method is a black-box approach, in which no states, internal signals or structural properties need to be measured or known. The first step is to estimate a partly structured polynomial (nonlinear) state-space model from input-output measurements. Secondly, an algebraic approach is used to split the dynamics and the nonlinearities by decomposing the multivariate polynomial coefficients.

Linear time-invariant system identification is considered in the behavioral setting. Nonstandard features of the problem are specification of missing and exact variables and identification from multiple time series with different length. The problem is equivalent to mosaic Hankel structured low-rank approximation with element-wise weighted cost function. Zero/infinite weights are assigned to the missing/exact data points. The problem is in general nonconvex. A solution method based on local optimization is outlined and compared with alternative methods on simulation examples. In a stochastic setting, the problem corresponds to errors-in-variables identification. A modification of the generic problem considered is presented that is a deterministic equivalent to the classical ARMAX identification. The modification is also a mosaic Hankel structured low-rank approximation problem.

Keywords: system identification; behavioral approach; missing data; mosaic Hankel matrix; low-rank approximation

The paper presents initial results on a subspace method for exact identification of a linear time-invariant system from data with missing values. The identification problem with missing data is equivalent to a Hankel structured low-rank matrix completion problem. The novel idea is to search systematically and use effectively completely specified submatrices of the incomplete Hankel matrix constructed from the given data. Nontrivial kernels of the rank-deficient completely specified submatrices carry information about the to-be-identified system. Combining this information into a full model of the identified system is a greatest common divisor computation problem. The developed subspace method has linear computational complexity in the number of data points and is therefore an attractive alternative to more expensive methods based on the nuclear norm heuristic.

Keywords: subspace system identification, missing data, low-rank matrix completion, nuclear norm, realization.

Discovering the structures of latent variable models whose conditional independence structures are trees is an important yet challenging learning task. Existing approaches for this task often require the unknown number of hidden states as an input. In this paper, we propose a quartet based approach which is agnostic to this number. The key contribution is a novel rank characterization of the tensor associated with the marginal distribution of a quartet. This characterization allows us to design a nuclear norm based test for resolving quartet relations. We then use the quartet test as a subroutine in a divide-and-conquer algorithm for recovering the latent tree structure. We also derive the conditions under which the algorithm is consistent and its error probability decays exponentially with increasing sample size. We demonstrate that the proposed approach compares favorably to alternatives. In a real world stock dataset, it also discovers meaningful groupings of variables, and produces a model that fits the data better.

Keywords: latent tree graphical model, structure learning, quartet test, tensor, low rank, nuclear norm

We approach the problem of estimating the parameters of a latent tree graphical model from a hierarchical tensor decomposition point of view. In this new view, the marginal probability table of the observed variables is treated as a tensor, and we show that: (i) the latent variables induce low rank structures in various matricizations of the tensor; (ii) this collection of low rank matricizations induces a hierarchical low rank decomposition of the tensor. We further derive an optimization problem for estimating (alternative) parameters of a latent tree graphical model, allowing us to represent the marginal probability table of the observed variables in a compact and robust way. The optimization problem aims to find the best hierarchical low rank approximation of a tensor in Frobenius norm.

For correctly specified latent tree graphical models, we show that a global optimum of the optimization problem can be obtained via a recursive decomposition algorithm. This algorithm recovers previous spectral algorithms for hidden Markov models (Hsu et al., 2009; Foster et al., 2012) and latent tree graphical models (Parikh et al., 2011; Song et al., 2011) as special cases, elucidating the global objective these algorithms are optimizing. For misspecified latent tree graphical models, we derive a novel decomposition based on our framework, and provide approximation guarantee and computational complexity analysis. In both synthetic and real world data, this new estimator significantly improves over the state-of-the-art.

Keywords: parameter estimation, latent tree graphical model, hierarchical tensor decomposition, low rank

Errors-in-variables system identification can be posed and solved as a Hankel structured low-rank approximation problem. In this paper different estimates based on suboptimal low-rank approximations are considered. The estimates are shown to have almost the same efficiency and lead to the same minimum when supplied as an initial approximation to local optimization solver of the structured low-rank approximation problem. In this paper it is shown that increasing Hankel matrix window length improves suboptimal estimates for autonomous systems and does not improve them for systems with inputs.

An unorthodox programme for teaching systems and control is developed and tested at the School of Electronics and Computer Science of the University of Southampton. Motivation for the employed teaching methods is Moore's method and S. Papert's book “Mindstorms: children, computers, and powerful ideas”. The teaching is shifted from lecture instruction to independent work on computer based projects and physical models. Our experience shows that involvement with projects is more effective in stimulating curiosity in systems and control related concepts and in achieving understanding of these concepts. The programme consists of two parts: 1) analytical and computational exercises, using Matlab/Octave, and 2) laboratory exercises, using programmable Lego mindstorms models. Both activities cut across several disciplines - physics, mathematics, computer programming, as well as the subject of the programme - systems and control theory.

Many problems of system identification, model reduction and signal processing can be posed and solved as a structured low-rank approximation problem (SLRA). In this paper a reformulation of SLRA as minimization of a multivariate rational function is considered. Using two different parametrizations, we show that the problem reduces to optimization over a compact manifold or to a set of optimization problems over bounded domains of Euclidean space. We make a review of methods of polynomial algebra for global optimization of the rational cost function.

The question in the title is answered empirically by solving instances of three classical problems: fitting a straight line to data, fitting a real exponent to data, and system identification in the errors-in-variables setting. The results show that the nuclear norm heuristic performs worse than alternative problem dependant methods—ordinary and total least squares, Kung’s method, and subspace identification. In the line fitting and exponential fitting problems, the globally optimal solution is known analytically, so that the suboptimality of the heuristic methods is quantified.