M22 – PARIS‐SACLAY 09/05/2016 – 13/05/2016

The Interplay Between Big Data and Sparsity in Control and Systems Identification

Mario Sznaier
Department of Electrical and Computer Engineering
Northeastern University, Boston, MA, USA


Arguably, one of the hardest challenges faced now by the systems community stems from the exponential explosion in the availability of data, fueled by recent advances in sensing technology. Simply stated, classical techniques are ill equipped to handle very large volumes of (heterogeneous) data, due to poor scaling properties and to impose the structural constraints required to implement ubiquitous sensing and control. To overcome these shortcomings, during the past few years a large research effort has been devoted to developing computationally tractable methods that seek to mitigate the “curse of dimensionality” by exploiting the twin blessings of self-similarity (high degree of spatio-temporal correlation in the data) and concentration of measure (inherent underlying sparsity).

These efforts have resulted in new approaches, that draw from many disparate areas, ranging from semi-algebraic geometry to sparse signal recovery and matrix completion, and exploit the underlying structure of the problem to obtain tractable relaxations (and is some cases exact solutions) to computationally hard problems. The goal of this short course is twofold: (1) provide a quick introduction to the subject for people in the systems community faced with “big data” and scaling problems, and (2) serve as a “quick reference” guide for researchers, summarizing the state of the art as of today and provide a comprehensive set of references. Part I of the course covers the issue of handling large data sets and sparsity priors in systems identification and model (in)validation, presenting very recently developed techniques that exploit a deep connection to semi-algebraic geometry, rank minimization and matrix completion. Part II of the course continues this theme, but focusing on control and filter design. The course concludes by illustrating these ideas using examples from several application domains, including machine learning, computer vision, systems biology and economics.

Course outline

1. Mathematical Foundations: - Review of convex optimization and Linear Matrix Inequalities – Review of semi-algebraic geometry – Promoting sparsity via optimization. Convex surrogates for cardinality and rank – Fast algorithms for convex optimization – Polynomial optimization: Sum-of-squares and moments based approaches – Exploiting sparsity in polynomial optimization.

2. Sparsity in Systems Identification: – Identification of LTI systems with missing data and outliers – Identification of sparse graphical models – Identification of Wiener systems – Semi-supervised identification of switched affine systems – Model invalidation.

3. Sparsity in Control and Estimation: – Synthesis of controllers subject to sparsity constraints: the convex case – Synthesis of controllers subject to sparsity flow constraints: the general case – Sparse filter design for LTI systems – Worst case optimal filters for switched systems.

4. Connections to Machine Learning: – Robust regression and subspace clustering – Manifold embedding as a Wiener identification problem.

5. Applications: – Actionnable information extraction as a SysId problem – Finding causal interactions as a sparse graphical model identification – Recovering 3D geometry from 2D data as aWiener identification problem – Anomaly detection as a model (in)validation problem – Multitarget tracking as a rank-minimizing assignment problem.