Behavior of greedy sparse representation algorithms on nested supports

We study the links between recovery properties of Orthogonal Matching Pursuit (OMP) and the whole General MP class for sparse signals with nested supports, i.e., supports that share an inclusion relationship. In particular, we show that the support recovery optimality of those algorithms is not locally nested: there is a dictionary and supports Γ ⊃ Γ′ such that OMP can recover all signals with support Γ, but not all signals with support Γ′. We also show that the support recovery optimality of OMP is globally nested: if OMP can recover all s-sparse signals, then it can recover all s′-sparse signals, s′ < s. We also provide a tighter version of the spark theorem, allowing us to complete a proof that sparse approximation algorithms can only be optimal for all s-sparse signals if s is strictly lower than half the spark of the dictionary.