# Adaptive Sparse Cyclic Coordinate Descent for Sparse Frequency Estimation
## 2 Adaptive-Sparse Coordinate Descent Algorithm
This characteristic allows discarding the areas of the frequency grid that remain zero over the iterations. Then, the frequency grid can be redefined to the areas of interest where the values are nonzero. This dimensional reduction of the frequency grid considerably reduces the number of mathematical operations needed per iteration and speeds up the convergence of the algorithm. The proposed algorithm is called Adaptive-SCCD and consists of two main steps:  
* In the first step, Algorithm 1 is run using a coarse grid. This means that the defined frequency spacing of the grid \(\Delta_{f\text{coarse}}\) uses a coarse grid spacing, which leads to a moderate number of columns of \(\mathbf{A}\). After running the algorithm, the non-zero positions are detected. These positions are located in the non-zero intervals around the peaks of the estimated vector \(\hat{\mathbf{x}}\). This is the reason why we performed a peak search and detected the beginnings and ends of these intervals. * In the second step, we again run Algorithm 1, but in this case, the frequency grid is constructed only considering the intervals detected in the first step and using a frequency spacing \(\Delta_{f\text{fine}}\). This considerably reduces the number of grid points  
Figure 1: Graphic representation of the shrink function. (i.e., number of columns of the matrix **A**) that need to be considered, resulting in a reduction of the required number of mathematical operations. ```
0:\(\mathbf{b}\), \(\lambda=[\lambda_{1},\ldots,\lambda_{L}]\), \(\Delta_{f}\), \(N,\theta\), \(p\)
0:\(\hat{\mathbf{x}}\), set of detected frequencies
1:\(\hat{\mathbf{x}}^{(0)}\leftarrow\mathbf{0}\)
2:\(\mathbf{r}\leftarrow\mathbf{b}\)
3:\(l=1\)\(\triangleright\) Index for \(\lambda\)
4:for\(k=1...K\)do\(\triangleright\)\(K\) as pre-set maximum of iterations
5:\(i\leftarrow((k-1)\bmod N)+1\)\(\triangleright\) cyclic processing
6:\(\mathbf{a}_{s,j}=[e^{2\pi i\Delta_{s}0},\ldots,e^{2\pi i\Delta_{j}m},\ldots,e^ {2\pi i\Delta_{j}M-1}]^{T}\)
7:\(\mu_{i}\gets 1/\left\|\mathbf{a}_{s,j}\right\|_{2}^{2}=1/M\)
8:\(\hat{\mathbf{x}}_{i}^{(k)}\leftarrow\text{shrink}(\hat{x}_{i}^{(k-1)}+\mu_{i} \mathbf{a}_{s,j}^{H}\mathbf{r},\mu_{i}\lambda_{l})\)
9:\(\mathbf{r}\leftarrow\mathbf{r}-\mathbf{a}_{i}(\hat{x}_{i}^{(k)}-\hat{x}_{i}^{( k-1)})\)
10:if\(i=1\)and\(\left\|\hat{\mathbf{x}}^{k}-\hat{\mathbf{x}}^{k-1}\right\|_{1}<\theta\)then
11:\(P=\text{AbsPeakPositions}(\hat{\mathbf{x}}^{k})\)
12:if\(|P|<p\)then
13:\(l\leftarrow\text{min}(L,l+1)\)
14:else return frequencies corresponding to \(P\)
15:endif
16:endif
17:endfor
```  
**Algorithm 1** Sparse cyclic coordinate descent (SCCD) for frequency estimation [12]  
The two main steps of the proposed algorithm are illustrated in Figure 2. The main advantage of this approach is that the first estimation (coarse search) allows finding intervals centered around the peaks. These intervals can be interpreted as the potential regions of the grid where the true frequencies can be located. Then, the size of the frequency grid is effectively reduced in the second step (fine search) by only considering the intervals detected before. As a consequence, the number of points of interest that need to be evaluated in the second step is reduced and the number of required mathematical operations also decreases. The pseudocode of Adaptive-SCCD is described in Algorithm 2, where FindNonZeroPositions and BuildGrid are auxiliary functions. Note that in Figure 2, the intervals centered around the peaks of the absolute value of the estimated vector \(\hat{\mathbf{x}}\) correspond to the non-zero positions. The function FindNonZeroPositions finds the start and end values of these peaks and stores them in the vectors \(\mathbf{s}\) and \(\mathbf{e}\). The function is described in Algorithm 3. The function BuildGrid is used to build a fine frequency grid in the intervals found by the coarse estimation. The fine grid uses the frequency spacing \(\Delta_{\text{fine}}\). It is described in more detail in Algorithm 4.