The Restless Multi-Armed Bandit Formulation of the Cognitive Compressive Sensing Problem

In this paper we introduce the Cognitive Compressive Sensing (CCS) problem, modeling a Cognitive Receiver (CR) that optimizes the K projections of a N > K dimensional vector dynamically, by optimizing the objective of correctly detecting the maximum number of idle entries, while updating each time its Bayesian beliefs on the future vector realizations. We formulate and study the CCS as a Restless Multi-Armed Bandit problem, generalizing the popular Cognitive Spectrum Sensing model, in which the CR can sense K out of the N sub-channels and propose a novel adaptive Finite Rate of Innovation (FRI) sampling method based on the CCS approach. While in general the optimum policy remains elusive, we provide sufficient conditions in which in the limit for large K and N the greedy policy is optimum. Numerical results corroborate our theoretical findings.