# Adaptive Sparse Cyclic Coordinate Descent for Sparse Frequency Estimation
## 1 Introduction  
Parametric frequency estimation has been an active research area for many years. As a consequence, several methods have been proposed in the literature for addressing this problem. Among the most classic estimation strategies are the multiple signal classification (MUSIC) [1], its extension Root-MUSIC [2], and the estimation of signal parameters via rotational invariance techniques (ESPRIT) [3]. The principal drawback of these algorithms is their high computational complexity due to the required computation of the eigenvalue decomposition (EVD) of the measurement signal's covariance matrix [4, 5]. Furthermore, a degradation of the performance in scenarios with low signal to noise ratios (SNRs) can be also observed. Some approaches found in the literature, e.g., the work proposed in [6] for source localization, inspired the application of sparse representations in frequency estimation as an alternative method for overcoming the limitations of the classic techniques. As a consequence, some algorithms that exploit the sparse nature of the signals in the frequency domain have been introduced [7, 8, 9, 10] in the literature. These methods rely on the sparse representation of the model. This means that the model assumes that the signal can be well-approximated as a linear combination of just a few underlying functions from a known basis or dictionary. Previous works based on these concepts using structured and dynamic dictionaries [11] have also been proposed. These algorithms have significant advantages, such as better performance compared with classic methods, less computational complexity, and more accurate results in scenarios with fewer available measurements. The frequency estimation problem can be modeled as a linear combination of complex exponentials in the presence of noise via the following model:  
\[b[m]=\sum_{q=1}^{p}x_{q}e^{2\pi f_{q}m}+w[m] \tag{1}\]where the coefficients \(x_{q}\) represent the (complex) amplitudes, and \(f_{q}\) are the frequencies of the signals. \(w[m]\) represents the noise samples and \(p\) is the number of frequencies that are assumed to be known in this work. Frequency estimation can be also formulated as a sparse representation problem using a sparse vector \(\mathbf{x}\) of amplitudes, where the signal model in (1) can be rewritten using a frequency grid with a spacing of \(\Delta_{f}\):  
\[\mathbf{b}=\mathbf{A}\mathbf{x}+\mathbf{w}. \tag{2}\]  
\(\mathbf{b}\) represents the measurement vector of values \(b[m]\), we the noise vector of values \(w[m]\), and \(\mathbf{A}\) is a \(M\times N\) matrix with columns \(\mathbf{a}_{*,i}\!=\! [e^{\!\beta\pi i\Delta_{f}0},\ldots,e^{\!\beta\pi i\Delta _{f}m},\ldots,e^{\!\beta\pi i\Delta_{f}M-1}]^{T}\). The measurement matrix \(\mathbf{A}\) can be seen as a dictionary in which the columns represent complex exponentials with frequencies corresponding to points on a frequency grid. We assume normalized frequencies, i.e., a sampling frequency \(f_{s}=1\) resulting in \(f_{s}/2=0.5\), which naturally results in a number of columns \(N=0.5/\Delta_{f}\) (assuming for simplicity that this fraction is an integer). For achieving high-precision estimation results, one should select a small \(\Delta_{f}\), which leads to a large number of columns of \(\mathbf{A}\), typically larger than the number of measurements \(M\)[12]. This representation encourages the use of sparse recovery algorithms. We present an approach that exploits this representation, leading to an algorithm that can be implemented efficiently in digital hardware, and is based on low complex coordinate rotation digital computer (CORDIC) operations. The proposed method is an extension of the sparse cyclic coordinate descent (SCCD) algorithm that significantly reduces the complexity further, allowing for efficient hardware implementations even for a large number of measurements. In contrast to, e.g., the Root-MUSIC algorithm that we will use for performance comparison, its complexity scales only quadratically in the number of measurements.