Abstract: Under sampling truncation effect, the sparse representation approximate error of smooth signal in DFT basis becomes explicit. In order to accurately obtain the sparse representation of a truncated smooth signal, an efficient and effective method was proposed. According to the signal’s frequency spectrum information, this method determines the signal subspaces, including numbers and positions, and redundantly expands these subspaces to form corresponding sub-dictionaries, which are concatenated to generate the whole dictionary. Compared to DFT basis and DFT frame, the designed redundant dictionary is adaptive to the signal and can better reflect its intrinsic characteristics. Moreover, the traditional matching pursuit algorithm is improved by employing the dictionary’s inherent tree structure. In the novel algorithm matching pursuit is divided into two levels at each iteration. The first level search, also called coarse search, is implemented to identify which sub-dictionaries the signal lives in. The second level search, which is also called precise search, is implemented to select the optimal atom at this iteration. This improved algorithm obtains the same accuracy and convergence property with the Matching Pursuit method but can reduce the search space and the computational complexity. Lastly, simulations are implemented to verify the correctness of theoretical analysis and the advantages of the method.