A Sharp RIP Condition for Orthogonal Matching Pursuit. (19th November 2013)

• Record Type: Journal Article
• Authors: Dan, Wei
• Other Names: Pereverzyev Sergei V. Academic Editor.
• Is Part Of: Abstract and applied analysis. Volume 2013(2013)
• Publication Date: 2013-11-19
• Subjects: Mathematical analysis -- Periodicals; Mathematical analysis; Applied Mathematics; Mathematical Analysis; Periodicals; 515.05
• DOI: 10.1155/2013/482357
• Languages: English
• ISSNs: 1085-3375

Abstract

Abstract : A restricted isometry property (RIP) condition δ K + K θ K, 1 < 1 is known to be sufficient for orthogonal matching pursuit (OMP) to exactly recover every K -sparse signal x from measurements y = Φ x . This paper is devoted to demonstrate that this condition is sharp. We construct a specific matrix with δ K + K θ K, 1 = 1 such that OMP cannot exactly recover some K -sparse signals.