A hierarchical framework for recovery in compressive sensing

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.