Abstract: It is one of themain problems in signal decomposition in over-complete dictionary that the atom construction process is very slow. To solve this problem, a new fast algorithm was proposed. In the algorithm, all atoms are divided into two categories: small and large atoms, according to their scales. Because the energy of a small atom concentrates in a small region of the whole atom, it is constructed within the region ofenergy concentration, and thewhole atom is represented by the locally constructed atom. A large atom is constructed by interpolation after a corresponding small atom has been constructed. Experimental results show tha,t when the length of the signal is 256, the proposed algorithm is 4. 7 times faster than traditionalmethodswith the same signal quality.