Motivated by the distance to uncontrollability problem, we define a distance between finite-length linear timeinvariant systems. The method proposed in this paper for computing the distance exploits the principal angles associated with structured matrices representing the systems.

There is a growing interest in data-driven control of nonlinear systems over the last years. In contrast to related works, this paper takes a step back and aims to solve the output matching problem, a problem closely related to the reference tracking control problem, for a broader class of nonlinear systems called output-generalized bilinear, thereby offering a new direction to explore for data-driven control of nonlinear systems. It is shown that discrete-time linear parameter-varying systems are included in this model class, with affine systems easily shown to also be included. The proposed model class and method are illustrated using the simulation of a real-life system.

Nonlinear phenomena can be represented as nonlinear autoregressive exogenous (NARX) systems. NARX systems can be seen as a nonlinear version of linear infinite impulse response filter. Data-driven approaches are witnessing considerable interests in recent times and they are well-flourished for linear time-invariant systems. However, for nonlinear systems, they are still limited and attempts have been made to generalize the results for linear systems to nonlinear systems. In this paper, we study the problem of data-driven simulation for NARX systems: compute the output trajectory from a given input trajectory and initial conditions without explicitly identifying the parametric model; the model is implicitly identified by observed trajectory. Next, we develop an algorithm for the implementation of our approach. Finally, we illustrate the developed algorithm by numerical experiments.

Keywords: Data-driven simulation, NARX, System identification

The paper demonstrates the claim in the title using missing data estimation as a generic example. The missing data estimation problem includes simulation, Kalman smoothing, and linear quadratic control as special cases. The solution method proposed uses an idea from subspace identification: under a persistency of excitation condition, the image of a Hankel matrix constructed from the data is equal to the behavior of the data-generating system. This fact allows construction of trajectories of the system directly from observed raw data. The construction of trajectories is the key for solving analysis, signal processing, and control problems without parametric model identification. The resulting methods require solution of systems of linear equations, however, the data is assumed exact and obtained from a linear time-invariant system.

We consider the problem of detecting the common dynamic among several observed signals. It has been shown in (Markovsky et al., 2019) that the problem is equivalent to a generalization of the classical Hankel low-rank approximation to the case of multiple rank constraints. We propose an optimization method based on the integration of ordinary differential equations describing a descent dynamic for a suitable functional to be minimized. We show how the proposed algorithm improves the numerical solutions computed by existing subspace methods which solve the same problem.

Estimation of line spectra is a classical problem in signal processing and arises in many applications. The problem is to estimate the frequencies and corresponding amplitudes of a sum of (possibly complex-valued) sinusoidal components from noisy measurements. It can be solved with maximum likelihood methods or with suboptimal subspace methods. The constraint that the model does not have damping is difficult to impose in subspace methods. We develop an equivalent formulation as a structured low-rank approximation problem and present a necessary condition for the model to be undamped. The condition is that a vector in the kernel of a Hankel matrix of observations has palindromic structure and it leads to a linear equality constraint which is easily incorporated into a numerical algorithm. Simulations show that even for relatively high noise-to-signal ratios, the necessary condition is in practice also sufficient, i.e. the identified model does not have damping.

Keywords: Line spectral estimation, structured low-rank approximation, palyndromic kernels, subspace methods

We consider the problem of computing (approximate) greatest common divisors for matrix polynomials and we present some related facts and applications in system and control theory. The main application is to compute the distance of a controllable multi-input multi-output system to the set of uncontrollable ones; then we describe some related results.

Keywords: Matrix polynomial common factor, Distance to uncontrollability, Behavioral approach

This paper presents the SLRA package (http://slra.github.io)---C software with interface to MATLAB, Octave, and R for solving low-rank approximation problems with the following features: mosaic Hankel structured approximating matrix, weighted 2-norm approximation criterion, and fixed and missing elements in the approximating matrix. The package has applications in system identification, machine learning, and computer algebra. The paper gives an overview of the features of the package, including the wrapper functions for system identification (IDENT package) and approximate greatest common divisor (AGCD) computations. The addendum to the paper, available from https://imarkovs.github.io/slra-demo, includes examples that demonstrate the usage, versatility, and efficiency of the software.

Keywords: system identification; low-rank approximation; mosaic Hankel matrix; missing data; approximate greatest common factor; software

Applications of signal processing and control are classically model-based, involving a two-step procedure for modeling and design: first a model is built from given data, and second, the estimated model is used for filtering, estimation, or control. Both steps typically involve optimization problems, but the combination of both is not necessarily optimal, and the modeling step often ignores the ultimate design objective. Recently, data-driven alternatives are receiving attention, which employ a direct approach combining the modeling and design into a single step. In earlier work, it was shown that data-driven signal processing problems can often be rephrased as missing data completion problems, where the signal of interest is part of an incomplete low-rank mosaic Hankel structured matrix. In this paper, we consider the exact data case and the problem of simulating from a given input, an output trajectory of the unknown data generating system. Our findings suggest that, when using an adequate rescaling of the given data, the exact data-driven simulation problem can be solved by replacing the original structured low-rank matrix completion problem by a convex optimization problem, using the nuclear norm heuristic.

Keywords: data-driven signal processing, low-rank matrix completion, mosaic Hankel matrix, nuclear norm, convex optimization

Estimation of common dynamics among several observed signals occurs in signal processing, system theory, and computer algebra problems. In this paper, we propose subspace methods for common linear time-invariant dynamics detection and estimation. First, we consider the deterministic problem of detection of common dynamics when the data is exact (noise free). Then, we consider the stochastic estimation problem when the data is corrupted by white Gaussian noise. The methods proposed have a system theoretic interpretation of finding the intersection of autonomous linear time-invariant behaviors.

Keywords: common dynamics, subspace identification, behavioral approach, approximate common divisor

Data-driven control is an alternative to the classical model-based control paradigm. The main idea is that a model of the plant is not explicitly identified prior to designing the control signal. Two recently proposed methods for data-driven control—a method based on correlation analysis and a method based on structured matrix low-rank approximation and completion—solve identical control problems. The aim of this paper is to compare the methods, both theoretically and via a numerical case study. The main conclusion of the comparison is that there is no universally best method: the two approaches have complementary advantages and disadvantages. Future work will aim to combine the two methods into a more effective unified approach for data-driven output tracking.

Keywords: data-driven control, output tracking, virtual reference feedback tuning, structured low-rank approximation, matrix completion

With the introduction of very dense sensor arrays in ultrasound (US) imaging, data transfer rate and data storage can become a bottle neck in ultrasound system design. To reduce the amount of sampled channel data, several strategies based on compressive sensing (CS) have been proposed. However, the reconstruction accuracy of CS-based methods is highly dependent on the sparse basis and the number of measurements for each channel cannot be lower than the sparsity thereby limiting the data reduction rate. Therefore, we propose to use a low-rank and joint-sparse model to represent US signals and exploit the correlations between adjacent receiving channels. Results show that the proposed method is better adapted to the ultrasound signals and can recover high quality image approximations from as low as 10% of the samples.

Keywords: compressive sensing, matrix completion, low-rank and joint-sparse model, ultrasound imaging

Fitting a signal to a sum-of-exponentials model is a basic problem in signal processing. It can be posed and solved as a Hankel structured low-rank matrix approximation problem. Subsequently, local optimization, subspace, and convex relaxation methods can be used for the numerical solution. In this paper, we show another approach, based on the recently proposed concept of structured data fusion. Structured data fusion problems are solved in the Tensorlab toolbox by local optimization methods. The approach allows fitting of signals with missing samples and adding constraints on the model, such as fixed exponents and common dynamics in multi-channel estimation problems. These problems are non-trivial to solve by other existing methods.

Keywords: system identification; low-rank approximation; mosaic Hankel matrix; tensorlab; structured data fusion.

The paper considers the class of discrete-time, single-input, single-output, nonlinear dynamical systems described by a polynomial difference equation. This class, call polynomial time-invariant, is a proper generalization of the linear time-invariant model class. The identification data is assumed to be generated in the errors-in-variables setting, where the input and the output noise is zero mean, white, and the noise variances is known up to a scaling factor. The identification problem has two sub-problems

structure selection: find the monomials appearing in the difference equation representation of the system, and parameter estimation: estimate the coefficients of the equation.

The main result shows that the parameter estimation by minimization of the 2-norm of the equation error leads to unstructured low-rank approximation of an extended data matrix. The resulting method is computationally robust and efficient due to the use of the singular value decomposition. However, it requires knowledge of the model structure and even when the correct model structure is used, it leads to biased results. For the structure selection, the use 1-norm regularization is proposed. For the bias removal an adjustment of the ordinary least squares estimator is proposed. The resulting adjusted low-rank approximation methods defines an unbiased estimator for the model parameters of the polynomial time-invariant model.

The applicability of subspace-based system identification methods highly depends on the disturbances acting on the system. It is well-known, e.g., that the standard implementations of the MOESP, N4SID or CVA algorithms yield biased estimates when closed-loop noisy data is considered. In order to bypass this difficulty, we follow the recent trends for closed-loop subspace-based model identification and suggest, in a first step, pre-estimating the innovation term from the available data. By doing so, the initial subspace-based identification problem can be written as a deterministic problem for which efficient methods exist. Once the innovation sequence is estimated, the second step of our subspace-based identification procedure focuses on the estimation of the open-loop and closed-loop system's Markov parameters. A constrained least-squares solution is more precisely considered to guarantee structural constraints satisfied by Toeplitz matrices involved the open-loop and closed-loop data equations, respectively. The performance of the methods is illustrated through the study of simulation examples under open-loop and closed-loop conditions.

Keywords:

A classical tool for spurious poles detection in modal analysis is the stabilization diagram. It is widely used by practitioners because of its simplicity and intuitive appeal. Despite of its popularity the stabilization diagram requires subjective human judgment and lacks theoretical justification. In this paper, we propose an new approach to spurious poles detection that 1) has theoretical justification and 2) does not make unverifiable assumptions about the data generating system, apart form the basic one that it is linear time-invariant. The method is based on a quantitative measure of the distance of the identified model to a system with an eliminated spurious pole. Small distance indicates that the eliminated pole does not degrade the model quality. The procedure can be iterated for elimination of multiple spurious poles. An increase of the distance indicates that all spurious poles are eliminated from the model.

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

We present a new connection between higherorder tensors and affinely structured matrices, in the context of low-rank approximation. In particular, we show that the tensor low multilinear rank approximation problem can be reformulated as a structured matrix low-rank approximation, the latter being an extensively studied and well understood problem.

We first consider symmetric tensors. Although the symmetric tensor problem is at least as difficult as the general unstructured tensor problem, the symmetry allows us to simplify and clearly show the relation to the matrix structured low-rank approximation problem. By imposing linear equality constraints in the optimization problem, the proposed approach is applicable to unstructured tensors, as well as to affinely structured tensors. Therefore, it can be used to find (locally) optimal low multilinear rank approximation with a predefined structure. An advantage of the proposed approach is that it can deal with more difficult variations of the main problem, including having missing and fixed elements in the given tensor or approximating with respect to a weighted norm. The drawback is its higher computational cost, compared to existing algorithms, partially due to the generality of the approach.

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.

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.

Closed-loop data-driven simulation refers to the problem of constructing trajectories of a closed-loop system directly from data of the plant and a representation of the controller. Conditions under which the problem has a solution are given and an algorithm for computing the solution is presented. The problem formulation and its solution are in the spirit of the deterministic identification algorithms, i.e., in the theoretical analysis of the method, the data is assumed exact (noise free).

The subject area of this paper is discrete-time linear time-invariant systems composed of subsystems whose state updating is asynchronous due to the clock signal arriving with delays. This leads to the synchronization error identification problem which is to find from a trajectory of the system the order in which the subsystems' states are updated. A solution to this problem based on a direct search over all possible synchronization errors is developed together with conditions for its uniqueness.

Band-pass, Kalman, and adaptive filters are used for removal of resuscitation artifacts from human ECG signals. A database of separately recorded human ECG and animal resuscitation artifact signals is used for evaluation of the methods. The considered performance criterion is the signal-to-noise ratio (SNR) improvement, defined as the ratio of the SNRs of the filtered signal and the given ECG signal. The empirical results show that for low SNR of the given signal, a band-pass filter yields the best performance, while for high SNR, an adaptive filter yields the best performance.

We study the linear quadratic control problem from a representation-free point of view, and we show that this formulation brings forth two self-contained and original proofs of the optimality of state feedback control laws; these proofs which do not depend on an a priori state-space representation.

The roots of palindromic and antipalindromic polynomials appear in pairs (s,1/s). A polynomial with such roots is antipalindromic if and only if in addition, it has a root at 1 of an odd multiplicity. The result has applications in system theory: 1) any kernel representation of a discrete-time, time-reversible, scalar, autonomous LTI system is either palindromic or antipalindromic. (Similar statement holds for systems with inputs.) 2) LTI systems with palindromic or antipalindromic kernel representations have nontrivial conserved quantities.

The classical approach for solving control problems is model based: first a model representation is derived from given data of the plant and then a control law is synthesized using the model and the control specifications. We present an alternative approach that circumvents the explicit identification of a model representation. The considered control problem is finite horizon linear quadratic tracking. The results are derived assuming exact data and the optimal trajectory is constructed off-line.

A MATLAB toolbox for exact linear time-invariant system identification is presented. The emphasis is on the variety of possible ways to implement the mappings from data to parameters of the data generating system. The considered system representations are input/state/output, difference equation, and left matrix fraction. The reader is referred to the literature for the theory behind the implemented algorithm. The paper shows the implementation details on the level of documented MATLAB code.

Keywords: Exact system identification, numerical implementation, MATLAB.

We propose an estimation method for an errors-in-variables model with unknown input and output noise variances. The main assumption that allows identifiability of the model is clustering of the data into two clusters that are distinct in a certain specified sense. We show an application of the proposed method for system identification.

Keywords: errors-in-variables, system identification, total least squares, clustering

We consider algorithms for recursive computation of an exact model for a given time series. Existing algorithms that operate recursively in time are reviewed and a new algorithm that operates recursively in the degrees of the system laws is described.

Keywords: most powerful unfalsified model,recursive identification,partial realization,Berlekamp-Massey algorithm

In this presentation, we consider the problem of obtaining the state trajectory directly from an observed vector time-series. We show how the Hankel structure of the data matrix can be exploited in this construction. Both the cases of infinite as well as finite time-series are considered, but only deterministic systems are discussed.

Keywords: Most powerful unfalsified model, subspace identification, state construction.

We consider ARMAX system representations and identification problems. Identifiability conditions in terms of the correlation function of the process are given. One of the conditions is persistency of excitation of an input component of the process and another one is a rank condition for a pair of Hankel matrices.

We study the linear combinations of the process and its shifts that produce a process independent of the input. The set of all such linear combinations, called the orthogonalizers, has a module structure and under identifiability conditions completely specifies the deterministic part of the ARMAX system. Computing a module basis for the orthogonalizers is a deterministic identification problem.

We propose an ARMAX identification algorithm, which has three steps: first compute the deterministic part of the system via the orthogonalizers, then the AR part, which also has a module structure, and finally the MA part.

The stabilization diagrams, used in modal analysis, rely on the intuitive notion of a spurious pole. In this paper, we give a definition of a spurious pole, based on the most powerful unfalsified model (MPUM) of the data, i.e., on an exact model for the data. The poles of the MPUM are by definition physical and a pole that is not physical is by definition spurious. Our definition does not make assumptions about the data, apart from the basic postulation of the linear time-invariant model class. In this sense it is unprejudiced. Since the MPUM can be constructed from the data, one can compute the physical poles and thus answer the question in the title. If, however, one knows a priori that the data are noise corrupted trajectory of a true data generating system or that there is an unobserved process noise acting on the true system, one should use this knowledge. In this case, the MPUM concept has to be modified to allow for approximation. Methods for approximate system identification and model reduction are reviewed and applied for spurious pole detection of simulated data.