Compressed sensing refers to the recovery of a high-dimensional but sparsevector using a small number of linear measurements. Minimizing the$\ell_1$-norm is among the more popular approaches for compressed sensing. Arecent paper by Cai and Zhang has provided the "best possible" bounds for$\ell_1$-norm minimization to achieve robust sparse recovery (a formalstatement of compressed sensing). In some applications, "group sparsity" ismore natural than conventional sparsity. In this paper we present sufficientconditions for $\ell_1$-norm minimization to achieve robust group sparserecovery. When specialized to conventional sparsity, these conditions reduce tothe known "best possible" bounds proved earlier by Cai and Zhang. This isachieved by stating and proving a group robust null space property, which is anew result even for conventional sparsity. We also derive bounds for the$\ell_p$-norm of the residual error between the true vector and itsapproximation, for all $p \in [1,2]$. These bounds are new even forconventional sparsity and of course also for group sparsity, because previouslyerror bounds were available only for the $\ell_2$-norm.
展开▼
