资源描述：
《201005-A FIRST-ORDER AUGMENTED LAGRANGIAN METHOD FOR COMPRESSED SENSING》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、AFIRST-ORDERAUGMENTEDLAGRANGIANMETHODFORCOMPRESSEDSENSINGN.S.AYBAT∗ANDG.IYENGAR†Abstract.Inthispaper,weproposeafirst-orderaugmentedLagrangianalgorithm(FAL)thatsolvesthebasispursuit(k)1problemmin{kxk1:Ax=b}byinexactlysolvingasequenceofproblemsoftheformminx∈ℜnλkxk1+
2、2kAx−b−λ(k)θ(k)k2,foranappropriatelychosensequenceofmultipliers{(λ(k),θ(k))}k∈Z+.Eachofthesesubproblemsaresolvedusing2Algorithm3in[19]whereineachupdatereducesto“shrinkage”[12]orconstrained“shrinkage”.WeshowthatFALconvergestoanoptimalsolutionx∗ofthebasispursuitprob
3、lem,i.e.x∗∈argmin{kxk1:Ax=b}andthatthereexistapriorifixedsequence{λ(k)}k∈Z+suchthatforallǫ>0,iteratesx(k)computedbyFALareǫ-feasible,i.e.kAx(k)−bk2≤ǫ,andǫ-optimal,kx(k)k≤ǫ,afterO(ǫ−1)iterations,wherethecomplexityofeachiterationisO(nlog(n)).Wealsoreportthe1−kx∗k1resu
4、ltsofnumericalexperimentscomparingtheperformanceofFALwithSPA[1],NESTA[18],FPC[10,11],FPC-AS[21]andaBregman-regularizedsolver[20].AverystrikingresultthatweobservedinournumericalexperimentswasthatFALalwayscorrectlyidentifiesthezero-setofthetargetsignalwithoutanythres
5、holdingorpost-processingforallreasonablysmallerrortolerancevalues.1.Introduction.Inthispaperwedesignanewfirst-orderaugmentedLagrangianalgorithmforsolvingtheℓ1-minimizationproblemminkxk1subjecttoAx=b,(1.1)x∈RnPnmnm×nwhereℓ1-normkxk1=i=1
6、xi
7、,xidenotesthei-thcomponent
8、ofthevectorx,b∈R,x∈R,A∈Randthenumberofequationsm≪n.Thisproblemcanbereformulatedintoalinearprogram(LP)andtherefore,can,intheory,besolvedefficiently.LPsoftheform(1.1)haverecentlyattractedalotofattentionsincetheyappearinthecontextofanewsignalprocessingparadigmknownasco
9、mpressivesensing(CS)[4,5,6,9].ThegoalinCSistorecoverasparsesignalxfromasmallsetoflinearmeasurementsortransformvaluesb=Ax.OrdinarilythesparsesignalwouldhavetoberecoveredbysolvingtheNP-hardℓ0-minimizationproblemminkxk0subjecttoAx=b,(1.2)x∈RnPnwheretheℓ0normkxk0=i=11
10、(xi6=0).Recently,Candes,RombergandTao[4,5,6]andDonoho[9]haveshownthatwhenthetargetsignalxiss-sparse,i.e.onlysofthencomponentsarenon-zeros,themeasurement
