A Remark on the Restricted Isometry Property in Orthogonal Matching Pursuit
This paper demonstrates that if the restricted isometry constant delta(K+1) of the measurement matrix A satisfies delta(K+1) < 1/root K + 1 then a greedy algorithm called Orthogonal Matching Pursuit (OMP) can recover every K-sparse signal x in K iterations from Ax. By contrast, a matrix is also constructed with the restricted isometry constant delta(K+1) = 1/root K such that OMP can not recover some K-sparse signal x in K iterations. This result positively verifies the conjecture given by Dai and Milenkovic in 2009.
restricted isometry property orthogonal matching pursuit compressed sensing sparse signal reconstruction