Support Recovery with Orthogonal Matching Pursuit in the Presence of Noise: A New Analysis

Abstract

Support recovery of sparse signals from compressed linear measurements is a fundamental problem in compressed sensing (CS). In this paper, we study the orthogonal matching pursuit (OMP) algorithm for the recovery of support under noise. We consider two signal-to-noise ratio (SNR) settings: i) the SNR depends on the sparsity level $K$ of input signals, and ii) the SNR is an absolute constant independent of $K$. For the first setting, we establish necessary and sufficient conditions for the exact support recovery with OMP, expressed as lower bounds on the SNR. Our results indicate that in order to ensure the exact support recovery of all $K$-sparse signals with the OMP algorithm, the SNR must at least scale linearly with the sparsity level $K$. In the second setting, since the necessary condition on the SNR is not fulfilled, the exact support recovery with OMP is impossible. However, our analysis shows that recovery with an arbitrarily small but constant fraction of errors is possible with the OMP algorithm. This result may be useful for some practical applications where obtaining some large fraction of support positions is adequate.

13 pages

Cited by in corpus (11)

• A Sharp Condition for Exact Support Recovery of with Orthogonal Matching Pursuit
• Mobility-Aware Uplink Interference Model for 5G Heterogeneous Networks
• Compressive Spectrum Sensing Using Sampling-Controlled Block Orthogonal Matching Pursuit
• Optimization of light fields in ghost imaging using dictionary learning
• Recovery of Sparse Signals Using Multiple Orthogonal Least Squares
• Tuning Free Orthogonal Matching Pursuit
• Signal and Noise Statistics Oblivious Sparse Reconstruction using OMP/OLS
• Orthogonal Matching Pursuit with Tikhonov and Landweber Regularization
• High SNR Consistent Compressive Sensing
• A New Bound on Approximate Support Recovery
• On the Fundamental Recovery Limit of Orthogonal Least Squares