  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.
