A Constraint Generation Approach to Learning Stable Linear Dynamical Systems

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

Full description

Saved in:
Bibliographic Details
Main Authors: Siddiqi, Sajid M, Boots, Byron, Gordon, Geoffrey J
Format: Report
Language:English
Subjects:
ACCURACY
ALGORITHMS
CONVEX BODIES
DYNAMICS
LEARNING
LINEAR SYSTEMS
LINEARITY
Numerical Mathematics
QUALITY
SEQUENCES
SIMULATION
STABILITY
TEST AND EVALUATION
TEXTURE
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 [1, 2], with positive results in terms of accuracy, quality of simulated sequences, and efficiency.