The restless multi-armed bandit formulation of the cognitive compressive sensing problem

Saeed Bagheri, Anna Scaglione

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


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.

Original languageEnglish (US)
Article number7004089
Pages (from-to)1183-1198
Number of pages16
JournalIEEE Transactions on Signal Processing
Issue number5
StatePublished - Mar 1 2015


  • Cognitive radio
  • compressive sensing
  • multi-channel sensing
  • myopic policy
  • opportunistic spectrum access

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'The restless multi-armed bandit formulation of the cognitive compressive sensing problem'. Together they form a unique fingerprint.

Cite this