Compressed Sensing with Combinatorial Designs: Theory and Simulations

Darryn Bryant, Charles J Colbourn, Daniel Horsley, Padraig O. Cathain

Research output: Contribution to journalArticleResearchpeer-review

12 Citations (Scopus)

Abstract

We use deterministic and probabilistic methods to analyse 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√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.

Original languageEnglish
Pages (from-to)4850-4859
Number of pages10
JournalIEEE Transactions on Information Theory
Volume63
Issue number8
DOIs
Publication statusPublished - Aug 2017

Keywords

  • combinatorial designs
  • Compressed sensing
  • compressed sensing
  • Electronic mail
  • Error correction
  • Error correction codes
  • Matrices
  • signal recovery
  • Sparse matrices
  • Standards

Cite this