Abstract
We prove that if Orthogonal Matching Pursuit (OMP) recovers all s-sparse signals for a given dictionary, then it also recovers all s 0 -sparse signals on the same dictionary for any s 0 < s. We also extend Tropp’s Exact Recovery Condition (ERC) to dictionaries with non-normalized atoms. Our result does not contradict an earlier result stating that there are dictionaries and cardinalities s 0 < s such that all s-size supports satisfy Tropp’s (ERC) but not all s 0 -size supports do: that result was proved using non-normalized dictionaries and in that case Tropp’s ERC is not linked to the recovery by OMP.