| dc.description.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 | en_US |
