2013/06/17 by Stojnic, Mihailo
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1306.3977
In this paper we revisit one of the classical problems of compressed sensing. Namely, we consider linear under-determined systems with sparse solutions. A substantial success in mathematical characterization of an ℓ1 optimization technique typically used for solving such systems has been achieved during the last decade. Seminal works \citeCRT,DOnoho06CS showed that the ℓ1 can recover a so-called linear sparsity (i.e. solve systems even when the solution has a sparsity linearly proportional to the length of the unknown vector). Later considerations \citeDonohoPol,DonohoUnsigned (as well as our own ones \citeStojnicCSetam09,StojnicUpper10) provided the precise characterization of this linearity. In this paper we consider the so-called structured version of the above sparsity driven problem. Namely, we view a special case of sparse solutions, the so-called block-sparse solutions. Typically one employs ℓ2/ℓ1-optimization as a variant of the standard ℓ1 to handle block-sparse case of sparse solution systems. We considered systems with block-sparse solutions in a series of work \citeStojnicCSetamBlock09,StojnicUpperBlock10,StojnicICASSP09block,StojnicJSTSP09 where we were able to provide precise performance characterizations if the ℓ2/ℓ1-optimization similar to those obtained for the standard ℓ1 optimization in \citeStojnicCSetam09,StojnicUpper10. Here we look at a similar class of systems where on top of being block-sparse the unknown vectors are also known to have components of the same sign. In this paper we slightly adjust ℓ2/ℓ1-optimization to account for the known signs and provide a precise performance characterization of such an adjustment.