CMU-ML-08-101
Machine Learning Department
School of Computer Science, Carnegie Mellon University



CMU-ML-08-101

A Constraint Generation Approach to
Learning Stable Linear Dynamical Systems

Sajid M. Siddiqi*, Byron Boots, Geoffrey J. Gordon

January 2008

CMU-ML-08-101.pdf


Keywords: Dynamical systems, sequential data modeling, constraint generation, control, stability


Stability is a desirable characteristic for linear dynamical systems, but it is often ignored by algorithms that learn these systems from data. We propose a novel method for learning stable linear dynamical systems: we formulate an approximation of the problem as a convex program, start with a solution to a relaxed version of the program, and incrementally add constraints to improve stability. Rather than continuing to generate constraints until we reach a feasible solution, we test stability at each step; because the convex program is only an approximation of the desired problem, this early stopping rule can yield a higher-quality solution. We apply our algorithm to the task of learning dynamic textures from image sequences as well as to modeling biosurveillance drug-sales data. The constraint generation approach leads to noticeable improvement in the quality of simulated sequences. We compare our method to those of Lacy and Bernstein, with positive results in terms of accuracy, quality of simulated sequences, and efficiency.

17 pages

*Robotics Institute, Carnegie Mellon University


SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu