Jorge Gonçalves

Zuogong Yue, Johan Thunberg, Wei Pan et al.

Performing multiple experiments is common when learning internal mechanisms of complex systems. These experiments can include perturbations to parameters or external disturbances. A challenging problem is to efficiently incorporate all collected data simultaneously to infer the underlying dynamic network. This paper addresses the reconstruction of dynamic networks from heterogeneous datasets under the assumption that underlying networks share the same Boolean structure across all experiments. Parametric models for dynamical structure functions are derived to describe causal interactions between measured variables. Multiple datasets are integrated into one regression problem with additional demands of group sparsity to assure network sparsity and structure consistency. To acquire structured group sparsity, we propose a sampling-based method, together with extended versions of l1 methods and sparse Bayesian learning. The performance of the proposed methods is benchmarked in numerical simulation. In summary, this paper presents efficient methods on network reconstruction from multiple experiments, and reveals practical experience that could guide applications.

Zuogon Yue, Johan Thunberg, Lennart Ljung et al.

Network reconstruction of dynamical continuous-time (CT) systems is motivated by applications in many fields. Due to experimental limitations, especially in biology, data could be sampled at low frequencies, leading to significant challenges in network inference. We introduce the concept of "system aliasing" and characterize the minimal sampling frequency that allows reconstruction of CT systems from low sampled data. A test criterion is also proposed to check whether system aliasing is presented. With no system aliasing, the paper provides an algorithm to reconstruct dynamic network from data in the presence of noise. In addition, when there is system aliasing we perform studies that add additional prior information of the system such as sparsity. This paper opens new directions in modelling of network systems where samples have significant costs. Such tools are essential to process the available data in applications subject to current experimental limitations.

Ye Yuan, Ling Shi, Jun Liu et al.

Fueled by applications in sensor networks, these years have witnessed a surge of interest in distributed estimation and filtering. A new approach is hereby proposed for the Distributed Kalman Filter (DKF) by integrating a local covariance computation scheme. Compared to existing well-established DKF methods, the virtue of the present approach lies in accelerating the convergence of the state estimates to those of the Centralized Kalman Filter (CKF). Meanwhile, an algorithm is proposed that allows each node to compute the averaged measurement noise covariance matrix within a minimal discrete-time running steps in a distributed way. Both theoretical analysis and extensive numerical simulations are conducted to show the feasibility and superiority of the proposed method.

E. Yeung, J. Goncalves, H. Sandberg et al.

Interconnected dynamic systems are a pervasive component of our modern infrastructures. The complexity of such systems can be staggering, which motivates simplified representations for their manipulation and analysis. This work introduces the complete computational structure of a system as a common baseline for comparing different simplified representations. Linear systems are then used as a vehicle for comparing and contrasting distinct partial structure representations. Such representations simplify the description of a system's complete computational structure at various levels of fidelity while retaining a full description of the system's input-output dynamic behavior. Relationships between these various partial structure representations are detailed, and the landscape of new realization, minimality, and model reduction problems introduced by these representations is briefly surveyed.

Zuogong Yue, Johan Thunberg, Lennart Ljung et al.

Dynamic network reconstruction has been shown to be challenging due to the requirements on sparse network structures and network identifiability. The direct parametric method (e.g., using ARX models) requires a large amount of parameters in model selection. Amongst the parametric models, only a restricted class can easily be used to address network sparsity without rendering the optimization problem intractable. To overcome these problems, this paper presents a state-space-based method, which significantly reduces the number of unknown parameters in model selection. Furthermore, we avoid various difficulties arising in gradient computation by using the Expectation Minimization (EM) algorithm instead. To enhance network sparsity, the prior distribution is constructed by using the Sparse Bayesian Learning (SBL) approach in the M-step. To solve the SBL problem, another EM algorithm is embedded, where we impose conditions on network identifiability in each iteration. In a sum, this paper provides a solution to reconstruct dynamic networks that avoids the difficulties inherent to gradient computation and simplifies the model selection.

Zuogong Yue, Johan Thunberg, Lennart Ljung et al.

This paper addresses identification of sparse linear and noise-driven continuous-time state-space systems, i.e., the right-hand sides in the dynamical equations depend only on a subset of the states. The key assumption in this study, is that the sample rate is not high enough to directly infer the continuous time system from the data. This assumption is relevant in applications where sampling is expensive or requires human intervention (e.g., biomedicine applications). We propose an iterative optimization scheme with $l_1$-regularization, where the search directions are restricted those that decrease prediction error in each iteration. We provide numerical examples illustrating the proposed method; the method outperforms the least squares estimation for large noise.

J. Jin, Y. Yuan, A. Webb et al.

Increasing attention has recently been given to the inference of sparse networks. In biology, for example, most molecules only bind to a small number of other molecules, leading to sparse molecular interaction networks. To achieve sparseness, a common approach consists of applying weighted penalties to the number of links between nodes in the network and the complexity of the dynamics of existing links. The selection of proper weights, however, is non-trivial. Alternatively, this paper proposes a novel data-driven method, called GESBL, that is able to penalise both network sparsity and model complexity without any tuning. GESBL combines Sparse Bayesian Learning (SBL) and Group Sparse Bayesian Learning (GSBL) to introduce penalties for complexity, both in terms of element (system order of nonzero connections) and group sparsity (network topology). The paper considers a class of sparse linear time-invariant networks where the dynamics are represented by multivariable ARX models. Data generated from sparse random ARX networks and synthetic gene regulatory networks indicate that our method, on average, considerably outperforms existing state-of-the-art methods. The proposed method can be applied to a wide range of fields, from systems biology applications in signalling and genetic regulatory networks to power systems.

Ye Yuan, Guy-Bart Stan, Sean Warnick et al.

Network reconstruction, i.e., obtaining network structure from data, is a central theme in systems biology, economics and engineering. In some previous work, we introduced dynamical structure functions as a tool for posing and solving the problem of network reconstruction between measured states. While recovering the network structure between hidden states is not possible since they are not measured, in many situations it is important to estimate the minimal number of hidden states in order to understand the complexity of the network under investigation and help identify potential targets for measurements. Estimating the minimal number of hidden states is also crucial to obtain the simplest state-space model that captures the network structure and is coherent with the measured data. This paper characterizes minimal order state-space realizations that are consistent with a given dynamical structure function by exploring properties of dynamical structure functions and developing an algorithm to explicitly obtain such a minimal realization.

Rui Teixeira Ribeiro, Alexandre Mauroy, Jorge Goncalves

In this work, we address the problem of identifying sparse continuous-time dynamical systems when the spacing between successive samples (the sampling period) is not constant over time. The proposed approach combines the leave-one-sample-out cross-validation error trick from machine learning with an iterative subset growth method to select the subset of basis functions that governs the dynamics of the system. The least-squares solution using only the selected subset of basis functions is then used. The approach is illustrated on two examples: a 6-node feedback ring and the Van der Pol oscillator.

Arthur N. Montanari, François Lamoline, Robert Bereza et al.

Data-driven modeling of dynamical systems often faces numerous data-related challenges. A fundamental requirement is the existence of a unique set of parameters for a chosen model structure, an issue commonly referred to as identifiability. Although this problem is well studied for ordinary differential equations (ODEs), few studies have focused on the more general class of systems described by differential-algebraic equations (DAEs). Examples of DAEs include dynamical systems with algebraic equations representing conservation laws or approximating fast dynamics. This work introduces a novel identifiability test for models characterized by nonlinear DAEs. Unlike previous approaches, our test only requires prior knowledge of the system equations and does not need nonlinear transformation, index reduction, or numerical integration of the DAEs. We employed our identifiability analysis across a diverse range of DAE models, illustrating how system identifiability depends on the choices of sensors, experimental conditions, and model structures. Given the added challenges involved in identifying DAEs when compared to ODEs, we anticipate that our findings will have broad applicability and contribute significantly to the development and validation of data-driven methods for DAEs and other structure-preserving models.

Ye Yuan, Junlin Li, Liang Li et al.

The study presents a general framework for discovering underlying Partial Differential Equations (PDEs) using measured spatiotemporal data. The method, called Sparse Spatiotemporal System Discovery ($\text{S}^3\text{d}$), decides which physical terms are necessary and which can be removed (because they are physically negligible in the sense that they do not affect the dynamics too much) from a pool of candidate functions. The method is built on the recent development of Sparse Bayesian Learning; which enforces the sparsity in the to-be-identified PDEs, and therefore can balance the model complexity and fitting error with theoretical guarantees. Without leveraging prior knowledge or assumptions in the discovery process, we use an automated approach to discover ten types of PDEs, including the famous Navier-Stokes and sine-Gordon equations, from simulation data alone. Moreover, we demonstrate our data-driven discovery process with the Complex Ginzburg-Landau Equation (CGLE) using data measured from a traveling-wave convection experiment. Our machine discovery approach presents solutions that has the potential to inspire, support and assist physicists for the establishment of physical laws from measured spatiotemporal data, especially in notorious fields that are often too complex to allow a straightforward establishment of physical law, such as biophysics, fluid dynamics, neuroscience or nonlinear optics.

Alexandre Mauroy, Jorge Goncalves

We develop a novel lifting technique for nonlinear system identification based on the framework of the Koopman operator. The key idea is to identify the linear (infinitedimensional) Koopman operator in the lifted space of observables, instead of identifying the nonlinear system in the state space, a process which results in a linear method for nonlinear systems identification. The proposed lifting technique is an indirect method that does not require to compute time derivatives and is therefore well-suited to low-sampling rate datasets. Considering different finite-dimensional subspaces to approximate and identify the Koopman operator, we propose two numerical schemes: the main method and the dual method. The main method is a parametric identification technique that can accurately reconstruct the vector field of a broad class of systems (including unstable, chaotic, and system with inputs). The dual method provides estimates of the vector field at the data points and is well-suited to identify high-dimensional systems with small datasets. The present paper describes the two methods, provide theoretical convergence results, and illustrate the lifting techniques with several examples.

Florian Bernard, Johan Thunberg, Jorge Goncalves et al.

In this work we study permutation synchronisation for the challenging case of partial permutations, which plays an important role for the problem of matching multiple objects (e.g. images or shapes). The term synchronisation refers to the property that the set of pairwise matchings is cycle-consistent, i.e. in the full matching case all compositions of pairwise matchings over cycles must be equal to the identity. Motivated by clustering and matrix factorisation perspectives of cycle-consistency, we derive an algorithm to tackle the permutation synchronisation problem based on non-negative factorisations. In order to deal with the inherent non-convexity of the permutation synchronisation problem, we use an initialisation procedure based on a novel rotation scheme applied to the solution of the spectral relaxation. Moreover, this rotation scheme facilitates a convenient Euclidean projection to obtain a binary solution after solving our relaxed problem. In contrast to state-of-the-art methods, our approach is guaranteed to produce cycle-consistent results. We experimentally demonstrate the efficacy of our method and show that it achieves better results compared to existing methods.

Johan Thunberg, Florian Bernard, Jorge Goncalves

This paper addresses the problem of synchronizing orthogonal matrices over directed graphs. For synchronized transformations (or matrices), composite transformations over loops equal the identity. We formulate the synchronization problem as a least-squares optimization problem with nonlinear constraints. The synchronization problem appears as one of the key components in applications ranging from 3D-localization to image registration. The main contributions of this work can be summarized as the introduction of two novel algorithms; one for symmetric graphs and one for graphs that are possibly asymmetric. Under general conditions, the former has guaranteed convergence to the solution of a spectral relaxation to the synchronization problem. The latter is stable for small step sizes when the graph is quasi-strongly connected. The proposed methods are verified in numerical simulations.

J. Jin, Y. Yuan, W. Pan et al.

This paper begins with considering the identification of sparse linear time-invariant networks described by multivariable ARX models. Such models possess relatively simple structure thus used as a benchmark to promote further research. With identifiability of the network guaranteed, this paper presents an identification method that infers both the Boolean structure of the network and the internal dynamics between nodes. Identification is performed directly from data without any prior knowledge of the system, including its order. The proposed method solves the identification problem using Maximum a posteriori estimation (MAP) but with inseparable penalties for complexity, both in terms of element (order of nonzero connections) and group sparsity (network topology). Such an approach is widely applied in Compressive Sensing (CS) and known as Sparse Bayesian Learning (SBL). We then propose a novel scheme that combines sparse Bayesian and group sparse Bayesian to efficiently solve the problem. The resulted algorithm has a similar form of the standard Sparse Group Lasso (SGL) while with known noise variance, it simplifies to exact re-weighted SGL. The method and the developed toolbox can be applied to infer networks from a wide range of fields, including systems biology applications such as signaling and genetic regulatory networks.

Johan Thunberg, Florian Bernard, Jorge Goncalves

Transitive consistency is an intrinsic property for collections of linear invertible transformations between Euclidean coordinate frames. In practice, when the transformations are estimated from data, this property is lacking. This work addresses the problem of synchronizing transformations that are not transitively consistent. Once the transformations have been synchronized, they satisfy the transitive consistency condition - a transformation from frame $A$ to frame $C$ is equal to the composite transformation of first transforming A to B and then transforming B to C. The coordinate frames correspond to nodes in a graph and the transformations correspond to edges in the same graph. Two direct or centralized synchronization methods are presented for different graph topologies; the first one for quasi-strongly connected graphs, and the second one for connected graphs. As an extension of the second method, an iterative Gauss-Newton method is presented, which is later adapted to the case of affine and Euclidean transformations. Two distributed synchronization methods are also presented for orthogonal matrices, which can be seen as distributed versions of the two direct or centralized methods; they are similar in nature to standard consensus protocols used for distributed averaging. When the transformations are orthogonal matrices, a bound on the optimality gap can be computed. Simulations show that the gap is almost right, even for noise large in magnitude. This work also contributes on a theoretical level by providing linear algebraic relationships for transitively consistent transformations. One of the benefits of the proposed methods is their simplicity - basic linear algebraic methods are used, e.g., the Singular Value Decomposition (SVD). For a wide range of parameter settings, the methods are numerically validated.

Wei Pan, Ye Yuan, Lennart Ljung et al.

In this paper, we propose a new method to identify biochemical reaction networks (i.e. both reactions and kinetic parameters) from heterogeneous datasets. Such datasets can contain (a) data from several replicates of an experiment performed on a biological system; (b) data measured from a biochemical network subjected to different experimental conditions, for example, changes/perturbations in biological inductions, temperature, gene knock-out, gene over-expression, etc. Simultaneous integration of various datasets to perform system identification has the potential to avoid non-identifiability issues typically arising when only single datasets are used.

Florian Bernard, Johan Thunberg, Peter Gemmar et al.

The alignment of a set of objects by means of transformations plays an important role in computer vision. Whilst the case for only two objects can be solved globally, when multiple objects are considered usually iterative methods are used. In practice the iterative methods perform well if the relative transformations between any pair of objects are free of noise. However, if only noisy relative transformations are available (e.g. due to missing data or wrong correspondences) the iterative methods may fail. Based on the observation that the underlying noise-free transformations can be retrieved from the null space of a matrix that can directly be obtained from pairwise alignments, this paper presents a novel method for the synchronisation of pairwise transformations such that they are transitively consistent. Simulations demonstrate that for noisy transformations, a large proportion of missing data and even for wrong correspondence assignments the method delivers encouraging results.

David Hayden, Ye Yuan, Jorge Goncalves

This paper considers the problem of inferring an unknown network of dynamical systems driven by unknown, intrinsic, noise inputs. Equivalently we seek to identify direct causal dependencies among manifest variables only from observations of these variables. For linear, time-invariant systems of minimal order, we characterise under what conditions this problem is well posed. We first show that if the transfer matrix from the inputs to manifest states is minimum phase, this problem has a unique solution irrespective of the network topology. This is equivalent to there being only one valid spectral factor (up to a choice of signs of the inputs) of the output spectral density. If the assumption of phase-minimality is relaxed, we show that the problem is characterised by a single Algebraic Riccati Equation (ARE), of dimension determined by the number of latent states. The number of solutions to this ARE is an upper bound on the number of solutions for the network. We give necessary and sufficient conditions for any two dynamical networks to have equal output spectral density, which can be used to construct all equivalent networks. Extensive simulations quantify the number of solutions for a range of problem sizes. For a slightly simpler case, we also provide an algorithm to construct all equivalent networks from the output spectral density.