Abstract: In order to improve the spatial resolution and computational speed of the fast iterative shrinkage-thresholding algorithm (FISTA) in deconvolution beamforming, an acoustic model based on fast Fourier transform is adopted, and an over-relaxed method and a "greedy" restart strategy are introduced. Two improved fast iterative shrinkage-thresholding algorithms, namely the over-relaxed monotone fast iterative shrinkage-threshold algorithm based on fast Fourier transform (FFT-OMFISTA) and the "greedy" fast iterative shrinkage-thresholding algorithm based on fast Fourier transform (FFTGFISTA), are proposed and applied to the solution process of deconvolution beamforming. The simulation and experiments for single and dual sound sources are designed in this paper to verify the effectiveness and superiority of the proposed algorithms. The results show that both of the proposed algorithms have good performance, achieving higher spatial resolution and faster computational speed in sound source localization.