Remarks on the Restricted Isometry Property in Orthogonal Matching Pursuit algorithm

Abstract

This paper demonstrates theoretically that if the restricted isometry constant ${\delta }_K$ of the compressed sensing matrix satisfies $${\delta }_{K+1}<\frac{1}{\sqrt{K}+1},$$ then a greedy algorithm called Orthogonal Matching Pursuit (OMP) can recover a signal with $K$ nonzero entries in $K$ iterations. In contrast, matrices are also constructed with restricted isometry constant $${\delta }_{K+1}=\frac{1}{\sqrt{K}}$$ such that OMP can not recover $K$-sparse $x$ in $K$ iterations. This result shows that the conjecture given by Dai and Milenkovic is ture.

we have a new version

Cited by in corpus (3)

• Orthogonal Matching Pursuit with Replacement
• Greedy type algorithms for RIP matrices. A study of two selection rules
• Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices