2011/04/06 by Jun Wang, Wang, Jun, Gang Li +5
Computer Science · Engineering · Mathematics · Physics and Astronomy · #FOS: Computer and information sciences #Information Theory (cs.IT) #Microwave Imaging and Scattering Analysis #Random lasers and scattering media #Sparse and Compressive Sensing Techniques #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1104.1071
10 pages, no figures
arxiv created 2011/04/06 · openalex publication_date 2011/04/06 · arxiv updated 2011/04/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Orthogonal matching pursuit (OMP) is a canonical greedy algorithm for sparse signal reconstruction. When the signal of interest is block sparse, i.e., it has nonzero coefficients occurring in clusters, the block version of OMP algorithm (i.e., Block OMP) outperforms the conventional OMP. In this paper, we demonstrate that a new notion of block restricted isometry property (Block RIP), which is less stringent than standard restricted isometry property (RIP), can be used for a very straightforward analysis of Block OMP. It is demonstrated that Block OMP can exactly recover any block K-sparse signal in no more than K steps if the Block RIP of order K+1 with a sufficiently small isometry constant is satisfied. Using this result it can be proved that Block OMP can yield better reconstruction properties than the conventional OMP when the signal is block sparse.