壓縮感知重構(gòu)算法

壓縮感知重構(gòu)算法之基追蹤(BasisPursuit,BP)除匹配追蹤類貪婪迭代算法之外，壓縮感知重構(gòu)算法另一大類就是凸優(yōu)化算法或最優(yōu)化逼近方法，這類方法通過將非凸問題轉(zhuǎn)化為凸問題求解找到信號的逼近，其中最常用的方法就是基追蹤(BasisPursuit,BP)，該方法提出使用l范數(shù)替代l范數(shù)來解決最優(yōu)化問題，以便1 0使用線性規(guī)劃方法來求解[1]。本篇我們就來講解基追蹤方法。理解基追蹤方法需要一定的最優(yōu)化知識基礎(chǔ)，可參見最優(yōu)化方法分類中的內(nèi)容。1、11范數(shù)和10范數(shù)最小化的等價(jià)問題在文獻(xiàn)【2】的第4部分，較為詳細(xì)的證明了l范數(shù)與1。范數(shù)最小化在某條件下等價(jià)。證明過程是一個(gè)比較復(fù)雜的數(shù)學(xué)推導(dǎo)，這里盡量引用文獻(xiàn)中的原文來說明。首先，在文獻(xiàn)【2】的4.1節(jié)，給出了(P1)問題，并給出了⑶)的線性規(guī)劃等價(jià)形式(LP)，這個(gè)等價(jià)關(guān)系后面再詳敘。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、基追蹤實(shí)現(xiàn)工具箱l1-MAGIC若要談基追蹤方法的實(shí)現(xiàn)，就必須提到l1-MAGIC工具箱(工具箱主頁：/~justin/l1magic/)，在工具箱主頁有介紹：L1-MAGICisacollectionofMATLABroutinesforsolvingtheconvexoptimizationprogramscentraltocompressivesampling.Thealgorithmsarebasedonstandardinterior-pointmethods,andaresuitableforlarge-scaleproblems.另外，該工具箱專門有一個(gè)說明文檔《l1-magic:RecoveryofSparseSignalsviaConvexProgramming》，可以在工具箱主頁下載。該工具箱一共解決了七個(gè)問題，其中第一個(gè)問題即是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節(jié)也進(jìn)行了介紹。在附錄中，給出了將(P)問題轉(zhuǎn)化為線性規(guī)劃問題的過程，但這個(gè)似乎并不怎么容1易看明白：3如何將(P1)轉(zhuǎn)化為線性規(guī)劃問題？盡管在11-MAGIC給出了一種基追蹤的實(shí)現(xiàn)，但需要基于它的l1eq_pd.m文件，既然基追蹤是用線性規(guī)劃求解，那么就應(yīng)該可以用MATLAB自帶的linprog函數(shù)求解，究竟該如何將(P1)轉(zhuǎn)化為標(biāo)準(zhǔn)的線性規(guī)劃問題呢？我們來看文獻(xiàn)【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.這里，文獻(xiàn)【3】的轉(zhuǎn)化說明跟文獻(xiàn)【2】中4.1節(jié)的說明差不多，但對初學(xué)者來說仍然會有一定的困難，下面我們就以文獻(xiàn)【3】中的符號為準(zhǔn)來解讀一下。首先，式(3.1)中的變量a沒有非負(fù)約束，所以要將a變?yōu)閮蓚€(gè)非負(fù)變量u和v的差a=u-v，由于u可以大于也可以小于v，所以a可以是正的也可以是負(fù)的[4]。也就是說，約束條件①a=s要變?yōu)棰?u-v)=s，而這個(gè)還可以寫為[①,-①][u;v]=s，更清晰的寫法如下：u中一"=因然后，根據(jù)范數(shù)的定義，目標(biāo)函數(shù)可進(jìn)一點(diǎn)寫為：ll.ll=Z也|=Z|Uf|1 i iii i目標(biāo)函數(shù)中有絕對值，怎么去掉呢？這里得看一下文獻(xiàn)【5】：對Llnorm如何線性化的理解最主要的是要想明白為什么對單一元素的最小化，即minixl等價(jià)于以下的線性規(guī)劃問題。miny+zy-z=xy,z>0TOC\o"1-5"\h\z現(xiàn)在假設(shè)以上的線性規(guī)劃問題的最優(yōu)解y,z，并且y>0,z>0。這個(gè)時(shí)候，總可以找0 0 0 0到一個(gè)很小的正數(shù)a使得y=y-a>0,z=z-共0。而對于y,z它們滿足以上線性規(guī)劃的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標(biāo)函數(shù)值，即y+z-2a。這就證明了y,z并不是最優(yōu)解，從而導(dǎo)出矛盾。所以這一般的0 0 0 0結(jié)論就是對于以上的線性規(guī)劃問題，其最優(yōu)解必須滿足要嗎y=0，要嗎z=0，從而其最優(yōu)目標(biāo)值要嗎是x，要嗎是-x，即lxl。現(xiàn)在推廣到有限維度的向量匕norm最小化，即minllxll=min2：lxI。它等價(jià)于以下的i=1線性規(guī)劃問題minc(Y+Z)Y-Z=XY,Z>0其中c是1行n列的矩陣，并且每個(gè)元素都是1。到現(xiàn)在一切應(yīng)該都清晰明白了，總結(jié)如下：問題minllall st.①a=s,ae□p可以轉(zhuǎn)化為線性規(guī)劃問題minctxs.tAx=b,x>0，其中，ct=[L1,???』]"，xe□2p，A=[①,-①]，b=s；求得最優(yōu)化解x0后可得變量a的最優(yōu)化解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,