l(2)/l(1)-Optimization in Block-Sparse Compressed Sensing and Its Strong Thresholds

It has been known for a while that l(1)-norm relaxation can in certain cases solve an under-determined system of linear equations. Recently, E. Candes et al. (Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Information Theory, vol. 52, no. 12, pp. 489-509, Dec. 2006) and D. Donoho (High-dimensional centrally symmetric polytopes with neighborlines proportional to dimension, Disc. Comput. Geometry, vol. 35, no. 4, pp. 617-652, 2006) proved (in a large dimensional and statistical context) that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of nonzero elements of the unknown vector) also proportional to the length of the unknown vector such that l(1)-norm relaxation succeeds in solving the system. In this paper, in a large dimensional and statistical context, we determine sharp lower bounds on the values of allowable sparsity for any given number (proportional to the length of the unknown vector) of equations for the case of the so-called block-sparse unknown vectors considered in On the reconstruction of block-sparse signals with an optimal number of measurements, (M. Stojnic et al., IEEE Trans, Signal Processing, submitted for publication.