Compressed Sensing With Combinatorial Designs: Theory and Simulations

We use deterministic and probabilistic methods to analyze the performance of compressed sensing matrices constructed from Hadamard matrices and pairwise balanced designs, previously introduced by a subset of the authors. In this paper, we obtain upper and lower bounds on the sparsity of signals for which our matrices guarantee recovery. These bounds are tight to within a multiplicative factor of at most 4 root 2. We provide new theoretical results and detailed simulations, which indicate that the construction is competitive with Gaussian random matrices, and that recovery is tolerant to noise. A new recovery algorithm tailored to the construction is also given.