Tight Performance Bounds for Compressed Sensing With Group Sparsity
share
Compressed sensing refers to the recovery of a high-dimensional but sparse vector using a small number of linear measurements. Minimizing the ℓ_1-norm is among the more popular approaches for compressed sensing. A recent paper by Cai and Zhang has provided the "best possible" bounds for ℓ_1-norm minimization to achieve robust sparse recovery (a formal statement of compressed sensing). In some applications, "group sparsity" is more natural than conventional sparsity. In this paper we present sufficient conditions for ℓ_1-norm minimization to achieve robust group sparse recovery. When specialized to conventional sparsity, these conditions reduce to the known "best possible" bounds proved earlier by Cai and Zhang. This is achieved by stating and proving a group robust null space property, which is a new result even for conventional sparsity. We also derive bounds for the ℓ_p-norm of the residual error between the true vector and its approximation, for all p ∈ [1,2]. These bounds are new even for conventional sparsity and of course also for group sparsity, because previously error bounds were available only for the ℓ_2-norm.
READ FULL TEXT