SAT-based Compressive Sensing

Understand

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.