Abstract: In this paper, after study of Matching Pursuit (MP) based signal sparse decomposition, a new sparse decomposition algorithm is presented based on analysis of structure property of the over-complete atom dictionary used in signal sparse decomposition. By making use of the structure property, firstly this new algorithm balances very well computers speed and memory. Then this algorithm converts very time-consuming inner product calculations in sparse decomposition into crosscorrelation calculations that are fast done by FFT. Therefore the new algorithm improves a lot the speed of signal sparse decomposition. Finally the experimental results show that the performance of the proposed algorithm is very good.