The main obstacle to the application of image sparse representation nowadays is the enormous computational complexity.Based on the estimation of the dictionary cross-correlation information

an improved matching pursuit algorithm is proposed for image approximation.At each iteration

the adaptive prediction is introduced to effectively reduce the inner product computation load.Meanwhile

the number of iterations is decreased significantly by picking a group of atoms at a time.As a result

the total computational complexity is greatly reduced.Experimental results show that the proposed algorithm yields a significant speed improvement over the original one

while maintaining the approximation quality.For instance

it achieves a speed-up gain of near 43 times when performing 800 atoms decomposition.The algorithm is applied to image coding and shown to provide results comparable to JPEG2000 at low bitrate.