A Sharp Restricted Isometry Constant Bound of Orthogonal Matching Pursuit

Abstract

We shall show that if the restricted isometry constant (RIC) ${\delta }_{s+1}(A)$ of the measurement matrix $A$ satisfies $${\delta }_{s+1}(A)<\frac{1}{\sqrt{s+1}},$$ then the greedy algorithm Orthogonal Matching Pursuit(OMP) will succeed. That is, OMP can recover every $s$-sparse signal $x$ in $s$ iterations from $b=Ax$. Moreover, we shall show the upper bound of RIC is sharp in the following sense. For any given $s\in \mathbb{N}$, we shall construct a matrix $A$ with the RIC $${\delta }_{s+1}(A)=\frac{1}{\sqrt{s+1}}$$ such that OMP may not recover some $s$-sparse signal $x$ in $s$ iterations.

arXiv comment8 pages, submitted to the IEEE Transactions on Information Theory

References in corpus (1)

• New Coherence and RIP Analysis for Weak Orthogonal Matching Pursuit

Cited by in corpus (13)

• A Sharp Condition for Exact Support Recovery of with Orthogonal Matching Pursuit
• Nearly Optimal Bounds for Orthogonal Least Squares
• A Tight Bound of Hard Thresholding
• On The Exact Recovery Condition of Simultaneous Orthogonal Matching Pursuit
• Signal-Dependent Performance Analysis of Orthogonal Matching Pursuit for Exact Sparse Recovery
• When does OMP achieve exact recovery with continuous dictionaries?
• Sharp Sufficient Conditions for Stable Recovery of Block Sparse Signals by Block Orthogonal Matching Pursuit
• A Sharp Condition for Exact Support Recovery of Sparse Signals With Orthogonal Matching Pursuit
• Joint Sparse Recovery Using Signal Space Matching Pursuit
• A sharp recovery condition for sparse signals with partial support information via orthogonal matching pursuit
• Recovery of signals by a weighted ${\ell }_2/{\ell }_1$ minimization under arbitrary prior support information
• A Quasi-Orthogonal Matching Pursuit Algorithm for Compressive Sensing
• On the Fundamental Recovery Limit of Orthogonal Least Squares