The parameter estimation of damped sinusoidal signals is an important issue in spectral analysis and many applications. The existing algorithms, such as the KT algorithms [8] and the TLS algorithms [13], are based on the low-rank approximation of prediction matrix, which ignores the Hankel property of the prediction matrix. We will prove in this paper that the performance of parameter estimation can be improved if both rank- deficient and Hankel properties of the prediction matrix are exploited in the matrix approximation. Based on this idea, a modified KT (MKT) algorithm and a super resolution algorithm- damped MUSIC (DMUSIC) algorithm are proposed. Computer simulation results demonstrate that, compared with the original KT algorithm, the MKT and MUSIC algorithms have about 5dB lower noise threshold and can estimate the parameters of signal with larger damping factors.