Remarks on the Restricted Isometry Property in Orthogonal Matching Pursuit algorithm

This paper demonstrates theoretically that if the restricted isometry constant $δ_K$ of the compressed sensing matrix satisfies $δ_{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 $δ_{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.

No reviews yet.

No comments yet.