A hierarchical framework for recovery in compressive sensing

Charles J. Colbourn, Daniel Horsley, Violet R. Syrotiuk

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)


A combinatorial framework for the construction of measurement matrices for compressive sensing is shown to exhibit great flexibility in signal recovery. The deterministic column replacement technique is hierarchical: Given as input a pattern matrix and ingredient measurement matrices, it produces a larger measurement matrix by replacing elements of the pattern matrix with columns from the ingredient matrices. Recovery for the measurement matrix produced does not rely on any fixed algorithm; rather it employs the recovery schemes of the ingredient matrices, which may differ from ingredient to ingredient. Because ingredient matrices can be much smaller than the measurement matrix produced, one can employ more computationally intensive recovery methods, sometimes resulting in fewer measurements. Noise can be accommodated in signal recovery by imposing additional conditions both on the pattern matrix and on the ingredient measurement matrices.

Original languageEnglish
Pages (from-to)96-107
Number of pages12
JournalDiscrete Applied Mathematics
Publication statusPublished - 19 Feb 2018


  • Compressive sensing
  • Deterministic column replacement
  • Hash family
  • Hierarchical signal recovery

Cite this