Blind identification of sparse dynamic networks and applications

Abstract — This paper considers the problem of identifying the topology of a sparsely interconnected network of dynamical systems from experimental noisy data. Specifically, we assume that the observed data was generated by an underlying, unknown graph topology where each node corresponds to a given time-series and each link to an unknown autoregressive model that maps those time series. The goal is to recover the sparsest (in the sense of having the fewest number of links) structure compatible with some a-priori information and capable of explaining the observed data. Contrary to related existing work, our framework allows for (unmeasurable) exogenous inputs, intended to model relatively infrequent events such as environmental or set-point changes in the underlying processes. The main result of the paper shows that both the network topology and the unknown inputs can be identified by solving a convex optimization problem, obtained by combining Group-Lasso type arguments with a re-weighted heuristics. As shown here, this combination leads to substantially sparser topologies than using either group Lasso or orthogonal decomposition based algorithms. These results are illustrated using both academic examples and several non–trivial problems drawn from multiple application domains that include finances, biology and computer vision. I