Accuracy guaranties for _1 recovery of block-sparse signals

DOI10.1214/12-AOS1057zbMATH Open1296.62088arXiv1111.2546WikidataQ57392890 ScholiaQ57392890MaRDI QIDQ741817FDOQ741817

Anatoli Juditsky, Boris T. Polyak, Arkadi Nemirovski, Fatma Kılınç-Karzan

Publication date: 15 September 2014

Published in: The Annals of Statistics (Search for Journal in Brave)

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-$el{l}_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-$el{l}_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.

Full work available at URL: https://arxiv.org/abs/1111.2546

Recommendations

• Accuracy Guarantees for <formula formulatype="inline"> <tex Notation="TeX">$\ell_1$</tex></formula>-Recovery
• A simple Gaussian measurement bound for exact recovery of block-sparse signals
• Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
• A note on guaranteed sparse recovery via \(\ell_1\)-minimization
• On the Reconstruction of Block-Sparse Signals With an Optimal Number of Measurements
• Verifiable conditions of \(\ell_{1}\)-recovery for sparse signals with sign restrictions
• On Recovery of Sparse Signals Via $\ell _{1}$ Minimization
• Block-Sparse Recovery via Convex Optimization
• Estimation of block sparsity in compressive sensing

zbMATH Keywords

sparse recoveryoracle inequalitiesnonparametric estimation by convex optimization

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Estimation in multivariate analysis (62H12) Applications of mathematical programming (90C90)

Cites Work

• On the conditions used to prove oracle results for the Lasso
• Simultaneous analysis of Lasso and Dantzig selector
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Model Selection and Estimation in Regression with Grouped Variables
• The Group Lasso for Logistic Regression
• Decoding by Linear Programming
• Stable recovery of sparse overcomplete representations in the presence of noise
• DASSO: Connections Between the Dantzig Selector and Lasso
• Title not available (Why is that?)
• Oracle inequalities and optimal inference under group sparsity
• The benefit of group sparsity
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
• On the asymptotic properties of the group lasso estimator for linear models
• Some theoretical results on the grouped variables Lasso
• Sparse representations in unions of bases
• Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• The restricted isometry property and its implications for compressed sensing
• On the Reconstruction of Block-Sparse Signals With an Optimal Number of Measurements
• Support union recovery in high-dimensional multivariate regression
• Model-Based Compressive Sensing
• Robust Recovery of Signals From a Structured Union of Subspaces
• Accuracy Guarantees for <formula formulatype="inline"> <tex Notation="TeX">$\ell_1$</tex></formula>-Recovery
• Verifiable conditions of \(\ell_{1}\)-recovery for sparse signals with sign restrictions
• On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing

Cited In (4)

• High-order evaluation complexity for convexly-constrained optimization with non-Lipschitzian group sparsity terms
• On asymptotically optimal confidence regions and tests for high-dimensional models
• Parameter choices for sparse regularization with the ℓ1 norm ^*
• Group Sparse Optimization for Images Recovery Using Capped Folded Concave Functions

This page was built for publication: Accuracy guaranties for \(\ell_{1}\) recovery of block-sparse signals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q741817)