Recovery Guarantee Analyses of Joint Sparse Recovery via Tail $ \ell _{2,1}$ Minimization

Recovery guarantee analyses of the tail-
$ \ell _{2,1}$
minimization approach applied to multiple measurement vector (MMV) model are presented. Exact joint sparse recovery from the MMV model benefits from the rank enrichment of
$rank(\boldsymbol{X})$
. Generally speaking, unique sparse solution exists for sparsity level
$k < K_{0} \equiv [rank(\boldsymbol{X})+spark(\boldsymbol{A})-1]/2$
. We observe in extensive empirical tests that the MMV tail-
$ \ell _{2,1}$
minimization approach is capable of recovering signals of the sparsity level up to
$spark(\boldsymbol{A})$
, even for
$ rank(\boldsymbol{X})\ll k$
, significantly beyond the rank-enriched upper bound
$ K_{0}$
. This phenomenon is now known to be the measure theoretical uniqueness solution of the MMV problem. To analyze the greater recovery capacity of the MMV tail-
$ \ell _{2,1}$
minimization approach, two necessary and sufficient conditions for the unique solution are established. It is shown that these two tail-
$ \ell _{2,1}$
solution conditions are more likely to hold than comparable conditions of the conventional
$ \ell _{2,1}$
minimization approach. Furthermore, theoretical recovery guarantee analyses of the tail-minimization approach are carried out. Specifically, two recovery probability estimates are derived. These successful recovery probabilities are shown to approach 1 not only as the number of measurements
$L$
increases (exponentially) but also as
$|T^{c} \cap S|\to 0$
, where
$T$
is an estimation of the support index set
$S$
. That the MMV tail-
$ \ell _{2,1}$
minimization algorithm can recover signals of sparsity level beyond
$ K_{0}$
and approaching
$ spark(\boldsymbol{A})$
is sufficiently illustrated from these recovery probabilities.