Deterministic Construction of Compressed Sensing Matrices from Codes

Compressed sensing is a sparse sampling theory. Compared with the Nyquist-Shannon sampling theory, in compressed sensing one could reconstruct a sparse signal from a few linear and non-adaptive measurements. How to construct a good sensing matrix which captures the full information of a sparse signal is an important problem in compressed sensing. In this paper, we present a new deterministic construction using a linear or nonlinear code, which is a generalization of DeVore’s construction and Li et al.’s construction. By choosing some appropriate linear codes or nonlinear codes, we will construct some good binary sensing matrices which are superior to DeVore’s ones and Li et al.’s ones.