# Improved Convergence Speed of a DCD-Based Algorithm for Sparse Solutions
## 1 Introduction  
With the development of information technology, the number of participated devices and data transmission rate have substantially increased in recent years. Solving the problems in a wide range of signal processing applications is equivalent to getting the solution of a linear least squares (LS) problem [1]. These applications include adaptive antenna array applications [2], multi-user detection [3], multiple-input multiple-output (MIMO) detection [4], echo cancellation [5], equalization [6], and system identification [1; 7; 8; 9]. If the channel information is known, zero forcing (ZF) algorithm and minimum mean-square error (MMSE) algorithm are popular to be used in these applications. They are simple to implement but require the operation of matrix inversion. The complexity of matrix inversion requires \(\mathcal{O}(U^{3})\) arithmetic operations, where \(U\) is system size [10]. When the system size is large, the complexity of the matrix inversion is prohibitively high. As a result, there are some techniques proposed to solve systems of equations without inverting the matrix. Direct methods, for example Gaussian elimination, Cholesky factorization, and QR decomposition attain a complexity of \(\mathcal{O}(U^{3})\)[10; 11]. Therefore, it is difficult for direct methods to be implemented in real-time signal processing and hardware applications. Using these methods to solve the linear equations of large sparse systems may be prohibitively expensive and are infeasible for practical applications. Iterative methods, for example, the conjugate gradient method and the steepest descent method could achieve fast convergence. In each iteration, they require \(\mathcal{O}(U^{2})\) complexity. Other iterative methods, for example, the Southwell's relaxation [12], Jacobi [10] and Gauss-Seidel [10], are coordinate descent approaches. At each iteration, they only require \(\mathcal{O}(U)\) complexity but have a slower convergence speed. The number of iterations performed decides the computational complexityof these techniques. Iterative methods can solve problems with sparse structures more efficiently compared with direct methods [13]. Moreover, iterative methods have the potential to achieve a good initial guess for the expected results, which can reduce the number of iterations required to obtain a solution [14]. However, some iterative methods include the numerical operations of multiplying or dividing, which are difficult for hardware implementation. Prior research work investigates the dichotomous coordinate descent (DCD) algorithms that use a reduced number of operations to solve systems of equations. DCD-based algorithms are well known in many applications because the DCD algorithm avoids the operations of multiplying and dividing, which are expensive to implement. In [15; 16; 17], by applying the DCD iterations, the numerical complexity of affine projection algorithms for active noise control is reduced. In [18], DCD iterations solve the recursive least squares (RLS) matrix inversion problem by using bit-shift. The DCD algorithm [14; 19] is a non-stationary iterative method based on stationary CD techniques. Only \(\mathcal{O}(U)\) additions or \(\mathcal{O}(1)\) additions are required in each iteration [11]. The DCD algorithm, therefore, is a good choice for real-time hardware implementations. The DCD algorithm variants, cyclic DCD and leading DCD algorithm, were presented in [20]. When scenarios with sparse true solutions are considered, such as multi-path channel estimation and detection of a multi-user system with several unknown active users, the leading DCD algorithm converges faster than the cyclic DCD algorithm. The cyclic DCD algorithm is ideal for solving systems of equations that require a large number of iterations because it converges faster and has a lower error level than the leading DCD algorithm. However, the leading DCD algorithm has a faster convergence rate than the cyclic DCD algorithm in the initial iterations if the solution is not very sparse.