A Constraint Generation Approach to Learning Stable Linear Dynamical Systems

Sajid Siddiqi, Byron Boots, and Geoffrey Gordon
Advances in Neural Information Processing Systems, December, 2007.


Download
  • Adobe portable document format (pdf) (899KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
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.

Notes

Text Reference
Sajid Siddiqi, Byron Boots, and Geoffrey Gordon, "A Constraint Generation Approach to Learning Stable Linear Dynamical Systems," Advances in Neural Information Processing Systems, December, 2007.

BibTeX Reference
@inproceedings{Siddiqi_2007_5871,
   author = "Sajid Siddiqi and Byron Boots and Geoffrey Gordon",
   title = "A Constraint Generation Approach to Learning Stable Linear Dynamical Systems",
   booktitle = "Advances in Neural Information Processing Systems",
   month = "December",
   year = "2007",
}