压缩感知重构算法

压缩感知重构算法之基追踪(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,