  We propose to reduce the original well-posed problem of compressive sensing
to weighted-MAX-SAT. Compressive sensing is a novel randomized data acquisition
approach that linearly samples sparse or compressible signals at a rate much
below the Nyquist-Shannon sampling rate. The original problem of compressive
sensing in sparse recovery is NP-hard; therefore, in addition to restrictions
for the uniqueness of the sparse solution, the coding matrix has also to
satisfy additional stringent constraints -usually the restricted isometry
property (RIP)- so we can handle it by its convex or nonconvex relaxations. In
practice, such constraints are not only intractable to be verified but also
invalid in broad applications. We first divide the well-posed problem of
compressive sensing into relaxed sub-problems and represent them as separate
SAT instances in conjunctive normal form (CNF). After merging the resulting
sub-problems, we assign weights to all clauses in such a way that the
aggregated weighted-MAX-SAT can guarantee successful recovery of the original
signal. The only requirement in our approach is the solution uniqueness of the
associated problems, which is notably looser. As a proof of concept, we
demonstrate the applicability of our approach in tackling the original problem
of binary compressive sensing with binary design matrices. Experimental results
demonstrate the supremacy of the proposed SAT-based compressive sensing over
the $\ell_1$-minimization in the robust recovery of sparse binary signals.
SAT-based compressive sensing on average requires 8.3% fewer measurements for
exact recovery of highly sparse binary signals ($s/N\approx 0.1$). When $s/N
\approx 0.5$, the $\ell_1$-minimization on average requires 22.2% more
measurements for exact reconstruction of the binary signals. Thus, the proposed
SAT-based compressive sensing is less sensitive to the sparsity of the original
signals.
