A Two Stage Generalized Block Orthogonal Matching Pursuit (TSGBOMP)
  Algorithm
  Recovery of an unknown sparse signal from a few of its projections is the key
objective of compressed sensing. Often one comes across signals that are not
ordinarily sparse but are sparse blockwise. Existing block sparse recovery
algorithms like BOMP make the assumption of uniform block size and known block
boundaries, which are, however, not very practical in many applications. This
paper addresses this problem and proposes a two step procedure, where the first
stage is a coarse block location identification stage while the second stage
carries out finer localization of a non-zero cluster within the window selected
in the first stage. A detailed convergence analysis of the proposed algorithm
is carried out by first defining the so-called pseudoblock-interleaved block
RIP of the given generalized block sparse signal and then imposing upper bounds
on the corresponding RIC. We also extend the analysis for complex vector as
well as matrix entries where it turns out that the extension is non-trivial and
requires special care. Furthermore, assuming real Gaussian sensing matrix
entries, we find a lower bound on the probability that the derived recovery
bounds are satisfied. The lower bound suggests that there are sets of
parameters such that the derived bound is satisfied with high probability.
Simulation results confirm significantly improved performance of the proposed
algorithm as compared to BOMP.
