《压缩感知重构算法》由会员分享，可在线阅读，更多相关《压缩感知重构算法（4页珍藏版）》请在金锄头文库上搜索。
1、压缩感知重构算法之基追踪(Basis Pursuit, BP)除匹配追踪类贪婪迭代算法之外，压缩感知重构算法另一大类就是凸优化算法或最优化 逼近方法，这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，其中最常用的方法 就是基追踪(Basis Pursuit, BP)，该方法提出使用l范数替代l范数来解决最优化问题，以便 10 使用线性规划方法来求解1。本篇我们就来讲解基追踪方法。理解基追踪方法需要一定的 最优化知识基础，可参见最优化方法分类中的内容。1、11范数和10范数最小化的等价问题在文献【2】的第4部分，较为详细的证明了l范数与l范数最小化在某条件下等价。10 证明过程是一个比较复杂
2、的数学推导，这里尽量引用文献中的原文来说明。首先，在文献【2】的4.1节，给出了 (P1)问题，并给出了 (P1)的线性规划等价形式(LP), 这个等价关系后面再详叙。4.1 The Case p = 1In the case p = 1, (P ) is a convex optimization problem. Write it out in an equivalent form, with10 being the optimization variable:min II0 II subject to 0 = y .0 1 nThis can be formulated as a lin
3、ear programming problem: let A be the n by 2m matrix 一.The linear program(LP) minlT z subject to Az = y , x 0. nzhas a solution z*, say, a vector in2m which can be partitioned as z* = u*v* ; then 0 * = u* 一 v*solves (P) . The reconstruction x = 0 * . This linear program is typically considered 11, n
4、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 工具箱(工具箱主页： http:/users.ece.gatech.edu/justin/l1magic/),在工具箱主页有介绍：L
5、1-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，
6、可以在工具箱主页下载。该工具箱一共解决了七个问题，其中第一个问题即是 Basis Pursuit ：Min- l with equality constraints. The problem1(P) min II x II subject to Ax=b,11also known as basis pursuit, finds the vector with smallest l norm1| |x | = Y x |1iithat explains the observations b . As the results in 4, 6 show, if a sufficiently spar
7、se x exists0such that Ax = b then (P) will find it. When x,A,b have real-valued entries, (P) can be 0 1 1recast as an LP (this is discussed in detail in 10).工具箱中给出了专门对(P )的代码，使用方法可参见lleq_example.m,说明文档3.11 节也进行了介绍。在附录中，给出了将( P )问题转化为线性规划问题的过程，但这个似乎并不怎么容1 易看明白：3如何将(P1 )转化为线性规划问题？尽管在11-MAGIC给出了一种基追踪的实
8、现，但需要基于它的I1eq_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 s = Y a Q
9、 .Y Y YThe principle of Basis Pursuit is to find a representation of the signal whose coefficients have minimal l norm. formally, one solves the problem1min II a II subject to a = s .(3.1)1From one point of view, (3.1) is very similar to the method of Frames (2.3): we are simply replacing the l2 nor
10、m in (2.3) with the l1 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 requi
11、res 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 fo
12、rm 7,16 is a constrained optimization problem defined in terms of a variable x e m bymin cTx subject to Ax = b, x 0,(3.2)where ctx is the objective function, Ax = b is a collection of equality constraints, and x 0 is a set of bounds. The main question is, which variables should be zero.The Basis Pur
13、suit problem (3.1) can be equivalently reformulated as a linear program in the standard form (3.2) by making the following translations:m o 2p;x o (u, v);c o (1,1);A o (，一);b o s.Hence, the solution of (3.4) can be obtained by solving an equivalent linear program. (The equivalent of minimum l optimi
14、zations with linear programming has been known since the11950s; see2). The connection between Basis Pursuit and linear programming is useful in several ways.这里，文献【3】的转化说明跟文献【2】中4.1节的说明差不多，但对初学者来说仍然 会有一定的困难，下面我们就以文献【3】中的符号为准来解读一下。首先，式(3.1)中的变量a没有非负约束，所以要将a变为两个非负变量u和v的差 a = u- v，由于u可以大于也可以小于v，所以a可以是正的
15、也可以是负的4。也就是说， 约束条件a = s要变为(u -v) = s，而这个还可以写为，-u;v = s，更清晰的写法如下：u v然后，根据范数的定义，目标函数可进一点写为：II a II =工I a I =工I u - v I1 i i iii 目标函数中有绝对值，怎么去掉呢？这里得看一下文献【5】： 对 L1norm 如何线性化的理解最主要的是要想明白为什么对单一元素的最小化，即 min I x I 等价于以下的线性规划问题。min y + zy - z = xy, z 0现在假设以上的线性规划问题的最优解y ,z，并且y 0,z 0。这个时候，总可以找0 0 0 0到一个很小的正数a使得y = y -a 0,z = z -a 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，即I xI。现在推广到有限维度的向量L norm最小化，即min II x
