Deterministic Construction of Compressed Sensing Matrices over Finite Sets

Compressed sensing (CS) has broken through the traditional Nyquist sampling theory as it is a new technique in signal processing. According to CS theory, compressed sensing makes full use of sparsity so that a sparse signal can be reconstructed from very few measurements. It is well known that the construction of CS matrices is the central problem. In this paper, we provide one kind of deterministic sensing matrix by describing a combinatorial design. Then, we obtain two cases by instantiating the RIP framework with the obtained design, with the latter case being the majorization of the former. Finally, we show that our construction has better properties than DeVore’s construction using polynomials over finite fields.