Recoverability analysis of block-sparse representation

Recoverability of block-sparse signals by convex relaxation methods is considered for the underdetermined linear model. In previous works, some explicit but pessimistic recoverability results which were associated with the dictionary were presented. This paper shows the recoverability of block-sparse signals are associated with the block structure when a random dictionary is given. Several probability inequalities are obtained to show how the recoverability changes along with the block structure parameters, such as the number of nonzero blocks, the block length, the dimension of the measurements and the dimension of the blocksparse representation signal. Also, this paper concludes that if the block-sparse structure can be considered, the recoverability of the signals will be improved. Numerical examples are given to illustrate the availability of the presented theoretical results.