Accuracy guaranties for ${\ell }_1$ recovery of block-sparse signals

Abstract

We introduce a general framework to handle structured models (sparse and block-sparse with possibly overlapping blocks). We discuss new methods for their recovery from incomplete observation, corrupted with deterministic and stochastic noise, using block-${\ell }_1$ regularization. While the current theory provides promising bounds for the recovery errors under a number of different, yet mostly hard to verify conditions, our emphasis is on verifiable conditions on the problem parameters (sensing matrix and the block structure) which guarantee accurate recovery. Verifiability of our conditions not only leads to efficiently computable bounds for the recovery error but also allows us to optimize these error bounds with respect to the method parameters, and therefore construct estimators with improved statistical properties. To justify our approach, we also provide an oracle inequality, which links the properties of the proposed recovery algorithms and the best estimation performance. Furthermore, utilizing these verifiable conditions, we develop a computationally cheap alternative to block-${\ell }_1$ minimization, the non-Euclidean Block Matching Pursuit algorithm. We close by presenting a numerical study to investigate the effect of different block regularizations and demonstrate the performance of the proposed recoveries.

Published in at http://dx.doi.org/10.1214/12-AOS1057 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (9)

• Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• On the conditions used to prove oracle results for the Lasso
• Consistency of the group Lasso and multiple kernel learning
• Block-Sparse Recovery via Convex Optimization
• On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing
• Near-Oracle Performance of Greedy Block-Sparse Estimation Techniques from Noisy Measurements
• Accuracy guarantees for L1-recovery
• Verifiable conditions of ${\ell }_1$-recovery of sparse signals with sign restrictions
• Accuracy guaranties for ${\ell }_1$ recovery of block-sparse signals

Cited by in corpus (4)

• On asymptotically optimal confidence regions and tests for high-dimensional models
• Accuracy guaranties for ${\ell }_1$ recovery of block-sparse signals
• Parameter Choices for Sparse Regularization with the ${\ell }_1$ Norm
• High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms