A Divide-and-conquer Approach for Sparse Recovery in High Dimensions

Block compressed sensing (BCS) alleviates the high storage and memory complexity with standard CS by dividing the sparse recovery problem into sub-problems. This paper presents a Welch bound-based guarantee on the reconstruction error with BCS, revealing that sparse recovery deteriorates with more partitions. To address this performance loss, we propose a data-driven BCS technique that leverages correlation across signal partitions. Our method surpasses classical BCS in moderate SNR regimes, with a modest increase in storage and computational complexities.