Journal of Systems Engineering and Electronics ›› 2009, Vol. 20 ›› Issue (4): 883-888.

• SOFTWARE ALGORITHM AND SIMULATION • Previous Articles     Next Articles

Fast M-fold matching pursuit algorithm for image approximation

Gan Tao, He Yanmin & Zhu Weile   

  1. School of Electronic Engineering, Univ. of Electronic Science and Technology of China, Chengdu 610054, P. R. China.
  • Online:2009-08-14 Published:2010-01-03


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.