A Fast Greedy Sparse Approximation for Image Based on Indexed Dictionary

Orthogonal Matching Pursuit (OMP) is an effective solution to sparse approximation based on redundant dictionary, but its greed nature requires that the algorithm traverse all the atoms in a redundant dictionary every time, which can consume much CPU time. The structure of a dictionary is of paramount importance for MP performance. Different from parametric or structured dictionary, the characteristics of the atoms in learned dictionary is unknown to us and cannot be exploited to speed up. This paper presents a novel method: we first cluster all the atoms in learned dictionary by exploiting the best similar greed nature of MP and set up the index of learned dictionary in advance, and then make matching among only a part of atoms via the index. As a result, it can avoid full search while trying to keep the matching effect. Thus it expedites the execution of the algorithm immensely. Some results show that our method is about twice as fast as ordinary OMP.