壓縮感知重構算法之基追蹤(BasisPursuit,BP)除匹配追蹤類貪婪迭代算法之外，壓縮感知重構算法另一大類就是凸優化算法或最優化逼近方法，這類方法通過將非凸問題轉化為凸問題求解找到信號的逼近，其中最常用的方法就是基追蹤(BasisPursuit,BP)，該方法提出使用l范數替代l范數來解決最優化問題，以便1 0使用線性規劃方法來求解[1]。本篇我們就來講解基追蹤方法。理解基追蹤方法需要一定的最優化知識基礎，可參見最優化方法分類中的內容。1、11范數和10范數最小化的等價問題在文獻【2】的第4部分，較為詳細的證明了l范數與1。范數最小化在某條件下等價。證明過程是一個比較復雜的數學推導，這里盡量引用文獻中的原文來說明。首先，在文獻【2】的4.1節，給出了(P1)問題，并給出了⑶)的線性規劃等價形式(LP)，這個等價關系后面再詳敘。4.1TheCasep=1Inthecasep=1,(P)isaconvexoptimizationproblem.Writeitoutinanequivalentform,with10beingtheoptimizationvariable:(P)min||0||subjectto①0=y.Thiscanbeformulatedasalinearprogrammingproblem:letAbethenby2mmatrix[①一①].Thelinearprogram(LP)minDzsubjecttoAz=y,x>0.z nhasasolutionz*,say,avectorin2mwhichcanbepartitionedasz*=[u*v*];then0*=u*—v*solves(P).Thereconstructionx=中0*.Thislinearprogramistypicallyconsidered1 1,ncomputationallytractable.Infact,thisproblemhasbeenstudiedinthesignalanalysisliteratureunderthenameBasisPursuit[7];inthatwork,verylarge-scaleunderdeterminedproblems.2、基追蹤實現工具箱l1-MAGIC若要談基追蹤方法的實現，就必須提到l1-MAGIC工具箱(工具箱主頁：/~justin/l1magic/)，在工具箱主頁有介紹：L1-MAGICisacollectionofMATLABroutinesforsolvingtheconvexoptimizationprogramscentraltocompressivesampling.Thealgorithmsarebasedonstandardinterior-pointmethods,andaresuitableforlarge-scaleproblems.另外，該工具箱專門有一個說明文檔《l1-magic:RecoveryofSparseSignalsviaConvexProgramming》，可以在工具箱主頁下載。該工具箱一共解決了七個問題，其中第一個問題即是BasisPursuit:Min-l1withequalityconstraints.Theproblem(P)min||x||subjecttoAx=b,alsoknownasbasispursuit,findsthevectorwithsmallestl1norm||x|=2x」|ithatexplainstheobservationsb.Astheresultsin[4,6]show,ifasufficientlysparsexexistssuchthatAx=bthen(P)willfindit.Whenx,A,bhavereal-valuedentries,(P)canberecastasanLP(thisisdiscussedindetailin[10]).工具箱中給出了專門對(P)的代碼，使用方法可參見l1eq_example.m,說明文檔3.11節也進行了介紹。在附錄中，給出了將(P)問題轉化為線性規劃問題的過程，但這個似乎并不怎么容1易看明白：3如何將(P1)轉化為線性規劃問題？盡管在11-MAGIC給出了一種基追蹤的實現，但需要基于它的l1eq_pd.m文件，既然基追蹤是用線性規劃求解，那么就應該可以用MATLAB自帶的linprog函數求解，究竟該如何將(P1)轉化為標準的線性規劃問題呢？我們來看文獻【3】的介紹：3BasisPursuitWenowdiscussourapproachtotheproblemofovercompleterepresentations.Weassumethatthedictionaryisovercomplete,sothatthereareingeneralmanyrepresentationss=Za?.TheprincipleofBasisPursuitistofindarepresentationofthesignalwhosecoefficientshaveminimallnorm.formally,onesolvestheproblemminIIaIIsubjectto①a=s. (3.1)Fromonepointofview,(3.1)isverysimilartothemethodofFrames(2.3):wearesimplyreplacingthe12normin(2.3)withthe11norm.however,thisapparentlyslightchangehasmajorconsequences.ThemethodofFramesleadstoaquadraticoptimizationproblemwithlinearequalityconstraints,andsoinvolvesessentiallyjustthesolutionofasystemoflinearequations.Incontrast,BasisPursuitrequiresthesolutionsofaconvex,nonquadraticoptimizationproblem,whichinvolvesconsiderablymoreeffortandsophistication.3.1LinearProgrammingToexplainthelastcomment,andthenameBasisPursuit,wedevelopaconnectionwithlinearprogramming(LP).Thelinearprograminso-calledstandardform[7,16]isaconstrainedoptimizationproblemdefinedintermsofavariablexembymincTxsubjecttoAx=b,x>0,(3.2)wherectxistheobjectivefunction,Ax=bisacollectionofequalityconstraints,andx>0isasetofbounds.Themainquestionis,whichvariablesshouldbezero.TheBasisPursuitproblem(3.1)canbeequivalentlyreformulatedasalinearprograminthestandardform(3.2)bymakingthefollowingtranslations:mo2p;xo(u,v);co(1,1)Ao(①,一①)；bos.Hence,thesolutionof(3.4)canbeobtainedbysolvinganequivalentlinearprogram.(Theequivalentofminimuml1optimizationswithlinearprogramminghasbeenknownsincethe1950’s;see[2]).TheconnectionbetweenBasisPursuitandlinearprogrammingisusefulinseveralways.這里，文獻【3】的轉化說明跟文獻【2】中4.1節的說明差不多，但對初學者來說仍然會有一定的困難，下面我們就以文獻【3】中的符號為準來解讀一下。首先，式(3.1)中的變量a沒有非負約束，所以要將a變為兩個非負變量u和v的差a=u-v，由于u可以大于也可以小于v，所以a可以是正的也可以是負的[4]。也就是說，約束條件①a=s要變為①(u-v)=s，而這個還可以寫為[①,-①][u;v]=s，更清晰的寫法如下：u中一"=因然后，根據范數的定義，目標函數可進一點寫為：ll.ll=Z也|=Z|Uf|1 i iii i目標函數中有絕對值，怎么去掉呢？這里得看一下文獻【5】：對Llnorm如何線性化的理解最主要的是要想明白為什么對單一元素的最小化，即minixl等價于以下的線性規劃問題。miny+zy-z=xy,z>0TOC\o"1-5"\h\z現在假設以上的線性規劃問題的最優解y,z，并且y>0,z>0。這個時候，總可以找0 0 0 0到一個很小的正數a使得y=y-a>0,z=z-共0。而對于y,z它們滿足以上線性規劃的1 0 1 0 1 1所有約束，比如y-z=y-a-(z-a)=y-z=x，但這組可行解卻具有比y,z更小的目1 1 0 0 0 0 0 0標函數值，即y+z-2a。這就證明了y,z并不是最優解，從而導出矛盾。所以這一般的0 0 0 0結論就是對于以上的線性規劃問題，其最優解必須滿足要嗎y=0，要嗎z=0，從而其最優目標值要嗎是x，要嗎是-x，即lxl。現在推廣到有限維度的向量匕norm最小化，即minllxll=min2：lxI。它等價于以下的i=1線性規劃問題minc(Y+Z)Y-Z=XY,Z>0其中c是1行n列的矩陣，并且每個元素都是1。到現在一切應該都清晰明白了，總結如下：問題minllall st.①a=s,ae□p可以轉化為線性規劃問題minctxs.tAx=b,x>0，其中，ct=[L1,???』]"，xe□2p，A=[①,-①]，b=s；求得最優化解x0后可得變量a的最優化解a=x(1:p)-x(p+1:2p)。4、基于linprog的基追蹤MATLAB代碼(BP_linprog.m)function[alpha]=BP_linprog(s,Phi)%BP_linprog(BasisPursuitwithlinprog)Summaryofthisfunctiongoeshere%Version:1.0writtenbyjbb0523@2016-07-21%Reference:ChenSS,DonohoDL,SaundersMA.Atomicdecompositionby%basispursuit[J].SIAMreview,2001,43(1):129-159.(Availableat:%/viewdoc/download?doi=7.4272&rep=rep1&type=pdf)%Detailedexplanationgoeshere%s=Phi*alpha(alphaisasparsevector)%Givens&Phi,trytoderivealpha[s_rows,s_columns]=size(s);ifs_rows<s_columnss=s';%sshouldbeacolumnvectorendp=size(Phi,2);%accordingtosection3.1ofthereferencec=ones(2*p,1);A=[Phi,