On the Reconstruction of Block-Sparse Signals With an Optimal Number of Measurements

Let A be an M by N matrix (M < N) which is an instance of a real random Gaussian ensemble. In compressed sensing we are interested in finding the sparsest solution to the system of equations Ax = y for a given y. In general, whenever the sparsity of x: is smaller than half the dimension of y then with overwhelming probability over A the sparsest solution is unique and can be found by an exhaustive search over x with an exponential time complexity for any y. The recent work of Candes, Donoho, and Tho shows that minimization of the l(1) norm of x subject to A x = y results in the sparsest solution provided the sparsity of x, say K, is smaller than a certain threshold for a given number of measurements. Specifically, if the dimension of y approaches the dimension of x, the sparsity of x should be K < 0.239 N. Here, we consider the case where x is block sparse, i.e., x consists of n = N/d blocks where each block is of length d and is either a zero vector or a nonzero vector (under nonzero vector we consider a vector that can have both, zero and nonzero components). Instead of l(1)-norm relaxation, we consider the following relaxation: min parallel to X-1 parallel to(2) + parallel to X-2 parallel to(2) +...+ parallel to X-n parallel to(2), subject to Ax = y where X-i = (X(i-1)d+1, X(i-1)d+2,...,X-id)(T) for i = 1, 2,..., N. Our main result is that as n -> infinity, (*) finds the sparsest solution to A x = y, with overwhelming probability in A, for any x whose sparsity is k/n (1/2) - O(epsilon), provided m/n > 1 - 1/d, and d = Omega(log(1/epsilon)/epsilon(3)). The relaxation given in (*) can be solved in polynomial time using semi-definite programming.