A Sharp Condition for Exact Support Recovery of with Orthogonal Matching Pursuit

Abstract

Support recovery of sparse signals from noisy measurements with orthogonal matching pursuit (OMP) has been extensively studied. In this paper, we show that for any $K$-sparse signal $\x$, if a sensing matrix $\A$ satisfies the restricted isometry property (RIP) with restricted isometry constant (RIC) ${\delta }_{K+1}<1/\sqrt{K+1}$, then under some constraints on the minimum magnitude of nonzero elements of $\x$, OMP exactly recovers the support of $\x$ from its measurements $\y=\A\x+\v$ in $K$ iterations, where $\v$ is a noise vector that is ${\ell }_2$ or ${\ell }_{\infty }$ bounded. This sufficient condition is sharp in terms of ${\delta }_{K+1}$ since for any given positive integer $K$ and any $1/\sqrt{K+1}\le \delta <1$, there always exists a matrix $\A$ satisfying the RIP with ${\delta }_{K+1}=\delta$ for which OMP fails to recover a $K$-sparse signal $\x$ in $K$ iterations. Also, our constraints on the minimum magnitude of nonzero elements of $\x$ are weaker than existing ones. Moreover, we propose worst-case necessary conditions for the exact support recovery of $\x$, characterized by the minimum magnitude of the nonzero elements of $\x$.

Jinming Wen, Zhengchun Zhou, Jian Wang, Xiaohu, Tang and Qun Mo. A Sharp Condition for Exact Support Recovery with Orthogonal Matching Pursuit, IEEE Transactions on Signal Processing, 65(2017),1370-1382

References in corpus (3)

• Support Recovery with Orthogonal Matching Pursuit in the Presence of Noise: A New Analysis
• A Sharp Restricted Isometry Constant Bound of Orthogonal Matching Pursuit
• Improved Bounds on the Restricted Isometry Constant for Orthogonal Matching Pursuit

Cited by in corpus (13)

• Nearly Optimal Bounds for Orthogonal Least Squares
• Underwater Source Localization Using TDOA and FDOA Measurements with Unknown Propagation Speed and Sensor Parameter Errors
• A New Analysis for Support Recovery with Block Orthogonal Matching Pursuit
• Signal-Dependent Performance Analysis of Orthogonal Matching Pursuit for Exact Sparse Recovery
• Compressive Spectrum Sensing Using Sampling-Controlled Block Orthogonal Matching Pursuit
• Sharp Sufficient Conditions for Stable Recovery of Block Sparse Signals by Block Orthogonal Matching Pursuit
• Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors
• Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models
• Orthogonal Matching Pursuit with Tikhonov and Landweber Regularization
• Exact Sparse Signal Recovery via Orthogonal Matching Pursuit with Prior Information
• A New Bound on Approximate Support Recovery
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors
• A Quasi-Orthogonal Matching Pursuit Algorithm for Compressive Sensing