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. Next, we move to a more complicated sparsity model, which is concerned with the recovery of a set of sparse control input vectors. In this setting, we first derive necessary and sufficient conditions for the existence of a sparse solution for any given pair of initial and final states in the LDS. These conditions enable us to develop a simple procedure to test the controllability of LDS using sparse inputs, which is non-combinatorial in nature, unlike the existing sparse-controllability tests. Following the existence test, we address the second question, namely that of devising low-complexity recovery algorithms. We develop online non-iterative algorithms for the same sparsity model. Motivated by the wideband wireless channel estimation problem, we assume that the control inputs are jointly sparse, and the system transfer matrix is diagonal. We devise two online algorithms based on the sparse Bayesian learning framework. The algorithms are implemented using the sequential expectation-maximization procedure, combined with Kalman smoothing. Consequently, they require minimal computational and memory resources, and have bounded delays. Further, we rigorously examine the properties of the algorithm to answer the third question on recovery guarantees. The analysis involves elegant use of tools from stochastic approximation theory. Finally, we present the most sophisticated sparsity model considered in the thesis, where both the control inputs and observation matrix are assumed to be unknown. This problem is referred to as the dictionary learning problem in the CS literature. Here, we focus on algorithm development and establishing its guarantees. We adopt a Bayesian approach for the recovery, and solve the resulting optimization problem using the alternating minimization procedure and the Armijo line search procedure. We then provide recovery guarantees by characterizing the properties of the algorithm using Kurdyka- Lojasiewicz-based analysis. We also show that the algorithm is likely to converge to a sparse representation. Apart from the above set of algorithms and theoretical results, we also apply the sparse signal recovery framework to anomaly imaging for structural health monitoring. The goal here is to recover the anomaly map of a structure using multi-sensor measurements. We develop an algorithm that exploits the inherit clustered sparsity in the map, and benchmark its performance against two state-of-the-art algorithms using real-world damage measurements. Overall, the thesis presents rigorous theoretical analysis and accurate yet low complexity algorithms for sparse recovery problems that arise in the context of LDS