Application Of Dichotomous Coordinate Descent Algorithm In System Identification And Sparse System

Applications that require signal processing in the communications field can be reduced to solving linear least squares(LS)problems;these applications include system identification,signal detection,and adaptive antenna arrays,etc.Solving linear LS problems is equivalent to solving a system of linear equations.The maximum likelihood algorithm can obtain the optimal solution of the linear equation,but in the face of complex systems,its calculation is very high,and practical operation is low.Therefore,many researchers design low-complexity sub-optimal algorithms,which usually require matrix inversions when solving linear equations.Direct inversion requiresO(N~3)(N is the size of the system size)operands.The Dichotomous Coordinate Descent(DCD)algorithm does not require multiplication/division operations,it can efficiently solve linear equations,and it is very suitable for hardware implementation.Among the many DCD algorithms,we mainly study the improvement and application of Cyclic and Leading DCD algorithms.The Cyclic DCD algorithm is suitable for solving system equations that require a large number of iterative updates.If the result of the problem to be solved is a sparse situation,such as multi-path channel estimation or multi-user detection,some users are inactive for a long time.In the case that the number of iteration updates required to solve this system equation is relatively small,the Leading DCD algorithm converges faster than the Cyclic DCD.Recursive Least Squares(Recursive Least Square,RLS)is known for its fast convergence rate among many adaptive algorithms,but it requiresO(N~2)operands(N is the order of the filter)for each sample.When the value of N is large,the complexity of the RLS algorithm will be very high.Therefore,it is very necessary to reduce the number of operations required for each sample of a typical RLS algorithm.In time-varying systems,when the fixed forgetting factor?is large,the stability error of the RLS algorithm is small,but the convergence speed is slow.When?is smaller,RLS converges faster,but the stability error is larger.We integrated the leading DCD iteration into the RLS algorithm,converted the adaptive RLS algorithm into a regular equation system for solving filter weights,and use the DCD iteration algorithm to solve the regular equations,thereby reducing the number of operations required for each sample.Besides for time-varying systems,without the need for additional parameter estimation,we update the forgetting factor in real-time by calculating the system noise power,so we propose an improved variable forgetting factor RLS based on DCD iteration(VFF-DCD-ERLS).The data results show that the proposed VFF-DCD-ERLS algorithm has faster convergence speed and lower steady-state error than RLS,DCD-ERLS and DCD-SRLS algorithms.Even when the system noise energy changes suddenly,the proposed VFF-DCD-ERLS algorithm can still ensure fast convergence,low steady-state error,and reflects strong robustness.The complexity required by the DCD algorithm to calculate the linear system equations usually depends on the system size,the sparsity of the results,and the number of system matrix conditions.When the system is sparse and the condition number of the system matrix is small,the leading DCD algorithm can provide fast convergence.When condition number of the system matrix is large,and the result is not strongly sparse,that is,the number of non-zeros in the result is greater than 1/8of the total number of elements,the Cyclic DCD algorithm has a lower stability error than the Leading DCD algorithm,but in the first a few iterations,Leading DCD has lower convergence speed than Cyclic DCD algorithm.Therefore,we consider combining the Leading DCD and Cyclic DCD algorithms,and propose the Leading-Cyclic DCD algorithm.The Leading-Cyclic DCD algorithm is divided into two steps:First,the Leading DCD algorithm uses fewer iterations to obtain the results;second,the Cyclic DCD algorithm uses the output of the Leading DCD as the initial input to obtain more accurate soft output results with a large number of update iterations.The data results show that the proposed Leading-Cyclic DCD algorithm has a faster convergence rate and lower stability error than the leading DCD algorithm and cyclic DCD algorithm in a system where the system matrix is a large condition number(>100)and sparseness(?>1/8).