Concerning the huge calculation of sparse decomposition, a fast sparse decomposition algorithm with low computation complexity was proposed for first-order Polynomial Phase Signals (PPS). In this algorithm, firstly,two concatenate dictionaries including Df and Dp were constructed, and the atoms in the Df were constructed by the frequency, and the atoms in the Dp were constructed by the phase.Secondly, for the dictionary Df, the group testing was used to search the atoms that matched the signal, and the correlation values of the atoms and the signal were tested twice to achieve the reliability. Finally, according to the matching frequency atoms tested by group testing, the dictionary Dp was constructed, and the matching phase atoms were searched by Matching Pursuit (MP) algorithm. Therefore, the sparse decomposition of real first-order PPS was finished. The simulation results show that the computational efficiency of the proposed algorithm is about 604 times as high as that of matching pursuit and about 139 times as high as that of genetic algorithm, hence the presented algorithm has less computation complexity, and can finish sparse decomposition fast. The complexity of the algorithm is only O(N).