Strong thresholds for ℓ<inf>2</inf>/ℓ<inf>1</inf>-optimization in block-sparse compressed sensing

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, [5, 10] 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 non-zero 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 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 [25].