An improvement on StOMP for sparse solution of linear underdetermined problems

StOMP is well suited to large-scale systems in sparse vector estimation. It can reduce computation complexity without significant deterioration of estimation accuracy, and has some attractive asymptotically statistical properties. However, the speed of vector estimation is at the cost of accuracy violation. In this paper, an improvement on StOMP is suggested. Firstly, during one stage of the algorithm, according to the mixed probability distribution of coefficients of a matched filter, distribution parameters are estimated more accurately using an outlier deletion method. This estimate also leads to an estimate on the support set of the sparse vector. Secondly, an initial estimate is obtained through least-squares method for sparse vector. Thirdly, a more accurate estimate of the support set is achieved on the basis of an estimated True Positive Rate (TPR), which results in a significant False Positive Rate (FPR) reduction. Finally, after solving a least-squares problem, an estimation residual is produced. This improved algorithm can not only more accurately estimate the parameters of distribution of matched filter coefficients, but also improve estimation accuracy for the sparse vector. Simulation results show that without significant increment in computation complexity, the proposed algorithm can greatly improve estimation accuracy for sparse solution problems.