A sharp RIP condition for orthogonal matching pursuit (Q2015581)

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