Fast M-fold matching pursuit algorithm for image approximation

A simple and effective greedy algorithm for image approximation is proposed. Based on the matching pursuit approach, it is characterized by a reduced computational complexity benefiting from two major modifications. First, it iteratively finds an approximation by selecting M atoms instead of one at a time. Second, the inner product computations are confined within only a fraction of dictionary atoms at each iteration. The modifications are implemented very efficiently due to the spatial incoherence of the dictionary. Experimental results show that compared with full search matching pursuit, the proposed algorithm achieves a speed-up gain of 14.4∼36.7 times while maintaining the approximation quality.