Error Bounds for Compressed Sensing Algorithms With Group Sparsity: A Unified Approach
Preprint
Abstract
In compressed sensing, in order to recover a sparse or nearly sparse vector from possibly noisy measurements, the most popular approach is $\ell_1$-norm minimization. Upper bounds for the $\ell_2$- norm of the error between the true and estimated vectors are given in [1] and reviewed in [2], while bounds for the $\ell_1$-norm are given in [3]. When the unknown vector is not conventionally sparse but is "group sparse" instead, a variety of alternatives to the $\ell_1$-norm have been proposed in the literature, including the group LASSO, sparse group LASSO, and group LASSO with tree structured overlapping groups. However, no error bounds are available for any of these modified objective functions. In the present paper, a unified approach is presented for deriving upper bounds on the error between the true vector and its approximation, based on the notion of decomposable and $\gamma$-decomposable norms. The bounds presented cover all of the norms mentioned above, and also provide a guideline for choosing norms in future to accommodate alternate forms of sparsity.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- The benefit of group sparsityThe Annals of Statistics, 2010
- Iteratively reweighted least squares minimization for sparse recoveryCommunications on Pure and Applied Mathematics, 2009
- Compressed sensing and best 𝑘-term approximationJournal of the American Mathematical Society, 2008
- The restricted isometry property and its implications for compressed sensingComptes Rendus Mathématique, 2008
- A Simple Proof of the Restricted Isometry Property for Random MatricesConstructive Approximation, 2008
- Deterministic constructions of compressed sensing matricesJournal of Complexity, 2007
- For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solutionCommunications on Pure and Applied Mathematics, 2006
- Model Selection and Estimation in Regression with Grouped VariablesJournal of the Royal Statistical Society Series B: Statistical Methodology, 2005
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- Regression Shrinkage and Selection Via the LassoJournal of the Royal Statistical Society Series B: Statistical Methodology, 1996