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

Aron Bevelander; Kim Batselier; Nitin Jonathan Myers

ICASSP 2025accepted0 citations

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

Aron Bevelander, Kim Batselier, Nitin Jonathan Myers

Abstract

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.

BibTeX

@inproceedings{icassp2025_adivideandconque,
  title = {A Divide-and-conquer Approach for Sparse Recovery in High Dimensions},
  author = {Aron Bevelander and Kim Batselier and Nitin Jonathan Myers},
  booktitle = {ICASSP 2025},
  year = {2025}
}