Accuracy guarantees for L1-recovery

Abstract

We discuss two new methods of recovery of sparse signals from noisy observation based on ${\ell }_1$- minimization. They are closely related to the well-known techniques such as Lasso and Dantzig Selector. However, these estimators come with efficiently verifiable guaranties of performance. By optimizing these bounds with respect to the method parameters we are able to construct the estimators which possess better statistical properties than the commonly used ones. We also show how these techniques allow to provide efficiently computable accuracy bounds for Lasso and Dantzig Selector. We link our performance estimations to the well known results of Compressive Sensing and justify our proposed approach with an oracle inequality which links the properties of the recovery algorithms and the best estimation performance when the signal support is known. We demonstrate how the estimates can be computed using the Non-Euclidean Basis Pursuit algorithm.

References in corpus (10)

• On the conditions used to prove oracle results for the Lasso
• The sparsity and bias of the Lasso selection in high-dimensional linear regression
• Lasso-type recovery of sparse representations for high-dimensional data
• Sparsity oracle inequalities for the Lasso
• The Dantzig selector and sparsity oracle inequalities
• Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing
• Nonparametric estimation by convex programming
• Verifiable conditions of ${\ell }_1$-recovery of sparse signals with sign restrictions

Cited by in corpus (6)

• A weighted L1-minimization approach for sparse polynomial chaos expansions
• On the Prediction Performance of the Lasso
• On Polynomial Chaos Expansion via Gradient-enhanced ${\ell }_1$-minimization
• Quasi-Likelihood and/or Robust Estimation in High Dimensions
• Accuracy guaranties for ${\ell }_1$ recovery of block-sparse signals
• Sparse Recovery from Extreme Eigenvalues Deviation Inequalities