  The problem of super-resolution is concerned with the reconstruction of
temporally/spatially localized events (or spikes) from samples of their
convolution with a low-pass filter. Distinct from prior works which exploit
sparsity in appropriate domains in order to solve the resulting ill-posed
problem, this paper explores the role of binary priors in super-resolution,
where the spike (or source) amplitudes are assumed to be binary-valued. Our
study is inspired by the problem of neural spike deconvolution, but also
applies to other applications such as symbol detection in hybrid millimeter
wave communication systems. This paper makes several theoretical and
algorithmic contributions to enable binary super-resolution with very few
measurements. Our results show that binary constraints offer much stronger
identifiability guarantees than sparsity, allowing us to operate in "extreme
compression" regimes, where the number of measurements can be significantly
smaller than the sparsity level of the spikes. To ensure exact recovery in this
"extreme compression" regime, it becomes necessary to design algorithms that
exactly enforce binary constraints without relaxation. In order to overcome the
ensuing computational challenges, we consider a first order auto-regressive
filter (which appears in neural spike deconvolution), and exploit its special
structure. This results in a novel formulation of the super-resolution binary
spike recovery in terms of binary search in one dimension. We perform numerical
experiments that validate our theory and also show the benefits of binary
constraints in neural spike deconvolution from real calcium imaging datasets.
