# Improved Convergence Speed of a DCD-Based Algorithm for Sparse Solutions
## 3 Proposed Leading-Cyclic DCD Algorithm  
From the results above, we can see that the cyclic DCD algorithm is more suitable for solving a non-sparse system with a large condition number. However, it is noted that when the percentage of non-zero elements of the solution is approximately 50%, the leading DCD algorithm provides a faster convergence in the initial updates. To further improve the convergence when the solution is not highly sparse, we consider combining the leading and cyclic DCD algorithms and propose the leading-cyclic DCD algorithm shown in Table 3.  
The proposed algorithm involves two steps. In the first step, a data vector is obtained using the leading DCD algorithm with a considerably smaller number of iterations \(N_{u_{leading}}\) than in the standard version of the leading DCD algorithm. In the second step, an improved soft output is generated by applying the cyclic DCD algorithm with a large number of iterations \(N_{u}\). The updated vectors of \(\mathbf{x}\) and \(\mathbf{\Gamma}\) and the step size of \(\sigma\) obtained from the leading DCD algorithm are the initial values for the cyclic DCD algorithm. There are two factors that determine the worst-case computational complexity of the leading-cyclic DCD algorithm. The cyclic DCD algorithm starts at \(m_{leading}-1\) bit for updating an element of the solution. The upper computational complexity of the cyclic DCD algorithm is calculated as follows. For the \(m\)-th bit, \(m=m_{leading}-1,2,3,\cdots,M_{b}-1\) has \((N_{u}-N_{u_{leading}})\) successful iterations. That is, executing the initial \((M_{b}-m_{leading})\) bits does not include a successful iteration and thus requires \((M_{b}-m_{leading})U\) additions. Among the \(U\) iterations \((n=1,2,\cdots,U)\), if there is only one successful iteration, then calculating the last bit \((m=M_{b})\) requires \(U\) additions for the comparison and  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Step** & **Input \(\beta\), \(\mathbf{R}\), \(\mathbf{M_{b}}\), \(\mathbf{\zeta}\), \(\mathbf{N_{u_{leading}}}\); Output \(\mathbf{x}\), \(\mathbf{\Gamma}\)** & **Addition** \\ \hline \multicolumn{3}{c}{Initialization: \(\mathbf{x}=0\), \(\mathbf{\Gamma}=\beta\), \(\sigma=\zeta\), \(m_{leading}=1\)} \\ \hline \multicolumn{3}{c}{for \(p=1,\ldots,N_{u_{leading}}\)} \\ \hline
1 & \(n=\arg\max_{j=1,\ldots,U}\{|\Gamma_{j}|\}\Rightarrow\) goto step 4 & \(U-1\) \\ \hline
2 & \(m_{leading}=m_{leading}+1,\sigma=\sigma/2\) \\ \hline
3 & if \(m_{leading}>M_{b}\), execution stops \\ \hline
4 & if  
\((U+1)\) additions for updating the residual vector \(\mathbf{\Gamma}\) and elements \(x_{n}\). In total, \((N_{u}-N_{u_{\textit{leading}}})\) successful iterations require \(N_{u}-N_{u_{\textit{leading}}}(2U+1)\) additions. The upper bound of computational complexity of the cyclic DCD algorithm is \(\{U[2(N_{u}-N_{u_{\textit{leading}}})+(M_{b}-m_{\textit{leading}})-1]+(N_{u}-N _{u_{\textit{leading}}})\}\) additions. The worst-case scenario for the complexity of the leading DCD algorithm occurs when the algorithm uses all \(N_{u_{\textit{leading}}}\) updates. By using \(N_{u_{\textit{leading}}}\) iterations, the computational complexity of the leading DCD algorithm is \(\{(2U+1)N_{u_{\textit{leading}}}+m_{\textit{leading}}\}\) additions. Therefore, the computational complexity of the leading-cyclic DCD algorithm has an upper limit of \(\{(2U+1)N_{u}+(1-U)m_{\textit{leading}}+(M_{b}-1)U\}\) real-valued additions. In a practical situation, in each pass there should be several successful updates, and the average complexity is close to \(2 UN_{u}\). \(N_{u_{\textit{cyclic}}}\) is approximately equal to \(N_{u}\); therefore, the average complexity of the leading-cyclic DCD algorithm is close to that of the cyclic DCD algorithm. The selection of \(N_{u_{\textit{leading}}}\) varies based on the system matrix condition and the solution sparsity. The leading-cyclic algorithm is evaluated by using different \(N_{u_{\textit{leading}}}\) values in the range of \([U(1-\gamma),Q+U]\).