  Compressed sensing is a relatively new mathematical paradigm that shows a
small number of linear measurements are enough to efficiently reconstruct a
large dimensional signal under the assumption the signal is sparse.
Applications for this technology are ubiquitous, ranging from wireless
communications to medical imaging, and there is now a solid foundation of
mathematical theory and algorithms to robustly and efficiently reconstruct such
signals. However, in many of these applications, the signals of interest do not
only have a sparse representation, but have other structure such as
lattice-valued coefficients. While there has been a small amount of work in
this setting, it is still not very well understood how such extra information
can be utilized during sampling and reconstruction. Here, we explore the
problem of integer sparse reconstruction, lending insight into when this
knowledge can be useful, and what types of sampling designs lead to robust
reconstruction guarantees. We use a combination of combinatorial, probabilistic
and number-theoretic methods to discuss existence and some constructions of
such sensing matrices with concrete examples. We also prove sparse versions of
Minkowski's Convex Body and Linear Forms theorems that exhibit some limitations
of this framework.
