Minimum Measurement Deterministic Compressed Sensing based on Complex Reed Solomon Decoding

Compressed Sensing (CS) is an emerging field in communications and mathematics that is used to measure few measurements of long sparse vectors with the ability of lossless reconstruction. In this paper we use results from channel coding to design a recovery algorithm for CS with a deterministic measurement matrix by exploiting error correction schemes. In particular, we show that a generalized Reed Solomon encoding-decoding structure can be used to measure sparsely representable vectors, that are sparse in some fitting basis, down to the theoretical minimum number of measurements with the ability of guaranteed lossless reconstruction, even in the low dimensional case.