Adaptive Estimation of Time-Varying Sparse Signals

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. This formulation allows us to use Bellman´s principle of optimality in the implementation of multi-step lookahead designs of compressive measurements. We compare the performance of adaptive versus traditional non-adaptive designs and study the value of multi-step (non-myopic) versus one-step (myopic) lookahead adaptive schemes by introducing two variations of the compressive measurement design problem. In the first variation, we consider the problem of sequentially selecting measurement matrices with fixed dimensions from a prespecified library of measurement matrices. 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 measurements. The second problem applies a linear combination of the number of measurements and conditional mutual information as the performance measure. Through several simulations, we study the effectiveness of different designs in various settings. The primary focus in these simulations is the application of a method known as rollout. However, the computational load required for using the rollout method has also inspired us to adapt two data association heuristics to the compressive sensing paradigm. These heuristics show promising decreases in the amount of computation for propagating distributions and searching for optimal solutions.