Linear Dynamical Systems with Sparsity Constraints Theory and Algorithms

Abstract

This thesis develops new mathematical theory and presents novel recovery algorithms for discrete linear dynamical systems (LDS) with sparsity constraints on either control inputs or initial state. The recovery problems in this framework manifest as the problem of reconstructing one or more sparse signals from a set of noisy underdetermined linear measurements. The goal of our work is to design algorithms for sparse signal recovery which can exploit the underlying structure in the measurement matrix and the unknown sparse vectors, and to analyze the impact of these structures on the efficacy of the recovery. We answer three fundamental and interconnected questions on sparse signal recovery problems that arise in the context of LDS. First, what are necessary and sufficient conditions for the existence of a sparse solution? Second, given that a sparse solution exists, what are good low-complexity algorithms that exploit the underlying signal structure? Third, when are these algorithms guaranteed to succeed? These questions are considered in the context of three different sparsity models, as described below. Within the LDS framework, we first consider the simplest sparsity model of a single unknown sparse initial state vector with no additional structure. This problem is known as the observability problem in the control theory literature, and the initial state can be recovered using standard compressed sensing (CS) algorithms. However, the recovery guarantees for this case are different from the classical sparse recovery guarantees because the measurement matrix that arises in LDS is fundamentally different from the matrices that are typically considered in the CS literature. We seek to obtain the conditions for observability of LDS when the initial state is sparse and the observation matrix is random. Taking advantage of randomness in the measurements, we use concentration inequalities to derive an upper bound on the minimum number of measurements that can ensure faithful recovery of the sparse initial state...