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

压缩感知重构算法之基追踪（Basis Pursuit，BP）除匹配追踪类贪婪迭代算法之外，压缩感知重构算法另一大类就是凸优化算法或最优化逼近方法，这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，其中最常用的方法就是基追踪(Basis Pursuit, BP)，该方法提出使用范数替代范数来解决最优化问题，以便使用线性规划方法来求解1。本篇我们就来讲解基追踪方法。理解基追踪方法需要一定的最优化知识基础，可参见最优化方法分类中的内容。1、l1范数和l0范数最小化的等价问题在文献【2】的第4部分，较为详细的证明了范数与范数最小化在某条件下等价。证明过程是一个比较复杂的数学推导，这里尽量引用文献中的原文来说明。首先，在文献【2】的4.1节，给出了(P1)问题，并给出了(P1)的线性规划等价形式(LP)，这个等价关系后面再详叙。4.1 The Case In the case , () is a convex optimization problem. Write it out in an equivalent form, with being the optimization variable: This can be formulated as a linear programming problem: let be the by matrix . The linear program.has a solution , say, a vector in which can be partitioned as ; then solves . The reconstruction . This linear program is typically considered computationally tractable. In fact, this problem has been studied in the signal analysis literature under the name Basis Pursuit 7; in that work, very large-scale underdetermined problems.2、基追踪实现工具箱l1-MAGIC若要谈基追踪方法的实现，就必须提到l1-MAGIC工具箱（工具箱主页：/justin/l1magic/），在工具箱主页有介绍：L1-MAGIC is a collection of MATLAB routines for solving the convex optimization programs central to compressive sampling. The algorithms are based on standard interior-point methods, and are suitable for large-scale problems.另外，该工具箱专门有一个说明文档l1-magic: Recovery of Sparse Signals via Convex Programming，可以在工具箱主页下载。该工具箱一共解决了七个问题，其中第一个问题即是Basis Pursuit ：Min- with equality constraints. The problem also known as basis pursuit, finds the vector with smallest norm that explains the observations . As the results in 4, 6 show, if a sufficiently sparse exists such that then will find it. When have real-valued entries, can be recast as an LP (this is discussed in detail in 10).工具箱中给出了专门对（）的代码，使用方法可参见l1eq_example.m, 说明文档3.1节也进行了介绍。在附录中，给出了将（）问题转化为线性规划问题的过程，但这个似乎并不怎么容易看明白：3 如何将(P1)转化为线性规划问题？尽管在l1-MAGIC给出了一种基追踪的实现，但需要基于它的l1eq_pd.m文件，既然基追踪是用线性规划求解，那么就应该可以用MATLAB自带的linprog函数求解，究竟该如何将(P1)转化为标准的线性规划问题呢？我们来看文献【3】的介绍：3 Basis PursuitWe now discuss our approach to the problem of overcomplete representations. We assume that the dictionary is overcomplete, so that there are in general many representations .The principle of Basis Pursuit is to find a representation of the signal whose coefficients have minimal norm. formally, one solves the problem. (3.1)From one point of view, (3.1) is very similar to the method of Frames (2.3): we are simply replacing the norm in (2.3) with the norm. however, this apparently slight change has major consequences. The method of Frames leads to a quadratic optimization problem with linear equality constraints, and so involves essentially just the solution of a system of linear equations. In contrast, Basis Pursuit requires the solutions of a convex, nonquadratic optimization problem, which involves considerably more effort and sophistication.3.1 Linear ProgrammingTo explain the last comment, and the name Basis Pursuit, we develop a connection with linear programming (LP).The linear program in so-called standard form 7,16 is a constrained optimization problem defined in terms of a variable by (3.2)where is the objective function, is a collection of equality constraints, and is a set of bounds. The main question is, which variables should be zero.The Basis Pursuit problem (3.1) can be equivalently reformulated as a linear program in the standard form (3.2) by making the following translations:Hence, the solution of (3.4) can be obtained by solving an equivalent linear program. (The equivalent of minimum optimizations with linear programming has been known since the 1950s; see2). The connection between Basis Pursuit and linear programming is useful in several ways.这里，文献【3】的转化说明跟文献【2】中4.1节的说明差不多，但对初学者来说仍然会有一定的困难，下面我们就以文献【3】中的符号为准来解读一下。首先，式(3.1)中的变量没有非负约束，所以要将变为两个非负变量和的差，由于可以大于也可以小于，所以可以是正的也可以是负的4。也就是说，约束条件要变为，而这个还可以写为，更清晰的写法如下：然后，根据范数的定义，目标函数可进一点写为：目标函数中有绝对值，怎么去掉呢？这里得看一下文献【5】：对L1norm如何线性化的理解最主要的是要想明白为什么对单一元素的最小化，即等价于以下的线性规划问题。现在假设以上的线性规划问题的最优解，并且。这个时候，总可以找到一个很小的正数使得。而对于它们满足以上线性规划的所有约束，比如，但这组可行解却具有比更小的目标函数值，即。这就证明了并不是最优解，从而导出矛盾。所以这一般的结论就是对于以上的线性规划问题，其最优解必须满足要吗，要吗，从而其最优目标值要吗是，要吗是，即。现在推广到有限维度的向量norm最小化，即。它等价于以下的线性规划问题其中是1行列的矩阵，并且每个元素都是1。到现在一切应该都清晰明白了，总结如下：问题可以转化为线性规划问题，其中，；求得最优化解后可得变量的最优化解。4、基于linprog的基追踪MATLAB代码(BP_linprog.m)functionalpha=BP_linprog(s,Phi)%BP_linprog(BasisPursuitwithlinprog)Summaryofthisfunctiongoeshere%Version:1.0writtenbyjbb05232016-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&Phi,trytoderivealphas_rows,s_columns=size(s);ifs_rowss_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(1:K)=5*randn(K,1);%x为K稀疏的，且位置是随机的Psi=eye(N);%x本