压缩感知重构算法之基追踪

1、压缩感知重构算法之基追踪(BasisPursuit,BP)除匹配追踪类贪婪迭代算法之外，压缩感知重构算法另一大类就是凸优化算法或最优化逼近方法，这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，其中最常用的方法就是基追踪(BasisPursuit,BP)，该方法提出使用l范数替代l范数来解决最优化问题，以便10使用线性规划方法来求解1。本篇我们就来讲解基追踪方法。理解基追踪方法需要一定的最优化知识基础，可参见最优化方法分类中的内容。1、11范数和10范数最小化的等价问题在文献【2】的第4部分，较为详细的证明了l范数与l范数最小化在某条件下等价。10证明过程是一个比较复杂的数学推导，这里尽量

2、引用文献中的原文来说明。首先，在文献【2】的4.1节，给出了(P1)问题，并给出了(P1)的线性规划等价形式(LP),这个等价关系后面再详叙。4.1TheCasep=1Inthecasep=1,(P)isaconvexoptimizationproblem.Writeitoutinanequivalentform,with10beingtheoptimizationvariable:minII0IIsubjectto0=y.01nThiscanbeformulatedasalinearprogrammingproblem:letAbethenby2mmatrix一.Thelinearprogr

3、am(LP)minlTzsubjecttoAz=y,x>0.nzhasasolutionz*,say,avectorin2mwhichcanbepartitionedasz*=u*v*;then0*=u*一v*solves(P).Thereconstructionx=¥0*.Thislinearprogramistypicallyconsidered11,ncomputationallytractable.Infact,thisproblemhasbeenstudiedinthesignalanalysisliteratureunderthenameBasisPursuit7;

4、inthatwork,verylarge-scaleunderdeterminedproblems.2、基追踪实现工具箱l1-MAGIC若要谈基追踪方法的实现，就必须提到l1-MAGIC工具箱(工具箱主页：/justin/l1magic/),在工具箱主页有介绍：L1-MAGICisacollectionofMATLABroutinesforsolvingtheconvexoptimizationprogramscentraltocompressivesampling.Thealgorithmsarebasedonstandardinterio

5、r-pointmethods,andaresuitableforlarge-scaleproblems.另外，该工具箱专门有一个说明文档l1-magic:RecoveryofSparseSignalsviaConvexProgramming，可以在工具箱主页下载。该工具箱一共解决了七个问题，其中第一个问题即是BasisPursuit：Min-lwithequalityconstraints.Theproblem1(P)minIIxIIsubjecttoAx=b,11alsoknownasbasispursuit,findsthevectorwithsmallestlnorm1|x|=Yx|1i

6、ithatexplainstheobservationsb.Astheresultsin4,6show,ifasufficientlysparsexexists0suchthatAx=bthen(P)willfindit.Whenx,A,bhavereal-valuedentries,(P)canbe011recastasanLP(thisisdiscussedindetailin10).工具箱中给出了专门对(P)的代码，使用方法可参见lleq_example.m,说明文档3.11节也进行了介绍。在附录中，给出了将(P)问题转化为线性规划问题的过程，但这个似乎并不怎么容1易看明白：3如何将(P

7、1)转化为线性规划问题？尽管在11-MAGIC给出了一种基追踪的实现，但需要基于它的I1eq_pd.m文件，既然基追踪是用线性规划求解，那么就应该可以用MATLAB自带的linprog函数求解，究竟该如何将(P1)转化为标准的线性规划问题呢？我们来看文献【3】的介绍：3BasisPursuitWenowdiscussourapproachtotheproblemofovercompleterepresentations.Weassumethatthedictionaryisovercomplete,sothatthereareingeneralmanyrepresentationss=YaQ.

8、YYYTheprincipleofBasisPursuitistofindarepresentationofthesignalwhosecoefficientshaveminimallnorm.formally,onesolvestheproblem1minIIaIIsubjecttoa=s.(3.1)1Fromonepointofview,(3.1)isverysimilartothemethodofFrames(2.3):wearesimplyreplacingthel2normin(2.3)withthel1norm.however,thisapparentlyslightchangeh

9、asmajorconsequences.ThemethodofFramesleadstoaquadraticoptimizationproblemwithlinearequalityconstraints,andsoinvolvesessentiallyjustthesolutionofasystemoflinearequations.Incontrast,BasisPursuitrequiresthesolutionsofaconvex,nonquadraticoptimizationproblem,whichinvolvesconsiderablymoreeffortandsophisti

10、cation.3.1LinearProgrammingToexplainthelastcomment,andthenameBasisPursuit,wedevelopaconnectionwithlinearprogramming(LP).Thelinearprograminso-calledstandardform7,16isaconstrainedoptimizationproblemdefinedintermsofavariablexembymincTxsubjecttoAx=b,x>0,(3.2)wherectxistheobjectivefunction,Ax=bisacoll

11、ectionofequalityconstraints,andx>0isasetofbounds.Themainquestionis,whichvariablesshouldbezero.TheBasisPursuitproblem(3.1)canbeequivalentlyreformulatedasalinearprograminthestandardform(3.2)bymakingthefollowingtranslations:mo2p;xo(u,v);co(1,1);Ao(，一);bos.Hence,thesolutionof(3.4)canbeobtainedbysolvi

12、nganequivalentlinearprogram.(Theequivalentofminimumloptimizationswithlinearprogramminghasbeenknownsincethe11950's;see2).TheconnectionbetweenBasisPursuitandlinearprogrammingisusefulinseveralways.这里，文献【3】的转化说明跟文献【2】中4.1节的说明差不多，但对初学者来说仍然会有一定的困难，下面我们就以文献【3】中的符号为准来解读一下。首先，式(3.1)中的变量a没有非负约束，所以要将a变为两个非

13、负变量u和v的差a=u-v，由于u可以大于也可以小于v，所以a可以是正的也可以是负的4。也就是说，约束条件a=s要变为(u-v)=s，而这个还可以写为，-u;v=s，更清晰的写法如下：uv然后，根据范数的定义，目标函数可进一点写为：IIaII=工IaI=工Iu-vI1iiiii目标函数中有绝对值，怎么去掉呢？这里得看一下文献【5】：对L1norm如何线性化的理解最主要的是要想明白为什么对单一元素的最小化，即minIxI等价于以下的线性规划问题。miny+zy-z=xy,z>0现在假设以上的线性规划问题的最优解y,z，并且y>0,z>0。这个时候，总可以找0000到一个很小的正

14、数a使得y=y-a>0,z=z-a>0。而对于y,z它们满足以上线性规划的101011所有约束，比如y-z=y-a-(z-a)=y-z=x，但这组可行解却具有比y,z更小的目11000000标函数值，即y+z-2a。这就证明了y,z并不是最优解，从而导出矛盾。所以这一般的0000结论就是对于以上的线性规划问题，其最优解必须满足要吗y=0，要吗z=0，从而其最优目标值要吗是x，要吗是-x，即IxI。现在推广到有限维度的向量Lnorm最小化，即minIIxII=min丫IxI。它等价于以下的11i线性规划问题minc(Y+Z)Y-Z=XY,Z>0其中c是1行n列的矩阵，并且每个元

15、素都是1。到现在一切应该都清晰明白了，总结如下：问题minIIaIIst.a=s,aep可以转化为线性规划问题minctxs.tAx=b,x>0，1其中，ct=1,1,1，xe2p，A=，一，b=s;求得最优化解x后可得变量a的最1x2p0优化解a=x(1:p)-x(p+1:2p)o0004、基于linprog的基追踪MATLAB代码(BPinprog.m)functionalpha=BP_linprog(s,Phi)%BP_linprog(BasisPursuitwithlinprog)Summaryofthisfunctiongoeshere%Version:1.0writtenby

16、jbb05232016-07-21%Reference:ChenSS,DonohoDL,SaundersMA.Atomicdecompositionby%basispursuitJ.SIAMreview,2001,43(1):129-159.(Availableat:%/viewdoc/download?doi=7.4272&rep=rep1&type=pdf)%Detailedexplanationgoeshere%s=Phi*alpha(alphaisasparsevector)%Givens&P

17、hi,trytoderivealphas_rows,s_columns=size(s);ifs_rows<s_columnss=s'%sshouldbeacolumnvectorendp=size(Phi,2);%accordingtosection3.1ofthereferencec=ones(2*p,1);A=Phi,-Phi;b=s;lb=zeros(2*p,1);x0=linprog(c,A,b,lb);alpha=x0(1:p)-x0(p+1:2*p);end5、基追踪单次重构测试代码(CS_Reconstuction_Test.m)测试代码与OMP测试单码相同，仅仅是修改了重构函数。%压缩感知重构算法测试clearall;closeall;clc;M=64;%观测值个数N=256;%信号x的长度K=10;%信号x的稀疏度Index_K=randperm(N);x=zeros(N,1);x(Index_K(l:K)=5*randn(K,l);%x为K稀疏的，且位置是随机的Psi=eye(N);%x本身是稀疏的，定义稀疏矩阵为单位阵x=Psi*thetaPhi=randn(M