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.
Acoustics, Speech, and Signal Processing (icassp), International Conference on, 2013, p. 5710-5714
Main Research Area:
I E E E International Conference on Acoustics, Speech and Signal Processing. Proceedings
IEEE International Conference on Acoustics, Speech and Signal ProcessingInternational Conference on Acoustics, Speech and Signal Processing, 2013