An Algorithm for Learning Switched Linear Dynamics from Data
Main Conference Track
Authors: Guillaume Berger, Monal Narasimhamurthy, Kandai Watanabe, Morteza Lahijanian, Sriram Sankaranarayanan

We present an algorithm for learning switched linear dynamical systems in discrete time from noisy observations of the system's full state or output. Switched linear systems use multiple linear dynamical modes to fit the data within some desired tolerance. They arise quite naturally in  applications to  robotics and cyber-physical systems.  Learning  switched systems  from  data is a NP-hard problem that is nearly identical  to the $k$-linear regression problem of fitting $k > 1$ linear models to the data.  A direct mixed-integer linear programming (MILP) approach  yields time  complexity that is  exponential in the number of data points. In this paper, we modify the problem formulation  to yield an algorithm that is linear in the size of the data while remaining exponential in the number of state variables and the desired number of modes. To do so, we combine classic ideas from the ellipsoidal method for solving convex optimization problems, and well-known oracle separation results in non-smooth optimization.  We demonstrate our approach on a set of microbenchmarks and a few interesting real-world problems. Our evaluation  suggests that the benefits of this algorithm can be made practical even against highly optimized off-the-shelf MILP solvers.