One-bit compressive sensing of dictionary-sparse signals

R. Baraniuk, S. Foucart, D. Needell, Y. Plan, M. Wootters

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


One-bit compressive sensing has extended the scope of sparse recovery by showing that sparse signals can be accurately reconstructed even when their linear measurements are subject to the extreme quantization scenario of binary samples-only the sign of each linear measurement is maintained. Existing results in one-bit compressive sensing rely on the assumption that the signals of interest are sparse in some fixed orthonormal basis. However, in most practical applications, signals are sparse with respect to an overcomplete dictionary, rather than a basis. There has already been a surge of activity to obtain recovery guarantees under such a generalized sparsity model in the classical compressive sensing setting. Here, we extend the one-bit framework to this important model, providing a unified theory of one-bit compressive sensing under dictionary sparsity. Specifically, we analyze several different algorithms-based on convex programming and on hard thresholding-and show that, under natural assumptions on the sensing matrix (satisfied by Gaussian matrices), these algorithms can efficiently recover analysis-dictionary-sparse signals in the one-bit model.

Original languageEnglish (US)
Pages (from-to)83-104
Number of pages22
JournalInformation and Inference
Issue number1
StatePublished - Mar 15 2018


  • Compressive sensing
  • Convex optimization
  • One-bit compressive sensing
  • Quantization
  • Thresholding
  • Tight frames

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Analysis
  • Applied Mathematics
  • Statistics and Probability
  • Numerical Analysis


Dive into the research topics of 'One-bit compressive sensing of dictionary-sparse signals'. Together they form a unique fingerprint.

Cite this