Compressed sensing of block-sparse positive vectors

Abstract

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 ${\ell }_1$ optimization technique typically used for solving such systems has been achieved during the last decade. Seminal works \cite{CRT,DOnoho06CS} showed that the ${\ell }_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 \cite{DonohoPol,DonohoUnsigned} (as well as our own ones \cite{StojnicCSetam09,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 ${\ell }_2/{\ell }_1$-optimization as a variant of the standard ${\ell }_1$ to handle block-sparse case of sparse solution systems. We considered systems with block-sparse solutions in a series of work \cite{StojnicCSetamBlock09,StojnicUpperBlock10,StojnicICASSP09block,StojnicJSTSP09} where we were able to provide precise performance characterizations if the ${\ell }_2/{\ell }_1$-optimization similar to those obtained for the standard ${\ell }_1$ optimization in \cite{StojnicCSetam09,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 ${\ell }_2/{\ell }_1$-optimization to account for the known signs and provide a precise performance characterization of such an adjustment.

acknowledgement footnote added arXiv admin note: substantial text overlap with arXiv:1304.0001, arXiv:0907.3679, arXiv:1306.3801

References in corpus (7)

• Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• Reduce and Boost: Recovering Arbitrary Sets of Jointly Sparse Vectors
• Joint-sparse recovery from multiple measurements
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Block-length dependent thresholds in block-sparse compressed sensing
• Regularly random duality
• Optimality of ${\ell }_2/{\ell }_1$-optimization block-length dependent thresholds