Stability and robustness of the l2/lq-minimization for block sparse recovery

This paper focuses on block sparse recovery with the l(2)/l(q)-minimization for 0 < q <= 1. We first give the l(q) stable block Null Space Property (NSP), a new sufficient condition to exactly recover block sparse signals via the l(2)/l(q)-minimization, and it is weaker than the block Restricted Isometry Property (RIP). Second, we propose the l(p), (q)(0 < q <= p) robust block NSP and generalize the instance optimality and quotient property to the block sparse case. Furthermore, we show that Gaussian random matrices and random matrices whose columns are drawn uniformly from the sphere satisfy the block quotient property with high probability. Finally, we obtain the stability estimate of the decoder,triangle(epsilon)(l2/lq) for y = Ax + e with a priori parallel to e parallel to(2) <= epsilon based on the robust block NSP. In addition, for arbitrary measurement error, we also obtain the robustness estimate of the decoder triangle(l2/lq) for y = Ax + e without requiring the knowledge of noise level, which provides a practical advantage when the estimates of measurement noise levels are absent. The results demonstrate that the l(2)/l(q)-minimization can perform well for block sparse recovery, and remains not only stable but also robust for reconstructing noisy signals when the measurement matrices satisfy the robust block NSP and the block quotient property. (C) 2017 Elsevier B.V. All rights reserved.