Outlier deletion based improvement on the StOMP algorithm for sparse solution of large-scale underdetermined problems  

作　　者：ZHANG WanHong ZHOU Tong HUANG BoXue 

机构地区：[1]Department of Automation,Tsinghua University [2]Department of Chemical Machinery,Qinghai University [3]Tsinghua National Laboratory for Information Science and Technology,Tsinghua University

出　　处：《Science China(Information Sciences)》2014年第9期238-251,共14页中国科学（信息科学）（英文版）

基　　金：supported in part by National Basic Research Program of China (973)(Grant No. 2012CB316504);National Natural Science Foundation of China (Grant Nos. 61174122,61021063);Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20110002110045)

摘　　要：StOMP algorithm is well suited to large-scale underdetermined applications in sparse vector estimations. It can reduce computation complexity and has some attractive asymptotical statistical properties.However,the estimation speed is at the cost of accuracy violation. This paper suggests an improvement on the StOMP algorithm that is more efficient in finding a sparse solution to the large-scale underdetermined problems. Also,compared with StOMP,this modified algorithm can not only more accurately estimate parameters for the distribution of matched filter coefficients,but also improve estimation accuracy for the sparse vector itself. Theoretical success boundary is provided based on a large-system limit for approximate recovery of sparse vector by modified algorithm,which validates that the modified algorithm is more efficient than StOMP. Actual computations with simulated data show that without significant increment in computation time,the proposed algorithm can greatly improve the estimation accuracy.StOMP algorithm is well suited to large-scale underdetermined applications in sparse vector estimations. It can reduce computation complexity and has some attractive asymptotical statistical properties.However,the estimation speed is at the cost of accuracy violation. This paper suggests an improvement on the StOMP algorithm that is more efficient in finding a sparse solution to the large-scale underdetermined problems. Also,compared with StOMP,this modified algorithm can not only more accurately estimate parameters for the distribution of matched filter coefficients,but also improve estimation accuracy for the sparse vector itself. Theoretical success boundary is provided based on a large-system limit for approximate recovery of sparse vector by modified algorithm,which validates that the modified algorithm is more efficient than StOMP. Actual computations with simulated data show that without significant increment in computation time,the proposed algorithm can greatly improve the estimation accuracy.

关 键 词：stagewise orthogonal matching pursuit sparse solution linear underdetermined equations systems biology outlier deletion 

分 类 号：TN911.7[电子电信—通信与信息系统]