Coherence-Based Performance Guarantees for Estimating a Sparse Vector Under Random Noise

Abstract

We consider the problem of estimating a deterministic sparse vector x from underdetermined measurements Ax+w, where w represents white Gaussian noise and A is a given deterministic dictionary. We analyze the performance of three sparse estimation algorithms: basis pursuit denoising (BPDN), orthogonal matching pursuit (OMP), and thresholding. These algorithms are shown to achieve near-oracle performance with high probability, assuming that x is sufficiently sparse. Our results are non-asymptotic and are based only on the coherence of A, so that they are applicable to arbitrary dictionaries. Differences in the precise conditions required for the performance guarantees of each algorithm are manifested in the observed performance at high and low signal-to-noise ratios. This provides insight on the advantages and drawbacks of convex relaxation techniques such as BPDN as opposed to greedy approaches such as OMP and thresholding.

12 pages, 3 figures. Submitted to IEEE Transactions on Signal Processing

References in corpus (7)

• Simultaneous analysis of Lasso and Dantzig selector
• Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• Near-ideal model selection by ${\ell }_1$ minimization
• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
• Uncertainty Relations for Shift-Invariant Analog Signals
• On MMSE and MAP Denoising Under Sparse Representation Modeling Over a Unitary Dictionary
• The Cramer-Rao Bound for Sparse Estimation

Cited by in corpus (32)

• Structured Compressed Sensing: From Theory to Applications
• The Cosparse Analysis Model and Algorithms
• The Random Frequency Diverse Array: A New Antenna Structure for Uncoupled Direction-Range Indication in Active Sensing
• Noise Folding in Compressed Sensing
• Projection Design For Statistical Compressive Sensing: A Tight Frame Based Approach
• Perturbation Analysis of Orthogonal Matching Pursuit
• Near-Oracle Performance of Greedy Block-Sparse Estimation Techniques from Noisy Measurements
• Boosting Occluded Image Classification via Subspace Decomposition Based Estimation of Deep Features
• Successive Concave Sparsity Approximation for Compressed Sensing
• On MMSE and MAP Denoising Under Sparse Representation Modeling Over a Unitary Dictionary
• On the Performance Bound of Sparse Estimation with Sensing Matrix Perturbation
• Sparse regression algorithm for activity estimation in $\gamma$ spectrometry
• On Probability of Support Recovery for Orthogonal Matching Pursuit Using Mutual Coherence
• Proof of Convergence and Performance Analysis for Sparse Recovery via Zero-point Attracting Projection
• High Resolution Radar Sensing with Compressive Illumination
• On the SNR Variability in Noisy Compressed Sensing
• Beamspace Channel Estimation for Millimeter-Wave Massive MIMO Systems with Lens Antenna Array
• RIP-Based Near-Oracle Performance Guarantees for Subspace-Pursuit, CoSaMP, and Iterative Hard-Thresholding
• Oracle-order Recovery Performance of Greedy Pursuits with Replacement against General Perturbations
• Efficient Least Residual Greedy Algorithms for Sparse Recovery
• Coherence Statistics of Structured Random Ensembles and Support Detection Bounds for OMP
• Data recovery from corrupted observations via l1 minimization
• Sparse Signals Recovery from Noisy Measurements by Orthogonal Matching Pursuit
• Power-Constrained Sparse Gaussian Linear Dimensionality Reduction over Noisy Channels
• Recovery of Sparsely Corrupted Signals
• Large-Scale Antenna-Assisted Grant-free Non-Orthogonal Multiple Access via Compressed Sensing
• Zadoff-Chu sequence design for random access initial uplink synchronization
• Tight Recovery Guarantees for Orthogonal Matching Pursuit Under Gaussian Noise
• Relaxed Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay
• Reduced-dimension multiuser detection: detectors and performance guarantees
• The Statistical Coherence-based Theory of Robust Recovery of Sparsest Overcomplete Representation
• High SNR Consistent Compressive Sensing