One-bit compressive sensing of dictionary-sparse signals
Abstract
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 10, 2017
- Source ID
- 10.1093/imaiai/iax009
Entities
People
- D Needell
- M Wootters
- R Baraniuk
- S Foucart
- Y Plan
Organizations
- Air Force Office of Scientific Research
- Alfred P. Sloan Foundation
- Army Research Office
- National Science Foundation
- Natural Sciences and Engineering Research Council
- Rice University
- Stanford University
- Texas A&M University
- University of British Columbia
- University of California, Los Angeles