# Adaptive Sparse Cyclic Coordinate Descent for Sparse Frequency Estimation
## 2 Adaptive-Sparse Coordinate Descent Algorithm
Finally, the function SCCD_fine is used for estimating the frequency parameters using the fine frequency grid. This function is similar to the original one described in Algorithm 1, only the inner product of line 8 is now performed by only considering the non-zero intervals detected in the first run of SCCD. Then, for implementing the function SCCD_fine, the lines 5 and 6 in Algorithm 1 are replaced by ```
1:\(\mathbf{b}\), \(\lambda=[\lambda_{1},\ldots,\lambda_{L}]\), \(\theta\), \(p\), \(\Delta_{f}\), \(\Delta_{\text{coarse}}\)
2:set of detected frequencies \(\mathbf{\hat{z}}\)
3:\(N=0.5/\Delta_{\text{coarse}}\)
4:\([\mathbf{\hat{x}}]\)= SCCD (\(\mathbf{b}\), \(\lambda\),\(\Delta_{f\text{coarse}}\),\(N,\theta,p\))
5:\([\mathbf{s},\mathbf{e}]\)= FindNonZeroPositions\((\mathbf{\hat{x}},\Delta_{f\text{coarse}})\)
6:\(\Delta_{\text{fine}}=\Delta_{f}\)
7:\(\text{grid\_fine}=\text{BuildGrid}(\mathbf{s},\mathbf{e},\Delta_{\text{fine}})\)
8:\(N=\text{size}(\text{grid\_fine})\)
9:\([\mathbf{\hat{x}}_{\text{fine}},\mathbf{\hat{f}}]\)= SCCD_fine(\(\mathbf{b}\), \(\lambda\),\(\text{grid\_fine}\),\(N,\theta,p\))
```

**Algorithm 2** Adaptive-SCCD for frequency estimation

```
1:\(\mathbf{\hat{x}},\Delta_{f\text{coarse}}\)
2:\(\mathbf{s},\mathbf{e}\)
3:\(f_{\text{grid}}=0:\Delta_{f\text{coarse}}:0.5\)
4:\([\text{pks},\text{loc}]=\text{AbsPeakPositions}(\mathbf{\hat{x}})\)
5:\(\mathbf{\hat{x}}=\text{abs}(\mathbf{\hat{x}})\)
6:\(\text{dx}=[0\text{ diff}(\mathbf{\hat{x}})]\)
7:\(P=\text{length(pks)}\)
8:\(\text{start}=\text{zeros}(P,1)\)
9:\(\text{end}=\text{zeros}(P,1)\)
10:\(\text{\bf for}=1...P\)do
11:\(\text{start}=\text{find}((f_{\text{grid}}<f_{\text{grid}}(\text{loc}(k)))\) & \((\text{dx}<=0))\)
12:if isempty(start) then
13:\(\text{start}\)=1
14:endif
15:\(\mathbf{s}(k)=\text{start}\)
16:\(\text{end}=\text{find}((f_{\text{grid}}>f_{\text{grid}}(\text{loc}(k)))\) & \((\text{dx}>=0))\)
17:if isempty(end) then
18:\(\text{end}\)=1
19:endif
20:\(\mathbf{e}(k)=\text{end}\)
21:endfor
```

**Algorithm 3** FindNonZeroPositions

## 3 Results

The performance of our method in the following estimation scenarios is evaluated in terms of the mean square error (MSE). \[\text{MSE}=\frac{1}{Rp}\sum_{r=1}^{R}\sum_{i=1}^{p}|\hat{f}_{i,r}-f_{i}|^{2} \tag{4}\]

between the correct frequencies \(f_{i}\), \(i=1,2,\ldots,p\) and their estimates \(\hat{f}_{i,r}\) in \(R=1000\) runs. The measurement noise samples were drawn from an i.i.d. complex Gaussian random process with zero mean and variance \(\sigma^{2}\). The measurements have been created by summing \(p\) real sinusoids with phase \(\phi\) uniformly distributed at random in the interval \((0,2\pi)\) and the amplitudes were chosen randomly to be \(-1\) or \(1\) for all the simulations. The vector \(\lambda\) is defined as \(\lambda=[\lambda_{\max},\varepsilon\lambda_{\max},\varepsilon^{2}\lambda_{ \max},\ldots,\varepsilon^{(L-1)}\lambda_{\max}]\) where \(\epsilon=0.99\) and \(L=50\). In the case of SCCD, we considered a frequency grid with a spacing of \(\Delta_{f}=1/(20M)\), and for Adaptive-SCD we consider a coarse grid with \(\Delta_{f\text{coarse}}=1/(2M)\) for the first step and in the second step a spacing equal to the original version (i.e., \(\Delta_{f\text{fine}}=\Delta_{f}=1/(20M)\)). We also included the following algorithms for comparison: Root-MUSIC; ESPRIT, whose code is available in [26]; discrete-time Fourier transform (DTFT); and the two-step iterative shrinkage/thresholding (TwIST) algorithm [27], whose code is available in [28]. The simulation results for Root-MUSIC were obtained using the function rootmusic built in MATLAB and considering autocorrelation matrices of size \(M/2\times M/2\) for Root-MUSIC and also for ESPRIT. In the case of the algorithm TwIST, the parameter \(\tau\) was set to \(5\). Figure 2: Overall description of the principal steps of the Adaptive-SCD algorithm. Figure 3 depicts a scenario with \(M=50\) and five frequencies selected at random from the interval \((0,0.5)\).