Construction of Sparse Binary Sensing Matrices Using Set Systems

Recent developments at the intersection of algebra and optimization theory—by the name of compressed sensing (CS)—aim at providing linear systems with sparse descriptions. The deterministic construction of the sensing matrices is now an active directions in CS. The sparse sensing matrix contributes to fast processing with low computational complexity. The present work attempts to relate the notion of set systems to CS. In particular, we show that the set system theory may be adopted to designing a binary CS matrix of high sparsity from the existing binary CS matrices