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 A x = 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 Tao shows that minimization of the lscr 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 lscr 1 -norm relaxation, we consider the following relaxation: times min || X 1 || 2 + || X 2 || 2 + ldrldrldr + || X n || 2 , subject to A x = y (*) where X i = ( x ( i -1) d +1, x ( i -1) d +2, ldrldrldr , x i d ) T for i = 1, 2, ldrldrldr , N . Our main result is that as n rarr infin, (*) finds the sparsest solution to A = x = y , with overwhelming probability in A , for any x whose sparsity is k/n < (1/2) - O (isin), provided m / n > 1 - 1/ d , and d = Omega(log(1/isin)/isin 3 ) . The relaxation given in (*) can be solved in polynomial time using semi-definite programming.