A Constraint Generation Approach to Learning Stable Linear Dynamical Systems

• 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

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.