Compressive measurement design for detection and estimation of sparse signals
Date
2013
Authors
Zahedi, Ramin, author
Chong, Edwin K. P., advisor
Pezeshki, Ali, advisor
Estep, Donald, committee member
Young, Peter M., committee member
Journal Title
Journal ISSN
Volume Title
Abstract
We study the problem of designing compressive measurement matrices for two sets of problems. In the first set, we consider the problem of adaptively designing compressive measurement matrices for estimating time-varying sparse signals. We formulate this problem as a Partially Observable Markov Decision Process (POMDP). This formulation allows us to use Bellman's principle of optimality in the implementation of multi-step lookahead designs of compressive measurements. We introduce two variations of the compressive measurement design problem. In the first variation, we consider the problem of selecting a prespecified number of measurement vectors from a predefined library as entries of the compressive measurement matrix at each time step. In the second variation, the number of compressive measurements, i.e., the number of rows of the measurement matrix, is adaptively chosen. Once the number of measurements is determined, the matrix entries are chosen according to a prespecified adaptive scheme. Each of these two problems is judged by a separate performance criterion. The gauge of efficiency in the first problem is the conditional mutual information between the sparse signal support and the measurements. The second problem applies a linear combination of the number of measurements and the conditional mutual information as the performance measure. We present several simulations in which the primary focus is the application of a method known as rollout. The significant computational load for using rollout has also inspired us to adapt two data association heuristics in our simulations to the compressive sensing paradigm. These heuristics show promising decreases in the amount of computation for propagating distributions and searching for optimal solutions. In the second set of problems, we consider the problem of testing for the presence (or detection) of an unknown static sparse signal in additive white noise. Given a fixed measurement budget, much smaller than the dimension of the signal, we consider the general problem of designing compressive measurements to maximize the measurement signal-to-noise ratio (SNR), as increasing SNR improves the detection performance in a large class of detectors. We use a lexicographic optimization approach, where the optimal measurement design for sparsity level k is sought only among the set of measurement matrices that satisfy the optimality conditions for sparsity level k-1. We consider optimizing two different SNR criteria, namely a worst-case SNR measure, over all possible realizations of a k-sparse signal, and an average SNR measure with respect to a uniform distribution on the locations of the up to k nonzero entries in the signal. We establish connections between these two criteria and certain classes of tight frames. We constrain our measurement matrices to the class of tight frames to avoid coloring the noise covariance matrix. For the worst-case problem, we show that the optimal measurement matrix is a Grassmannian line packing for most—and a uniform tight frame for all—sparse signals. For the average SNR problem, we prove that the optimal measurement matrix is a uniform tight frame with minimum sum-coherence for most—and a tight frame for all—sparse signals.
Description
Rights Access
Subject
compressed sensing
dynamic programming
partially observable Markov decision processes
Q-learning
sparse signal detection
sparse signal estimation