A Sharp Condition for Exact Support Recovery of Sparse Signals With Orthogonal Matching Pursuit
share
Support recovery of sparse signals from noisy measurements with orthogonal matching pursuit (OMP) has been extensively studied in the literature. In this paper, we show that for any K-sparse signal , if the sensing matrix satisfies the restricted isometry property (RIP) of order K + 1 with restricted isometry constant (RIC) δ_K+1 < 1/√(K+1), then under some constraint on the minimum magnitude of the nonzero elements of , the OMP algorithm exactly recovers the support of from the measurements =+ in K iterations, where is the noise vector. This condition is sharp in terms of δ_K+1 since for any given positive integer K≥ 2 and any 1/√(K+1)≤ t<1, there always exist a K-sparse and a matrix satisfying δ_K+1=t for which OMP may fail to recover the signal in K iterations. Moreover, the constraint on the minimum magnitude of the nonzero elements of is weaker than existing results.
READ FULL TEXT