Fast and Efficient 2-D and $K$-D DFT-Based Sinusoidal Frequency Estimation
Veyis Solak, Sultan Aldırmaz-Çolak, Ahmet Serbes
Abstract
Frequency estimation of a 2-D complex sinusoid under white Gaussian noise is a significant problem having a wide range of applications from signal processing, radar/sonar to wireless communications. This paper proposes two novel and fast DFT-based algorithms for the frequency estimation of 2-D complex sinusoids. The proposed algorithms employ <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$q$</tex-math></inline-formula> -shifted DFT coefficients of the signal that correspond to interpolating the signal by a factor of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$1/|q|$</tex-math></inline-formula> without actually performing zero-padding, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$q\in [-0.5,0.5]$</tex-math></inline-formula> . We show that the first algorithm is asymptotically efficient since it achieves the asymptotic Cramér-Rao bound (CRB) when the DFT shift parameter and the number of iterations are selected appropriately for large signal size. We propose strict bounds on the selection of these parameters for overall asymptotic efficiency. Then, based on the first algorithm, we propose a second algorithm which also performs on the CRB for both small and large signal lengths. The total computational cost of both of the proposed algorithms is in the order of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">${\mathcal O}(N_{1} N_{2} \log N_{1} \log N_{2})$</tex-math></inline-formula> , where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$N_{1}$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$N_{2}$</tex-math></inline-formula> are the size of the signal. Finally, we generalize the second algorithm to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$K$</tex-math></inline-formula> -dimensions, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$K$</tex-math></inline-formula> is any integer larger than one. Comprehensive simulation results confirm all of our theoretical derivations, and also show that our algorithms outperform existing algorithms.