# Adaptive Sparse Cyclic Coordinate Descent for Sparse Frequency Estimation
## 2 Adaptive-Sparse Coordinate Descent Algorithm
Please note that Adaptive-SCCD showed about the same performance as the original version of SCCD. This validates our affirmation that the adaptive reduction of the frequency grid size does not affect the final performance. Both versions of SCCD also outperformed the Root-MUSIC, ESPRIT, DTFT, and TwIST algorithms for this test case. In the case of the DTFT, it is known that in the presence of multiple frequencies, the DTFT suffers from spectral leakage due to interference among the sinusoidal components [29], which causes it to become biased [30]. Its inferior performance in this scenario was expected. In the case of the subspace techniques, Root-MUSIC showed the best performance compared to ESPRIT and is comparable in performance to Adaptive-SCCD. The performance gap between Root-MUSIC and ESPRIT is due to the fact that they work in different subspaces: Root-MUSIC works in the noise subspace with dimensions \(M-p\), and ESPRIT works in the signal subspace with dimension \(p\). Moreover, TwIST is an interesting approach based on the iterative shrinkage/thresholding (IST) algorithm that was originally proposed for image restoration, but we can notice that its performance for the simulated scenario of frequency estimation was inferior to Root-MUSIC and the proposed method. We also analyzed how the selection of \(\Delta_{\text{fcoarse}}\) affects the final performance. We experimentally determined that a minimum spacing \(\Delta_{\text{fcoarse}}=(1/2M)\) is necessary to guarantee the same final performance than SCCD. Figure 4 shows the performance of the original formulation versus the adaptive version for different values of \(\Delta_{\text{fcoarse}}\). In the simulations, \(\Delta_{\text{fcoarse}}=\text{factor}\;\cdot(1/(20M))\). This is the reason why the figure is represented as a function of the factors. In the case of SCCD, the spacing of the grid \(\Delta_{f}=1/(20M)\) was always the same for all simulations. Note that for values of \(\Delta_{\text{fcoarse}}>(1/2M)\), i.e., factor values greater than 10, the performance of Adaptive-SCCD was worse than the performance of SCCD. This behavior was due to the fact that large values of \(\Delta_{\text{fcoarse}}\) lead to a very coarse frequency grid. This produces scenarios with \(M>N\) or even \(N\leq p\), where the coarse estimation fails to find all the intervals of interest (i.e., some parts of the grid where the true frequencies are located can not be detected in the coarse search). Therefore, some of these intervals of interest were excluded in the fine frequency grid. As a consequence, the Adaptive-SCCD algorithm was unable to estimate the true frequencies in the fine search. Figure 3: MSE versus SNR for \(p=5\) normalized frequencies. As expected, we also observed in the simulation results that for larger values of \(M\), the final performance improved, but we must consider that the increase of \(M\) also had an impact on the number of overall required computations. In [12], we outlined that the Algorithm 1 can be efficiently implemented in hardware using the CORDIC algorithm. In order to evaluate how the increase of the number of measurements impacts the complexity of such an implementation, we provide Figure 5.

Figure 5 shows the average numbers of required CORDIC operations of SCCD and Adaptive-SCCD for different numbers of measurements. We considered the total number of iterations until the algorithms finished. A second-order polynomial in \(M\) has been used to

Figure 4: MSE versus factors for a scenario with SNR = 10 dB and \(p=5\) normalized frequencies. Figure 5: CORDIC operations versus \(M\) for a scenario with SNR = 10 dB, \(p=5\) normalized frequencies, and \(\Delta_{f\text{coarse}}=1/4M\). For analyzing the complexity of the algorithms, a second-order polynomial in \(M\) was used. In addition, a linear fitting is also provided for Adaptive-SCCD. fit the points with resulting \(R^{2}\) (R-squared) values of 0.9988 and 0.9997 for Adaptive-SCCD and SCCD, respectively.