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.

8 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 (4)

• Signal-Dependent Performance Analysis of Orthogonal Matching Pursuit for Exact Sparse Recovery
• 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