A generic top-level mechanism for accelerating signal recovery in compressed sensing

Compressed Sensing (CS) is challenged by the computational complexity associated with signal recovery, especially in applications that involve recovering high-dimensional signals. We present an efficient mechanism based on divide-and-conquer principle for accelerating CS signal recovery with minimal impact on recovery quality. In principle, the proposed mechanism is applicable to any CS recovery algorithm, and achieves linear scaling between recovery time and sensed signal dimension in most cases. In addition to analytic performance guarantees, several numerical experiments were performed to verify the performance of the proposed mechanism. A sample result reports average recovery time improvement by a factor above 50 for recovering a 128×128 test image. This mechanism contributes to reducing recovery time, power consumption and the hardware cost required for CS signal recovery.