# Adaptive Sparse Cyclic Coordinate Descent for Sparse Frequency Estimation
## 1 Introduction
Sparse recovery algorithms can be classified into two principal categories: greedy algorithms (e.g., orthogonal matching pursuit (OMP) [13]; iterative hard thresholding (IHT) [14]) and convex optimization methods (least absolute shrinkage and selection operator (LASSO) [15], basis pursuit denoising (BPDN) [16], linearized Bregman iterations (LBI) [17], etc.). However, when choosing one of these algorithms for a particular application, there is a range of different properties that have to be considered, such as computational and storage requirements, ease of implementation, recovery performance, and flexibility [18]. An analysis of the performance guarantees of these algorithms usually involves quantities that measure the suitability of the measurement matrix \(\mathbf{A}\)[19]. Some of these measures of quality are the restricted isometry property (RIP) and the mutual coherence (MC). Greedy algorithms are easy to implement and can be extremely fast [18] in some scenarios. They ease the computational complexity by performing locally optimal greedy iterations, but the recovery guarantees are weaker than those of convex optimization methods. Successful estimation can only be guaranteed if one further assumes that all non-zero components of \(\mathbf{x}\) are somewhat larger than the noise level. Greedy techniques rely on a least square (LS) solution for an estimated support, and this approach performs poorly unless the support is correctly identified. A single incorrectly identified element of the support can lead to the entire estimation being severely incorrect [20]. In the case of OMP, the performance guarantees rely on the RIP condition and the mutual coherence of the measurement matrix \(\mathbf{A}\). In general, we do not normally know whether the RIP holds [18] and it is NP-hard to evaluate the restricted isometry constants (RICs) for a given matrix. They must then be bounded by efficiently computable properties of \(\mathbf{A}\), such as the mutual coherence [20]. The exact recovery of every \(p\)-sparse vector via orthogonal matching pursuit is guaranteed when the measurement matrix has a coherence \(\mu<1/(2p-1)\)[19]. The mutual coherence \(\mu=\mu(\mathbf{A})\) of a matrix \(\mathbf{A}\) is defined as \(\mu:=\max_{1\leq i\
eq j\leq N}|\langle\mathbf{a}_{i},\mathbf{a}_{j}\rangle|\) for a matrix \(\mathbf{A}\in\mathbb{C}^{M\times N}\) with \(\ell_{2}\)-normalized columns for all \(i\in[N]\)[19]. In applications such as frequency estimation where the measurement matrix is composed of complex exponentials that are highly correlated, conditions such as the one enunciated above are violated. For example, in a scenario with \(M=50,\Delta_{f}=1/(20M)\) and \(p=5\), the mutual coherence of the matrix \(\mathbf{A}\) is equal to \(0.9959\). Therefore this condition cannot be satisfied (i.e., \(\mu=0.9959>1/(2p-1)=0.111\)). On the other hand, convex optimization methods have very good performance guarantees, which make them a reliable tool for sparse signal recovery but with the drawback that these methods typically have a higher computational cost for large-scale problems. Therefore, iterative approaches such as sparse cyclic coordinate descent (SCCD) [21] were introduced for solving these problems. SCCD is an optimization technique that sequentially minimizes a cost function in the direction of a single coordinate while leaving all other coordinates fixed. This is particularly useful in cases where the single parameter problem is easy to solve [22]. It is also especially suitable for problems where the gradient of the cost function does not have a closed-form solution. Moreover, efficient storage in a sparse vector format can be implemented since SCCD only updates one entry of the sparse vector at each iteration. SCCD also offers other advantages in terms of memory requirements compared to alternative algorithms such as linearized Bregman iterations.