# Adaptive Sparse Cyclic Coordinate Descent for Sparse Frequency Estimation
## 2 Adaptive-Sparse Coordinate Descent Algorithm  
The SCCD algorithm solves the following cost function:  
\[\arg\min_{\mathbf{x}}\frac{1}{2}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{2}^{2}+ \lambda\|\mathbf{x}\|_{1}, \tag{3}\]  
where the regularization parameter \(\lambda\) is used to adjust the sparsity of the estimation result. Higher values of \(\lambda\) lead to more sparse estimation results [12]. An interesting phenomenon occurs over the iterations in SCCD: most coordinates at each update that are zero never become nonzero [22]. This characteristic allows using different strategies to speed up the convergence of the algorithm. For example, one can use a vector of lambda in descending order instead of a fixed \(\lambda\)[25]. Then, the estimation result of a higher \(\lambda\) is used as the start value for the next estimation with a lower \(\lambda\). Such a hot-starting strategy reduces the computational effort to obtain a whole solution path because the result of such a previous estimation provides a start vector for the next estimation that is typically closer to its solution than the all-zero vector. As a consequence, the computation of the final solution is considerably faster than computing the solution using a fixed arbitrary \(\lambda\). In [12], we proposed a version of SCCD for frequency estimation, where a decreasing strategy for updating the regularization parameter and a peak search are used for detecting the \(p\) frequencies exactly. This is repeated in Algorithm 1 for the reader's convenience. Algorithm 1 starts with a \(\lambda\)-value that would lead to the all-zero solution (i.e., \(\lambda_{1}=\lambda_{\text{max}}\) where \(\lambda_{\text{max}}=\max_{i}|\mathbf{a}_{*,i}^{H}\mathbf{y}|\)) [12] and reduces \(\lambda\) until the number of estimated frequencies matches the desired number of frequencies \(p\). For this, we use a vector of descending entries: \(\lambda=[\lambda_{1}=\lambda_{\text{max}},\lambda_{2},\ldots,\lambda_{L}]\). The iteration process basically consists of two principal steps. In the first step (line 8), the inner product between the corresponding column \(\mathbf{a}_{*,i}\) and the residual \(\mathbf{r}\) is computed and added to the currently estimated vector. Then, the resulting value is passed as the argument to the shrink function. The shrink function outputs zero if its input is smaller than a defined threshold (i.e., in our case smaller than \(\mu_{i}\lambda_{l}\)). If the input is larger than the threshold, the magnitude of the input is reduced by the threshold value. Figure 1 graphically depicts the shrink function. After applying the shrink function, the second step (line 9) of Algorithm 1 updates the residual. In order to find an estimated vector with exactly \(p\) nonzero values that correspond to the true frequencies, a very fine grid of \(\lambda\) values are required. This also implies a considerable increase in the number of iterations. In order to address this issue, a peak search on the estimated vector can be performed (line 11 of Algorithm 1). This allows detecting \(p\) frequencies, even when the number of nonzero elements of the estimated vector is larger than \(p\). This strategy also allows using a relatively coarse vector of \(\lambda\) values while still providing good estimation performance. The vector \(\mathbf{a}_{*,i}\) in Algorithm 1 is composed of complex exponentials. Therefore, the inner product of such a vector with the vector \(\mathbf{r}\) and the multiplication by a scalar (complex) number \(\mu_{i}\) (line 8 of Algorithm 1) can be easily performed by the CORDIC algorithm without explicitly calculating and storing \(\mathbf{a}_{*,i}\). Hence, the vector \(\mathbf{a}_{*,i}\) will only exist virtually in the hardware implementation [12]. Based on Algorithm 1, we propose an extension of the work published in [12]. In the proposed version, we continue to exploit the fact that most coordinates that are zero remain unchanging over the iterations.