Sparse optimization for System Identification: Recent Advances and New Perspectives

Organisers

  • Sophie Marie Fosson
  • Diego Regruto

Speakers

  • Sophie M. Fosson, Politecnico di Torino, Italy
  • Cristian Rusu, IIT, Genova, Italy
  • Cristian Rojas, School of Electrical Engineering, KTH Royal Institute of Technology, Stockholm, Sweden
  • João Mota, School of Engineering and Physical Sciences, Heriot-Watt University, Edinburgh, UK
  • Federica Garin, GIPSA-Lab - INRIA, Grenoble, France
  • Chiara Ravazzi, CNR-IEIIT, Torino, Italy
  • Attilio Fiandrotti, Télécom ParisTech, Paris, France
  • Jean-Christophe Loiseau, DynFluid, ENSAM, Paris, France
  • Florian Dörfler, Automatic Control Laboratory, ETH, Zürich, Switzerland

Summary

In modern data-driven system identification, the need for sparse solutions is steadily increasing. Building models from big data requires an extraction process to avoid redundancies, over-fitting, undesired high complexity, and storage issues. For this motivation, sparse optimization techniques have become popular in a number of identification problems. The theory of sparse optimization has been mainly developed in the context of signal processing and statistics. In particular, sparse optimization has reached maximum interest with the theory of compressed sensing, which has inspired several novel approaches and algorithms to deal with sparsity in the last decade.
The motivation behind this workshop is the fact that classical sparse techniques are often used in system identification, while advanced methodologies are developed within the signal processing field; the interplay between the two communities on this topic is not mature. The aim of the proposed workshop is to bring together researchers from system identification and signal processing communities to share experience and discuss new perspectives. Both theoretical advances and real-world applications are considered, with particular attention to more recent technologies where system identification is involved, e.g., deep learning, physical systems, networked systems, and 5G communications. The proposed workshop is organized as part of the activities of the IEEE CSS Technical Committee on System Identification and Adaptive Control (TC-SIAC).

Programme

Sparse optimization for system identification: an introduction, Sophie M. Fosson

We briefly review the history of sparse optimization and its interconnection with system identification. We illustrate the basics of the recovery of sparse vectors from linear measurements, and the compressed sensing theory. In particular, we review the convex approach based on the l1 heuristic, as well as more recent non-convex models, with discussion on the different theoretical conditions for recovery, e.g., coherence and restricted isometry properties. The analogies with the recovery of low-rank matrices are explained. Finally, we describe the applications to linear system identification.


Incoherent measurement matrices in compressed sensing and applications to 5G communications, Cristian Rusu

We discuss the construction of measurement matrices whose columns exhibit low mutual coherence (incoherent matrices or frames) and their application to 5G mmWave communication systems. We give a general outline of the problem, describe several constrained variants inspired by real-world scenarios and discuss the existing algorithms proposed to tackle them. We present a detailed application of incoherent frames to the problem of building massively concurrent non-orthogonal multiple access 5G Networks.


On the sparse estimation approach to change point detection, Cristian Rojas

We discuss the use of the l1 heuristic, in the fused Lasso form, for the segmentation of time series with respect to changes in the mean or variance. Given the wide range of applications of the fused Lasso, a relevant question to address is whether it determines the true change points of the underlying signal. This question is analyzed in an approximate support set recovery sense, as the number of samples tends to infinity. As a result, we see that the fused Lasso is not always consistent, but it can be modified to ensure consistency for a broad range of situations. Then, we discuss other variants of this approach, applicable to cases where the levels (of mean or variance) of the signal are very few, which leads to a change-point detection plus clustering problem.


Adaptive-rate reconstruction of sparse time-varying signals: applications in compressive background Subtraction, João Mota

We propose and analyze an online algorithm for reconstructing a sequence of signals from a limited number of linear measurements. The signals have a sparse representation, with unknown support, and evolve over time according to a generic nonlinear dynamical model. Our algorithm, based on theoretical results for l1-l1 minimization, is recursive and computes the number of measurements to be taken at each time on-the-fly. As an example, we apply the algorithm to online compressive video background subtraction. The performance of our method is illustrated on sequences of real images. We observe that it allows a dramatic reduction in the number of measurements or reconstruction error with respect to state-of-the-art compressive background subtraction schemes.


Security against sparse integrity attacks in cyber-physical systems, Federica Garin

The importance of ensuring security of SCADA systems has been highlighted by accidents such as Stuxnet malware or Maroochy water breach. In addition to classical tools for cyber security (cryptography, communication protocols, etc.), cyber-physical systems security can be improved with control-theoretic tools, exploiting knowledge of the system dynamics. In this talk, we review one line of research on cyber-physical security, dealing with integrity attacks, where the attacker can take full control of a subset of sensors and arbitrarily change their measurements. The possibility to detect such an unknown input is investigated, depending on the attacker resources (sparsity level), jointly using system-theoretic properties and compressive sensing techniques.


Learning hidden influences in sparse social networks, Chiara Ravazzi

Interpersonal influence estimation from empirical data is a central challenge in the study of social structures and dynamics. Opinion dynamics theory is a young interdisciplinary science that studies opinion formation in social networks and has a huge potential in applications, such as marketing, advertisement and recommendations. The term social influence refers to the behavioral change of individuals due to the interactions with others in a social system, e.g. organization, community, or society in general. The advent of Internet has made a huge volume of data easily available that can be used to measure social influence over large populations. Here, we aim at qualitatively and quantitatively infer social influence from data using a systems and control viewpoint. First, we introduce some definitions and models of opinions dynamics and review some structural constraints of online social networks, based on the notion of sparsity. Then, we review the main approaches to infer the network’s structure from a set of observed data. Finally, we present some algorithms that exploit the introduced models and structural constraints, focusing on the sample complexity and computational requirements.


Learning sparse neural topologies with a structure, Attilio Fiandrotti

Deep Neural Networks (DNNs) achieve state-of-the-art performance in several domains thanks to complex topologies with millions of learnable parameters. Large parameters numbers limit the deployability of DNNs in memory-constrained scenarios, e.g. embedded and IoT devices. Regularize-and-prune approaches leverage the knowledge that DNNs need to be over-parametrized during the learning phase to yield sparse topologies, i.e. where large part of the parameters are equal to zero. However, such sparsity is largely unstructured, which compromises the practical ability to exploit such sparsity. First, we review existing approaches towards learning sparse DNN topologies. Then, we present methods to achieve sparse yet structured topologies providing experimental evaluation of their performance.


Incorporating a priori physical constraints in the sparse identification of nonlinear dynamical systems, Jean-Christophe Loiseau

Identifying interpretable models from data has been an overarching goal in science. Over the past years, the Sparse Identification of Nonlinear Dynamics framework (SINDy) has sparked a renewed interest in the identification of continuous-time nonlinear dynamical systems from a limited set of available measurements. Since its introduction in 2015, SINDy has proven to be an extremely versatile framework with numerous variations proposed, e.g. vanilla SINDy, SINDy with control, MANDy, etc. In this talk, we thus aim to give the audience a general overview of the capabilities offered by the SINDy framework. For that purpose, canonical examples from dynamical system theory and fluid dynamics are considered. We most notably focus on how one can incorporate prior knowledge about the system (e.g. invariants, symmetries, etc) in the identification step.


Regularized and Distributionally Robust Data-Enabled Predictive Control, Florian Dörfler

We consider the problem of optimal and constrained control for unknown systems. A novel data-enabled predictive control (DeePC) algorithm is presented that computes optimal and safe control policies using real-time feedback driving the unknown system along a desired trajectory while satisfying system constraints. Using a finite number of data samples from the unknown system, our proposed algorithm uses a behavioral systems theory approach to learn a non-parametric system model used to predict future trajectories. We show that, in the case of deterministic linear time-invariant systems, the DeePC algorithm is equivalent to the widely adopted Model Predictive Control (MPC), but it generally outperforms subsequent system identification and model-based control. To cope with nonlinear and stochastic systems, we propose an l1-regularizations to the DeePC algorithm that promotes a sparse selection of motion primitives. Using techniques from distributionally robust stochastic optimization, we prove that this l1-regularization indeed robustifies DeePC against corrupted data. We illustrate our results with nonlinear and noisy simulations and experiments from aerial robotics, power electronics, and power systems.