How well can we estimate a sparse vector?

DOI10.1016/J.ACHA.2012.08.010MaRDI QIDQ1940130zbMATH OpenOpenAlexFDO

Authors Emmanuel J. Candès, Mark A. Davenport

Publication date 5 March 2013

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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

zbMATH Keywords

compressive sensingfano's inequalitymatrix Bernstein inequalityminimax lower boundssparse estimationsparse linear regression

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: The estimation of a sparse vector in the linear model is a fundamental problem in signal processing, statistics, and compressive sensing. This paper establishes a lower bound on the mean-squared error, which holds regardless of the sensing/design matrix being used and regardless of the estimation procedure. This lower bound very nearly matches the known upper bound one gets by taking a random projection of the sparse vector followed by an $el{l}_1$ estimation procedure such as the Dantzig selector. In this sense, compressive sensing techniques cannot essentially be improved.

Recommendations

• Sparsity and incoherence in compressive sampling
• The restricted isometry property and its implications for compressed sensing
• Lower bounds for sparse recovery
• Improved bounds for sparse recovery from subsampled random convolutions
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

Cited in

(17)

• An analysis of the SPARSEVA estimate for the finite sample data case
• A strong converse bound for multiple hypothesis testing, with applications to high-dimensional estimation
• Slope meets Lasso: improved oracle bounds and optimality
• Greedy variance estimation for the LASSO
• Error bounds for compressed sensing algorithms with group sparsity: A unified approach
• Estimation and variable selection with exponential weights
• Geometric inference for general high-dimensional linear inverse problems
• Multi-receivers and sparse-pixel pseudo-thermal light source for compressive ghost imaging against turbulence
• Book Review: A mathematical introduction to compressive sensing
• Nearly optimal minimax estimator for high-dimensional sparse linear regression
• High-dimensional estimation with geometric constraints
• Adaptive sensing performance lower bounds for sparse signal detection and support estimation
• Estimation of block sparsity in compressive sensing
• Learning sparse classifiers: continuous and mixed integer optimization perspectives
• Bayesian compressive sensing using generative models
• A note on the minimax risk of sparse linear regression
• High-probability minimax lower bounds

This page was built for publication: How well can we estimate a sparse vector?

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